Is it decidable whether a Turing machine M will reach state q on input s?
-
05-11-2019 - |
Pergunta
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?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange