1
$\begingroup$

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.

Now how about

$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?

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

As commented by dkaeae, there is no way to verify whether a general Turing machine (TM) loops forever on some input. No matter how many operations has been run by an algorithm that simulates the TM on that input, that algorithm cannot be sure the TM will loop forever. The TM may or may not stop at the next moment.

The intuition is pretty simple. The only way to know the behavior of a TM on some input is to run it, unless there are some extra information or restriction about the TM that we can take advantage of, such as only finitely many cells are used.

We can recognize all Turing machines that accepts some string that ends with 111 since we can list all such strings and we can use an universal TM to simulate all Turing machines on all such strings sort of in parallel, thanks to dovetailing. Ditto with the case of rejecting.

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.

$\endgroup$

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.