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