Is it decidable whether a TM reaches some position on the tape?

Problem Detail: 

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.

For an integer $c>1$, and the following three problems:

1. Is it true that for every input $x$, M does not pass the $|x|+c$ position when running on $x$?

2. Is it true that for every input $x$, M does not pass the $\max \{|x|-c,1 \}$ position when running on $x$?

3. Is it true that for every input $x$, M does not pass the $(|x|+1)/c$ position when running on $x$?

How many problems are decidable?

Problem number (1), in my opinion, is in $\text {coRE} \smallsetminus \text R$ if I understand correct since, I can run all inputs in parallel, and stop if some input reached this position and for showing that it's not in $\text R$ I can reduce the complement of Atm to it. I construct a Turing machine $M'$ as follows: for an input $y$ I check if $y$ is a history of computation, if it is, then $M'$ running right and doesn't stop, if it's not, then it stops.

For (3), I believe that it is decidable since for $c \geqslant 2$ it is all the Turing machines that always stay on the first cell of the stripe, since for a string of one char it can pass the first cell, so I need to simulate all the strings of length 1 for $|Q|+1$ steps (Is this correct?), and see if I'm using only the first cell in all of them.

I don't really know what to do with (2).

Asked By : Jozef

Answered By : SamM

Any situation which asks whether a Turing Machine is confined to a finite section of the tape (say of length $n$) on a given input is decidable.

The argument works as follows. Consider the Turing Machine, the tape, and the position of the Turing Machine on the tape. All together these have a finite number of configurations. To be specific, there are only $t = n|\Gamma|^n|Q|$ possible configurations. $\Gamma$ is the set of tape symbols and $Q$ is the set of states. I'll continue to use the word "configuration" to describe the state of the Turing Machine combined with the state of the tape and its position on the tape for the remainder of this answer, but that is not standard vocabulary.

Run the machine, keeping track of all its past configurations. If it ever goes beyond point $n$, return "yes, $M$ passes position $n$". Otherwise, the machine is somewhere between 0 and $n$. If the machine ever repeats a configuration--its state, the symbols on the tape, and its position on the tape are identical to what they were before--return "no, $M$ never passes position $n$."

By the pidgeonhole principle, this has to happen in no more than $t+1$ steps. So all of the above is decidable; after at most $t+1$ simulated steps you get an answer.

A quick note on why this works: when the machine, the tape, and its position on the tape repeat themselves, there must have been a sequence of configurations between these repetitions. This sequence will happen again, leading to the same configuration one more time--the machine is in an infinite loop. This is because we're keeping track of every aspect of the Turing Machine; nothing outside of the configuration can have an impact on what happened. So when a configuration repeats, it will repeat again, with an identical series of configurations in between.

So confining the tape to a finite part of the string is decidable. Therefore, by iterating over all possible input strings, the problem is in $\text{coRE}$ for all three questions. You may have already realized this (between your ideas for 1 and 3 and Ran G's answer for 2 it seems solved completely anyway) but I figured it may be worth posting nonetheless.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3119