# decider for a question not clear

This question was asked and answered but I cannot understand the solution.

1. Why is it sufficient to test all strings of |Q| + 1 length?
2. Why should special state q be found?

L2={ M | M is a TM and there exists an input w such that in the computation of M(w) the head only moves right and M never stops}

• Does this answer your question? How this language is decidable? – ttnick Jun 12 '20 at 8:37
• No. there is no answer there. I have the solution, I can't understand it. – Ella Jun 12 '20 at 8:38

The pigeonhole principle. If you go through $$|Q|+1$$ states, then there must be a state you have been in twice already. This means that because the input is $$\sqcup$$ almost all of the time, then we are stuck in a loop and the machine wont halt
• If you a word that reaches the special state that gets you stuck in a loop, you are done. To find one, look at the state-transition graph of $M$ and use any standard algorithm to find if a path exists to the special state – nir shahar Jun 12 '20 at 9:21
• The machine will see only the $\sqcup$ symbol (after reading $w$). There will be no moving left or staying in place - so writing into the tape is pretty useless as it does not affect the run. Moving only to the right ensures that we will always read the same symbol - and therefore be able to know there is a definite cycle. Also it helps find the $w$ that reaches the "special" state (think why) – nir shahar Jun 12 '20 at 10:55