# Halts for all rejects, but might accept/loop otherwise?

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
• I take it that by "loop" you mean "does not terminate"? A machine may fail to terminate without "entering a loop". Aug 11 '21 at 8:17
• 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 Aug 11 '21 at 13:21
• Loop means "not accept", i.e., reject. If it halts on all rejects, it halts on all inputs. Aug 14 '21 at 16:38

$$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.
• 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. Aug 12 '21 at 13:13