0
$\begingroup$

If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified?

Recognizability Decidability ${\langle L\rangle}$ ${\langle \overline{L}\rangle}$
Turing-Unrecognizable Undecidable loop or reject loop or reject
Turing-Recognizable Undecidable accept reject or loop
Turing-Recognizable Decidable accept reject
Co-Turing-Recognizable Undecidable reject or loop accept
Turing-??? Undecidable accept or loop reject
Co-Turing-??? Undecidable reject accept or loop
$\endgroup$
3
  • 1
    $\begingroup$ I take it that by "loop" you mean "does not terminate"? A machine may fail to terminate without "entering a loop". $\endgroup$ Aug 11 '21 at 8:17
  • 1
    $\begingroup$ When starting a turing machine on an input, three outcomes are possible. The machine may accept, reject, or loop. By loop we mean.. never leading to a halting state -- Theory of Comp, Sipser $\endgroup$ Aug 11 '21 at 13:21
  • $\begingroup$ Loop means "not accept", i.e., reject. If it halts on all rejects, it halts on all inputs. $\endgroup$
    – vonbrand
    Aug 14 '21 at 16:38
1
$\begingroup$

To answer the question

If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified?

$L$ is Turing-unrecognizable, but $\overline{L}$ is Turing-recognizable.

To see this, let $L=\overline{A_{TM}}$ and $\overline{L}=A_{TM}$, where $A_{TM} = \{(M,w)|\space M \space \text{is a TM that accepts} \space w\}$.

We can create a TM $M_L$ for $L$ that simulates the execution of the input $M$ on $w$. This TM will always halt and rejects when $M$ accepts but it is not guaranteed to always halt when $M$ does not accept. This is still a valid TM but not a recognizer. In Sipser it was proven that $L$ is unrecognizable but $\overline{L} $ is recognizable.

I think your table is a little misleading since it somehow hides the possibility of $L$ or its complement being TM-recognizable but not TM-decidable. Or maybe you overlooked the possibility that there are TM that are not recognizers. I am not sure what is the proper term to be used for them, though.

$\endgroup$
1
  • $\begingroup$ So basically we don't need to distinguish between reject and loop for recognizability, both are considered a fail to accept. Updated my table, but with this clarification I see that my accept/loop cases are invalid. $\endgroup$ Aug 12 '21 at 13:13

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.