0
$\begingroup$

Prove that the following language is recursively enumerable: L = {<M,x> | Turing machine M enters the same configuration twice on input x}

I have tried to construct a TM that maintains the current configuration which is of the form (u,q,v) where uv is the current tape content and the tape head is over the first symbol of v and q is the current state. However this would require infinite states to maintain the current tape content. I am not sure how to start this?

Improve this question
$\endgroup$
2
  • $\begingroup$ Given input <M, x>, could you construct a Turing machine which halts iff M enters the same configuration twice on input x? $\endgroup$
    – Command Master
    Commented Apr 28, 2023 at 3:41
  • $\begingroup$ @CommandMaster That is the idea but how do you do that ? $\endgroup$
    – revision
    Commented Apr 28, 2023 at 14:29

1 Answer 1

Reset to default
0
$\begingroup$

Big Hint: You can simulate infinite, random access memory (RAM) using a turing machine (this would not require an infinite number of states).

As you mentioned, you can encode the current configuration when running $M$ on $x$, so if you can store configurations in your unlimited memory, do you see how you can detect when $M$ enters the same configuration?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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