patternMinor
Is it decidable whether a Turing machine M will reach state q on input s?
Viewed 0 times
reachinputdecidablewillstatemachineturingwhether
Problem
Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$?
As we are not given anything about the word length, I assume that we have a finite length word. Then I believe this problem is decidable. After all, we only have to check whether we come across state $q$ when we feed $w$ to $M$.
But my solution manual claims that it is an undecidable problem.
Am I correct or is the manual correct? Do we ever take into consideration a word with infinite length during such analysis?
As we are not given anything about the word length, I assume that we have a finite length word. Then I believe this problem is decidable. After all, we only have to check whether we come across state $q$ when we feed $w$ to $M$.
But my solution manual claims that it is an undecidable problem.
Am I correct or is the manual correct? Do we ever take into consideration a word with infinite length during such analysis?
Solution
Do we ever take into consideration a word with infinite length during such analysis?
Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite.
Here is a more formal restatement/understanding of the problem in the question.
$$\begin{align}\text{TRIPLE }=&\{\langle M, q, w\rangle: M\text{ is a Turing machine. }\\
&q\text{ is one of the states of }M. \\
&w\text{ is a word over the input alphabet of }M.\}\\
\text{REACH }=&\{\langle M, q, w\rangle\in\text{TRIPLE}: M\text{ will reach }q\text{ on input }w. \}\end{align}$$
Is $\text{REACH}$ decidable? (the problem of state reachability)
Assume $\text{REACH}$ is decidable. By definition, there is a Turing machine $T$, which, given a Turing machine $M$, its state $q$ and an input word $w$ as its input, it will accept the input if and only if $M$ will reach state $q$ on input $w$.
Recall that $A_{\text{TM}} = \{\langle M,w\rangle : M \text{ is a TM and }M\text{ accepts }w\}$. Construct a new Turing machine $T'$ such that given input $\langle M, w\rangle$ where $M$ is a TM and $w$ is an input for $M$, $T'$ will change the input to $w'=\langle M, q_{\text{accept}}, w\rangle$ where $q_{\text{accept}}$ is the unique accept state of $M$, and then simulate $T$ on input $w'$. We see that $T'$ is a decider for $A_{\text{TM}}$.
I would believe you have learned that $A_{\text{TM}}$ is not decidable. That contradiction shows that our assumption must be wrong, which means this problem of state reachability cannot be decidable.
(In case that the Turing machines defined for you could have multiple accept states, $T'$ could replace all accept states in $M$ with a unique accept state at first.)
Reader can also take a look at a more intuitive and less notation-cluttered but less rigorous version of this answer here, which is just the first version of this answer.
Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite.
Here is a more formal restatement/understanding of the problem in the question.
$$\begin{align}\text{TRIPLE }=&\{\langle M, q, w\rangle: M\text{ is a Turing machine. }\\
&q\text{ is one of the states of }M. \\
&w\text{ is a word over the input alphabet of }M.\}\\
\text{REACH }=&\{\langle M, q, w\rangle\in\text{TRIPLE}: M\text{ will reach }q\text{ on input }w. \}\end{align}$$
Is $\text{REACH}$ decidable? (the problem of state reachability)
Assume $\text{REACH}$ is decidable. By definition, there is a Turing machine $T$, which, given a Turing machine $M$, its state $q$ and an input word $w$ as its input, it will accept the input if and only if $M$ will reach state $q$ on input $w$.
Recall that $A_{\text{TM}} = \{\langle M,w\rangle : M \text{ is a TM and }M\text{ accepts }w\}$. Construct a new Turing machine $T'$ such that given input $\langle M, w\rangle$ where $M$ is a TM and $w$ is an input for $M$, $T'$ will change the input to $w'=\langle M, q_{\text{accept}}, w\rangle$ where $q_{\text{accept}}$ is the unique accept state of $M$, and then simulate $T$ on input $w'$. We see that $T'$ is a decider for $A_{\text{TM}}$.
I would believe you have learned that $A_{\text{TM}}$ is not decidable. That contradiction shows that our assumption must be wrong, which means this problem of state reachability cannot be decidable.
(In case that the Turing machines defined for you could have multiple accept states, $T'$ could replace all accept states in $M$ with a unique accept state at first.)
Reader can also take a look at a more intuitive and less notation-cluttered but less rigorous version of this answer here, which is just the first version of this answer.
Context
StackExchange Computer Science Q#105316, answer score: 5
Revisions (0)
No revisions yet.