Difference between language is decidable and function calculable by turing machine

539 Views Asked by At

I'm trying to understand the difference between saying a language is decidable and a function is calculable by a turing machine. I must have understood something wrong, because for me it doesn't make much sense to speak about languages being decidable, but instead if a function is calculable. I see a Turing Machine as a machine that has an input and an output. The input being a word from a language and the output being the result of this word, the function value. For me a function is a superior concept in the sense that a language is the domain of the function. A language itself has no range, no output.

I guess my question is, given a calcultable function $f$ with a domain (language) $L$, isn't the function language $L$ always decidable?

1

There are 1 best solutions below

0
On BEST ANSWER

"language being decidable" just means there exists a computable function that tells you whether or not a string is in the language