Sign up ×
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.

What is difference between "recognizable" and "decidable" in context of Turing machines?

share|cite|improve this question

2 Answers 2

up vote 23 down vote accepted

A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.

A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.

Perhaps this link will be helpful:

share|cite|improve this answer
If valid words in a language define an infinite loop, that does not make it unrecognizable. The program is not run to determine its recognizability. Its property of being recognized means the program containing an infinite loop can be confirmed as a valid program in a finite amount of time and always accepts. For example, languages like python can validate a program in a finite amount of time even if the program specifies an infinite loop. Python is recognizable. –  Eric Leschinski Sep 10 at 16:32
@EricLeschinski: I am not sure what you are trying to say. We are talking about Turing machines. Talking about programming languages seems irrelevant. –  Aryabhata Sep 10 at 21:27

Disclaimer : I'll elaborate just a little.

When a Turing Machine(TM) is given an input, it can do one of three things :

  1. Accept the input by reaching accept state ($q_{accept}$).
  2. Reject the input by reaching reject state ($q_{reject}$).
  3. Keep computing forever. This can be called a "loop".

If the machine keeps computing forever, we consider that the machine has rejected the string but it does so in an infinite number of steps. Thus, if the machine accepts a string, it must do so in a finite number of steps!

A Language of a Turing Machine is simply the set of all strings that are accepted by the Turing Machine. In this case, we say that the Language is recognized by the Turing Machine. This brings me to the definition of a Turing Recognizable Language :

Def : A Language is called Turing Recognizable if some Turing Machine recognizes it.

Now, consider a Turing Machine $M$ and a language $L$(over input alphabet $\Sigma$) that is recognized by $M$. Thus, $L$ is a Turing Recognizable Language (since the TM $M$ recognizes it). Consider the set of strings that are not in $L$(we call it $\overline{L}$). We know that the machine $M$ does not accept these strings. So, when we simulate a string $w$ $\in$ $\overline{L}$ on $M$, there are two possibilities :

  1. M ends up on reject state ($q_{reject}$).
  2. M keeps computing forever(goes in a "loop").

If the machine $M$ is such that for all $w$ $\in$ $\overline{L}$, it produces the output by going into the reject state, then we have a Turing Machine($M$) for $L$ which has the property that, for any input (over $\Sigma^{*}$) it never goes into a loop! Thus, we can say that for any input (over $\Sigma^{*}$), the Turing Machine $M$ decides whether to accept or reject the input in a finite number of steps. The machine $M$ is called a decider. The languages for which we can design Turing Machines with the above property are called Turing Decidable languages. In the above example, we say that $M$ decides $L$. Here is the definition :

Def : A Language is called Turing Decidable if some Turing Machine decides it.

Keeping it simple - A language $L$ is Turing Decidable if some decider $M$, decides it.

For more information you can refer to : An Introduction to the Theory of Computation by Michael Sipser.

share|cite|improve this answer

Your Answer


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.