We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check decidability "the Turing machine makes move left or not" on particular input string. I have found some internet contents but very difficult to understand. I want to understand just intuition which is brief, not the concrete proof.


1 Answer 1


What would happen if we never move left? Either we halt at some time, or we always see the input $\sqcup$ (blank symbol) and choose to move right. But there is a finite number of states, and by the pigeonhole principle after a long time we will get stuck in a loop in those states.

Checking if we get stuck in a loop in the states, is not hard when the input is always $\sqcup$ - since we have to consider only the states.

In summary, the idea is to use the fact we will always see the same input after a while to our advantage - the states of a TM are finite, and hence it must act very simple (even simpler than a finite deterministic automaton!)

  • $\begingroup$ Machine moving in loop but how we say yes or no? $\endgroup$
    – Punia
    Oct 16, 2021 at 18:14
  • $\begingroup$ Use the pigeonhole principle $\endgroup$
    – nir shahar
    Oct 16, 2021 at 18:54
  • $\begingroup$ You don't understand my question. I mean when Machine moving in loop, how can we decide that machine move left? $\endgroup$
    – Punia
    Oct 16, 2021 at 18:57
  • $\begingroup$ As I said, use the pigeonhole principle to know the machine got stuck in a loop, and simply check at every point in time (until you complete at least one full loop) that the machine doesn't go left $\endgroup$
    – nir shahar
    Oct 16, 2021 at 19:00
  • $\begingroup$ Looping problem is undecidable, how can you say it is decidable? $\endgroup$
    – Punia
    Oct 16, 2021 at 19:12

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.