2
$\begingroup$

I am attempting to prove the following problem is undecidable. Given a Turing machine $M$ and input $x$, does $M$ visit infinitely many tape cells on input $x$?

I am considering a reduction from the halting problem. Is this the right approach?

$\endgroup$
  • $\begingroup$ Does a TM that visits infinitely many tape cells ever halt? $\endgroup$ – András Salamon Apr 22 '13 at 0:16
  • $\begingroup$ No, but even if it visits a finite number of cells, it may still not halt. $\endgroup$ – idealistikz Apr 22 '13 at 0:25
  • 3
    $\begingroup$ hint: consider a machine which after each step shifts the entire contents of the tape one cell to the right. $\endgroup$ – Sasho Nikolov Apr 22 '13 at 5:55
  • $\begingroup$ To the right, find many similar quesitons. Have a look and improve your question with an approach. See here for a related meta discussion. $\endgroup$ – Raphael Apr 22 '13 at 11:01
  • $\begingroup$ While it's true that not all TMs that halt visit infinitely many tape cells, the halting problem is solvable if you restrict TMs to those which visit a finite number of cells. A reduction from the Halting problem should work: being able to solve this problem would allow you to solve the Halting problem would allow you to solve the Halting problem for all TMs by first using the algorithm to see whether it visits infinitely many cells; if not, run the algorithm to see whether a TM visiting a finite number of cells halts. $\endgroup$ – Patrick87 Apr 22 '13 at 17:10
3
$\begingroup$

Based on my comments, I might as well make this an answer, and let the community decide whether it's right or not.

Suppose you could decide whether a TM visits an infinite number of cells on an input. Here's how to solve the Halting problem given this information:

Halts(TM, input)
1. if the TM visits an infinite number of cells for the input then return false
2. configurations = {}
3. while(true)
4.     configurations.add(non-blank tape area, TM head position, state)
5.     let the TM execute one step
6.     if state is halt accept or halt reject, return true
7.     if configurations.contains(non-blank tape area, TM head position, state) then return false
8. loop

This works because, if the TM doesn't visit an infinite number of cells, it visits some finite number of cells, $n$. The number of distinct configurations is therefore $|\Sigma|^n \times n \times |Q|$, and configurations.size() will never be bigger than this. By the pigeonhole principle, we must satisfy at least condition #7 in a finite number of moves. If none of the reached configurations enters a halting state, we never will; so we have to halt before we see the same configuration twice.

$\endgroup$
0
$\begingroup$

Yes this approach is correct. Try to visit a new blank cell between two computation steps by e.g. using some markers.

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