-1
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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!)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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