Question: You are given, as input, some Turing Machine M and some string w. The problem is to determine whether the machine M, when executed on
You are given, as input, some Turing Machine M and some string w. The problem is to determine whether the machine M, when executed on the input string w, ever moves its read-head to the left. Explain why the following algorithm is faulty:
if (some delta-rule in M has an L in the last entry of the 5-tuple of that delta-rule)
-->then when M is executed on w, the read-head will move left at some time during the computation.
--> --> else when M is executed on w, the read-head NEVER moves left during the computation.
Thanks a lot for your help!8
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
