patternMinor
Decider for the family of Turing machines that move infinitly to the right on some input
Viewed 0 times
thedeciderrightmoveinputthatformachinessometuring
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#3180, answer score: 7
Revisions (0)
No revisions yet.