2
$\begingroup$

I have the following question out of an old exam that I'm solving:

Input: a Turing machine and input w Question: Does on running of M on w, at least one of the following things happen           -M stops of w           -M visits the same configuration at least twice 

First I thought that it's clearly in $RE$, it is a recursive enumerable question since we can simulate running of $M$ on $w$ and list the configuration or wait until it stops,

but then I thought to myself:"If it visits the same configuration more than twice, it must be in an infinite loop", because, as I understand, if it reached the same configuration it's gonna copy the same transitions, over and over again, so the problem might be in $R$, it's decidable, since it's the same question as "It stops for $w$ or it doesn't"?

What do you think? Thank you!

  • 0
    Right, sorry :)2012-08-12

2 Answers 2

4

The $A = \{\langle M, w \rangle : M \text{ halts on } w \text{ or } M \text{ visits the same configuration twice }\}$ is r.e.

The algorithm that witnesses this property would just run $M$ on $w$ until (if ever) it halts or visits a configuration twice.

$A$ is not computable. You can reduce the Halting Problem $K = \{\langle M, w \rangle : M \text{ halts on } w\}$ to $A$. Given $\langle M, w \rangle$, ask if $\langle M, w \rangle \in A$. If it is then run $M$ on $w$. Since $\langle M, w \rangle$ is in $A$, you are certain that $M$ will halt on $w$ or $M$ will reach a configuration twice. Keep running $M$ until one of the two happens. If $M$ halts on $w$, then $\langle M, w \rangle \in K$. If $M$ on $w$ reaches a configuration twice, then it loops so $\langle M, w \rangle \notin K$. If $\langle M, w \rangle \notin A$, then clearly $\langle M, w \rangle \notin K$. Thus using $A$, you can computably know $K$. Since $K$, the halting problem, is know to be R.E. but not computable, $A$ can not be computable. If fact since $K$ is a complete c.e. set with respect to $m$-reductions, $A$ is actually $m$-equivalent to $K$, the halting problem. $m$-reduction is stronger is stronger that Turing reduction. So in a very strong sense $A$ and $K$ are the same.

Also your claim "since it's the same question as "It stops for w or it doesn't"? is not true. It is possible that you not halt but do not repeat any configuration. For example a Turing machine that just keeps writing $1$ on the tape and never halts is a Turing that never halts but never comes back to the same configuration since the tape will never be the same as it was in any previous stage.


General hint. To prove that something is recursive (decidable) or r.e., you need to produce a Turing Machine that witnesses that fact that something is decidable or r.e. However to show that something is not recursive or r.e., you need to the reduce something known to not recursive or r.e. to your set. The good set that is is r.e. but not computable is the halting problem $K$. Since $K$ is not computable, the complement of $K$, $\bar{K}$, is not r.e.

Of course this will not always work. As mentioned above $K$ is the most computationally power r.e. set. There are r.e. that are not computable but strictly weaker than $K$.

  • 0
    @Raphael The Halting problem for Deterministic Turing Machines is noncomputable. The noncomputability of that form of the halting problem is all I need to show that $A$ is noncomputable.2012-08-12
2

We can modify a Turing machine $T$ by replacing every computation step of $T$ by a procedure in which we go to the left end of the (used portion of) the tape, and one more step left, print a special symbol $U$, and then hustle back to do the intended step. So in the modified machine, a configuration never repeats. Thus if we can solve your problem, we can solve the Halting Problem. The conclusion is that your problem is not decidable.