I need help finding an algorithm which, given a Turing machine description $\langle M \rangle$, decides whether there exists an input $w$ such that in the computation of $M(w)$, the head only moves right and $M$ never stops.
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ What have you tried? $\endgroup$– RaphaelCommented Aug 14, 2012 at 15:43
-
$\begingroup$ cs.stackexchange.com/q/43892/755, cs.stackexchange.com/q/78124/755 $\endgroup$– D.W. ♦Commented Jun 26, 2021 at 19:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Given a Turing machine $M$ for which such an input exists, what does $M$'s state graph look like?
For some input $w$, there is a computation of the form $q_0 \leadsto q (\leadsto q)^\omega$ whose transitions all have movement $R$ (or $N$, depending on the meaning of "only"). Therefore, the state graph has to have an "$R$-path" from $q_0$ to some $q$ which lies on an "$R$-cycle".
Is this also a sufficient criterion? The answers to both questions lead you towards a decision procedure.