Determine if the following problem is decidable or not : Does the read–write head of a TM with the input w leave the word w?
-
29-09-2020 - |
Question
Determine if the following problem is decidable or not : Does the read–write head of a TM with the given input w leave the word w on the tape?
Solution
It is not clear if your language $L$ contains the pars $\langle T, w\rangle$ or if $w$ is fixed and $L$ only contains Turing machines. In any case the answer is the same.
Let $T$ be a (single tape) TM that does not leave the word $w$. Let $Q$ and $\Gamma$, be the set of states and the tape alphabet of $T$.
The number of possible configurations of $T$ can be upper bounded as a function of $|w|$, $|Q|$, and $|\Gamma|$ and this upper bound $B_T$ is computable.
To decide $L$ it suffices to simulate $T$ for $B_T$ steps. If $T$ ever leaves the word $w$ you can reject. Otherwise either $T$ halted without leaving $w$, or $T$ is stuck in an infinite loop that does not leave $w$. In both cases you can accept.