1
$\begingroup$

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?

the original question: Show that the set of all TMs that move only to the right and loop for some input is decidable

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}

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

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am trying to decide if there is a word w, that in the computation of M(w) the head only moves right and M never stops. How does reviewing a finite number of words in |Q|+1 help? $\endgroup$ – Ella Jun 12 '20 at 9:16
  • $\begingroup$ 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 $\endgroup$ – nir shahar Jun 12 '20 at 9:21
  • $\begingroup$ איפה בא לידי ביטוי החלק שהמכונה זזה רק ימינה? $\endgroup$ – Ella Jun 12 '20 at 10:50
  • $\begingroup$ 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) $\endgroup$ – nir shahar Jun 12 '20 at 10:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.