5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I think your answer is right. But before I accept the answer, I just wanted to get one clarification: am I right in saying that in your equivalent machine, the ``no''-equivalent state is not a halting state any more? And it is just some dummy state? $\endgroup$ – Ankur Nov 30 '12 at 0:06
  • 1
    $\begingroup$ The old no-state was halting, in the new machine the same state walks right (ad infinitum). You are right, it is no longer marked as rejecting state, I just reuse the state in another capacity. It is dummy in the sense it will not lead to a acceptance ever, but is necessary in the Papadimitriou way of accepting. I see it as a polite way of saying no: we avoid the answer but not halting. [English is not my mother tongue, I might slip in some ambiguities] $\endgroup$ – Hendrik Jan Nov 30 '12 at 0:17

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.