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?
$\begingroup$
$\endgroup$
10
-
$\begingroup$ Does a TM that visits infinitely many tape cells ever halt? $\endgroup$– András SalamonApr 22, 2013 at 0:16
-
$\begingroup$ No, but even if it visits a finite number of cells, it may still not halt. $\endgroup$– idealistikzApr 22, 2013 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 NikolovApr 22, 2013 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, 2013 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$– Patrick87Apr 22, 2013 at 17:10
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Yes this approach is correct. Try to visit a new blank cell between two computation steps by e.g. using some markers.