44
$\begingroup$

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

$\endgroup$
60
$\begingroup$

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: http://kilby.stanford.edu/~rvg/154/handouts/decidability.html

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eric Leschinski Sep 10 '15 at 16:32
  • 1
    $\begingroup$ @EricLeschinski: I am not sure what you are trying to say. We are talking about Turing machines. Talking about programming languages seems irrelevant. $\endgroup$ – Aryabhata Sep 10 '15 at 21:27
  • 2
    $\begingroup$ I feel its noteworthy to state that "recognizable = recursively enumerable" and "decidable = recursive". Am I wrong? $\endgroup$ – Maha Dec 23 '16 at 4:42
  • $\begingroup$ @PardonMeForMySuperPoorMaths: I believe you are right. Feel free to make an edit! $\endgroup$ – Aryabhata Jan 18 '17 at 22:15
18
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

My answer mostly agrees with Aryabhata’s:

A language is “Turing-Recognizable” iff there exists a Turing Machine such that

  1. when encountering a string in that language, the machine terminates and accepts that string;

  2. when encountering a string not in that language, the machine either terminates and rejects that string or doesn’t terminate at all.

A language is “Turing-Decidable” iff there exists a Turing Machine such that

  1. when encountering a string in that language, the machine terminates and accepts that string;

  2. when encountering a string not in that language, the machine terminates and rejects that string.

Note that “Turing-Decidable” is a stronger condition than “Turing-Recognizable”, because, if a language is Turing-Decidable then its corresponding Turing Machine never runs forever.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ this explains it too but i found your answer most helpful $\endgroup$ – William Reed Apr 5 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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