Decidable languages

286 Views Asked by At

I have been trying to understand Turing machine in a intuitive way and most of the resources I find are filled with the mathematical terms and notations. I agree that its because of the fact that in mathematics we cannot afford ambiguity. Having said that I want to know the intuitive meaning of the decidable language.

After reading various resources I could say that the DECIDABLE languages are:

For all string s in the Languages L if there exists a Turing machine which HALTS either by ACCEPTING or REJECTING the string s.

I know that there are similar questions asked but I need to know if I am clear in my understanding.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, that is correct. A language $L$ is decidable if there exists a Turing machine such that any time you give it a string from $L$ as input, it will always halt, either accepting or rejecting the string. Such a Turing machine is called a decider for the language, because it decides whether a given string is in the language or not.

A semidecidable (or recognizable) language is similar, but here the Turing machine does not need to always halt. A recognizer for a language only needs to halt with accept if given a string that is in the language, whereas when it is given a string not in the language, it may reject or never halt.