Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
"language being decidable" just means there exists a computable function that tells you whether or not a string is in the language. –  user58512 Jan 21 '13 at 14:19
    
well, that solves my question! –  Clash Jan 21 '13 at 14:27
    
A language $L$ can be regarded as the function that sends elements of $L$ to "yes" and sends all other inputs to "no". A language is decidable if, when viewed as a function in this way, it is a calculable function. –  Andreas Blass Jan 21 '13 at 14:29

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.