2
$\begingroup$

We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move left or not" among the infinite strings. I have found internet contents but very difficult to understand. I want to understand just intuition which is brief, not the concrete proof.

$\endgroup$
6
  • $\begingroup$ At first glance, turing machines making no left move cannot be very complicated since they always read a blank (assuming that we start , as usual , with an emty tape). This might be wrong. If such a machine can be complicated, it is clear that the decision whether the machine makes a left-move is difficult as well. Which references do you have abouth this ? $\endgroup$
    – Peter
    Commented Oct 16, 2021 at 12:50
  • $\begingroup$ @Peter When the machine makes a left-move is difficult as well? $\endgroup$
    – S. M.
    Commented Oct 16, 2021 at 12:53
  • $\begingroup$ Of course the machine can jump between many states, but I am not sure whether this can be made complicated enough to lead to "undecidable". If the problem is actually undecidable, it must be possible to make such a machine "arbitary complicated" , otherwise we could decide whether there is a left-move. $\endgroup$
    – Peter
    Commented Oct 16, 2021 at 12:59
  • $\begingroup$ I am not able to imagine a complicated enough machine that does NOT make a left-move, so I wonder how the problem can be undecidable. $\endgroup$
    – Peter
    Commented Oct 16, 2021 at 13:01
  • 2
    $\begingroup$ A Turing machine that can only move right is essentially a finite state automaton. Sure it can write to the tape, but that isn't any more powerful than just keeping track of a bit of extra data in the state. $\endgroup$
    – TomKern
    Commented Oct 16, 2021 at 13:08

1 Answer 1

8
$\begingroup$

(Note: To avoid complications, my Turing machines always have to move either to the left or to the right; they cannot remain in place. Not using this convention makes the proofs a bit more cumbersome, but doesnt change anything meaningful.)

Theorem: The problem "Given a TM $T$ and an input $w \in \Sigma^*$, will $T$ when run on $w$ ever move to the left on the tape?" is decidable.

Proof: A decision procedure starts as follows: We simulate what $T$ does on input $w$. If we ever see $T$ moving to the left, we answer "yes". If we see it halt instead, we answer "no". If neither of these happen, then $T$ will eventually have read all of $w$ and move on to the blank part of the tape to the right of $w$.

From then on, the tape has no impact on what $T$ does anymore (as there is always a blank there anyway). We keep simulating $T$ for as many further steps as $T$ has states. Again, if we see $T$ moving to the left, we can answer "yes". If we don't see $T$ moving to the left within these extra steps, $T$ will never do so - because $T$ has already completed the loop it will now follow forever. Thus, we can answer "no" at the end.

Theorem: The problem "Given a TM $T$, does there exist an input $w \in \Sigma^*$ such that $T$ ever moves left when run on $w$?" is decidable.

Proof: We inspect the control mechanism of $T$, and see whether there is any path from the starting state to transition involving a move to the left at all. If there is no such path, then obviously $T$ can never move to the left regardless of the input, and we answer "no". If there is such a path, we can answer "yes". To see this, consider a shortest such path. As $T$ would move left for the first time on the end of that path, every symbol it reads is a fresh symbol from the input word. Thus, by letting $w$ be whatever $T$ needs to read to go along this path, we can make $T$ move to the left.

$\endgroup$
1
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Commented Oct 18, 2021 at 15:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .