Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
In English one may write "M stops." or "Does M stop?", but not "Does M stops?". –  Michael Hardy Aug 11 '12 at 22:17
    
Right, sorry :) –  Jozef Aug 12 '12 at 7:47
add comment

2 Answers 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.

share|improve this answer
add comment

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

share|improve this answer
    
Thank you very much, it was very helpful. –  Jozef Aug 11 '12 at 21:08
    
But it is not possible to repeat configuration and halt, right? –  Jozef Aug 11 '12 at 21:12
    
@Jozef Yes, by exactly the reason you wrote above. –  William Aug 11 '12 at 21:13
    
I wonder if the problem itself "For $M$ and $x$, on running $M(x)$, $M$ visits the same configuration twice" is in $RE$ or in $R$ by checking $M$'s transitions, since the answer for this question has surprised me. math.stackexchange.com/questions/179909/… –  Jozef Aug 12 '12 at 6:49
    
or: "Is there input where a configuration while running M on it being repeated twice?" I got confused. –  Jozef Aug 12 '12 at 7:48
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.