4
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Aug 14 '12 at 12:37

This question came from our site for professional and enthusiast programmers.

  • 4
    $\begingroup$ What have you tried? $\endgroup$ – Raphael Aug 14 '12 at 15:43
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy