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?

cs.stackexchange https://cs.stackexchange.com/questions/127774

문제

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.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top