# Recognizably turing machine question (reject / loop)

The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?

Give a deterministic TM D that recognizes L such that if $$w \in L$$ then D accepts w. Or if $$w \notin L$$, then D does not accept $$w$$. I realized this definition states on whether D accepts a $$w$$ like

$$A_{*111} = \{\langle M \rangle \mid M$$ is a TM, and $$M$$ accepts some string that ends with 111$$\}$$, which is recognizable and easy to prove through dovetailing.

$$R_{*111} = \{\langle M \rangle \mid M$$ is a TM, and $$M$$ reject some string that ends with 111$$\}$$? Is this also recognizable and would the proof be the same as the one above ? I think this will work but what about

$$L_{*111} = \{\langle M \rangle \mid M$$ is a TM, and $$M$$ loops on some string that ends with 111$$\}$$?

How do you check if something loops?

• "How do you check if something loops?" You can't. – dkaeae Jun 11 at 7:17

However, a simulation cannot be finished if the TM keeps running. There is no point of time that an algorithm can be sure that the Turing machine (TM) under inspection will loop forever. Even if it looks like the simulated TM will never stop, it might halt at the next moment. The very fact that it keeps running prevents us from making a foolproof decision on whether it will eventually halt or loop forever. So we should believe that $$L_{*111}$$ is not recognizable. In fact, we should believe the simpler language $$L_{111} = \{\langle M \rangle \mid M$$ is a TM that loop on $$111\}$$ is not recognizable either.
Of course, we still need a rigorous proof that shows neither $$L_{*111}$$ nor $$L_{111}$$ is recognizable. We can make a reduction from the known unrecognizable language $$\overline{HALT}=\{\langle M \rangle \mid M$$ is a TM that does not halt on the empty string$$\}$$ to both of them.