3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Who is the author of your solution manual? Can you add a reference to it? $\endgroup$
    – John L.
    Commented Mar 8, 2019 at 8:18
  • $\begingroup$ It's not exactly a solution manual... Its the solution of a test series I follow for my exams. (Please check the 1st question) gradeup.co/… $\endgroup$ Commented Mar 8, 2019 at 8:24
  • $\begingroup$ "After all, we only have to check whether we come across state q when we feed s to M." -- How do you check that? Keep in mind that TMs, other than NFA and PDA, are not limited to a single pass over the input, and can write arbitrarily many symbols to the tape during their computation. $\endgroup$
    – Raphael
    Commented Mar 8, 2019 at 10:45

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Hi @Apass.Jack, I have one more question: If I was asked whether turing machine TM reaches state,say $q_4$ when provided an input 'aaaa', then can I claim that this problem is decidable? $\endgroup$ Commented Mar 8, 2019 at 8:40
  • 1
    $\begingroup$ Good question. No. Recall that it is not decidable, given a Turing machine $M$ and empty input, whether it will halt. we can construct $M'$ that behaves like $M$ but ignores the input (such as erasing input then starting from scratch). Renaming states of $M'$ so that a new state $q_4$ will be the new final halting state. So $M'$ reaches $q_4$ on 'aaaa' iff $M$ halts on empty input. If we could decide the former, then we could decide the later. $\endgroup$
    – John L.
    Commented Mar 8, 2019 at 9:11
  • 1
    $\begingroup$ @AbhilashMishra Yes, the Turing machine must vary for this problem-answer pair to hold. I am going to update the question so that it will not be ambiguous. I am going to update the answer as well. $\endgroup$
    – John L.
    Commented Mar 8, 2019 at 16:24
  • 1
    $\begingroup$ Nitpick: there can be multiple final states. It's of course trivial to create an equivalent Turing machine with a single accept state (as long as $L(M) \neq \emptyset$, at least), but it's a formal gap. $\endgroup$
    – Raphael
    Commented Mar 9, 2019 at 0:40
  • 1
    $\begingroup$ @Raphael Nitpicking continued. Introduction to the theory of computation by Michael Sipser defines Turing machine as having a unique accept state and a unique reject state. Of course, your nitpicking makes sense since Turing machines can be defined differently. $\endgroup$
    – John L.
    Commented Mar 9, 2019 at 4:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.