# Decider for the family of Turing machines that move infinitly to the right on some input

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.

## migrated from stackoverflow.comAug 14 '12 at 12:37

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

• What have you tried? – Raphael Aug 14 '12 at 15:43

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".