last day (15 days later) » 

15:39
5
A: Why "Turing machine makes no left move"- is undecidable?

Arno(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...

But there are many infinitely many string, how could we check all strings? Here only one string we need to check?
@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?".
Yes, exactly I mean it
@Arno Seems that I misinterpreted the question in the same way.
@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?
15:39
@Student The problem you had in mind is apparently completely different from how Arno and I interpreted it.
@peter now if you understand, please explain me.
As I said, I am not an expert in this topic, but perhaps Rice's theorem helps.
@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.
@Student I have added the answer and proof for the other version of the question.
@Arno by your logic emptiness, finiteness also be decidable which is impossible.
15:39
@Student The proofs are there. Read them until you understand them.
@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?
@Student Again, please read what I have actually written.
@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?
@Student In Theorem 1, $w$ is one finite string provided to us as part of the input (as clearly stated).
So you wrote "all of w" means all character of w?
15:39
@Student Yes. And as I am getting the "avoid extended discussions" warning, let's stop here.
@Arno Machine moving in loop but how we say "no"?
In your second proof, are you assuming that the head must move either left or right on each step, and that staying in the same position is not allowed? I'm aware that that's a reasonably common convention, but it might be good to state it explicitly, since it confused me for a moment. (FWIW, I believe your proof is still salvageable even if "no move" transitions are allowed, but it does require some extra care in determining whether a left-move transition is actually reachable.)
@IlmariKaronen It's a common convention because any Turing machine can be put into that form. If the Turing machine's action in state $k$ reading symbol $s$ is "go to state $k'$, write symbol $s'$, stay put" then we can replace those instructions by whatever the instructions for state $k'$, symbol $s'$ say. Repeat until no "stay put" actions are left.
@MishaLavrov: …or until your find a loop where the machine keeps writing to the same cell but never moves. :) But yes, you make a good point, and it clearly shows that Arno's result still holds even if "no move" transitions are allowed, since they can be easily eliminated (except for infinite no-move loops, which for this particular proof we can treat as equivalent to halting).
@IlmariKaronen Yes, I like my TMs to be always on the move. For these arguments in particular.

last day (15 days later) »