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 i...
@Student Your language is not very clear. Do you mean instead the problem "Given a TM $T$, does there exist an input $w \in \Sigma^*$ such that $T$ when run on $w$ will ever move to the left?".
@Arno "If neither of these happen, then T will eventually have read all of w "-- there are infinite many w how can you say T read a of w? I don't understand this line. Please elaborate.
@Peter "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."-- could you explain the meaning of this line?
@peter now if you understand, please explain me.
@peter Rice's theorem isn't not applicable on machine property. So Rice's theorem isn't applicable here.
@Arno "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."--Please explain this statement.
@Arno your first proof definitely wrong. There are infinitely many strings. How can you read all of the strings and reach at the end. And check moving left or not?
@Arno "If neither of these happen, then T will eventually have read all of w"--here all of w means?and how can you say with gurantee T reads all infinite string?
I was just thinking about the question and came here to see the discussion. But please, be kind around here: these people don't get paid to help you, you know!
I think Arno's reasoning is perfectly sound. What is meant with "T has already completed the loop it will now follow forever. " is the following:
T only reads blank symbols (since w is processed), and in doing so it alters between its states. But since T only has a finite amount of states, there will be a cycle in the states its visits after a while.
More precisely by the pigeon-hole principle, if T has n states and does n+1 moves, at least one state will have been repeated. So from then on the machine is in an endless loop.
If it didn't go left the first time it was in the loop, it will never go left, of course (since it's a loop). So at that point, the meta-turing machine can say "no, T will never go left"
Discussion between Student and Arno
Discussion between Student and Arno