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?


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.

  • $\begingroup$ Why is |w| a upper bound ? $\endgroup$
    – Frank
    Jun 27 '20 at 20:42
  • $\begingroup$ |w| is not an upper bound. I just said that there is an upper bound which can be expressed as a function of $3$ parameters: $|w|$, $|Q|$, and $|\Gamma|$ and is computable. $\endgroup$
    – Steven
    Jun 27 '20 at 20:47

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.