- If a Turing Machine M, on input w, will M ever move its read/write head to the left?
- Determine if this violates Rice's Theorem.
1. I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:
Step 1: If M halts on w and it never moved left, reject it.
Step 2: If M ever moves left, halt and accept.
Step 3: If M loops forever (some configuration repeats) then reject it
Step 4: Otherwise, reject (M moves right, eventually encounters a blank symbol, and moves right forever, which means that M will never move left. So, reject it.)
2. We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:
"Step 2: If M ever moves left, halt and accept."
, and this does not violate Rice's Theorem.