[Solved]: Conflicting definitions of language accepted by Turing Machine?

Problem Detail: 

I am reading Papadimitriou, Computational Complexity, page 24, where it is says

We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \{\sqcup\})^*$, if $x \in L$, then $M(x) =$ ``yes''; however, if $x\notin L$, then $M(x) = \nearrow$.

The key issue is what happens for $x \notin L$. This definition insists that $M$ must not halt for $x \notin L$. Other sources I read, e.g., this says that if $x\notin L$ then either $M$ does not halt, or $M$ halts at ``no''.

Prima facie this seems to me to be a significant difference. Could someone clarify to me if these definitions are equivalent and if there is no loss of generality in talking of acceptance in the sense of Papadimitriou? Or is only one of these definitions the correct one?

Asked By : Ankur

Answered By : Hendrik Jan

The two definitions are in fact equivalent. Both halt and accept when the word belongs to the language. One is more restricted for strings outside of the language: it is not allowed to halt. Every Turing machine in the "classic" definition (which allows halting with "no") can be changed into a non-halting one easily. Just when the old machine wnat to stop in a no-state, its restricted equivalent moves into a no-sate that actually does not stop but instead keeps walking to the right (or the left, what you want). Both versions of the machine will accept the same language.

Thus, both versions define the class of recursively enumerable languages. Or partially decidable or Turing-acceptable, but I prefer the old terminology.

In conclusion, Papademitriou has a slightly non-standard definition, which is nevertheless equivalent to the commonly used one.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7025

3.2K people like this

 Download Related Notes/Documents