Question

Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

Short answer

The given problem in question is undecidable.

Step-by-step solution

Introduction to Turing Machine and Undecidability

Turing Machine

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-0. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Undecidable

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time

Proving the language is undecidable

Defining a language for above problem:

$L_{TM}=\left\{\left(M,w\right)|MisTuringMachineandisstringwhichtriestomoveitsheadfromleft-mosttapecell\right\}$

Let there be a Turing Machine decider $R$that decides $L_{TM}$.

Construct a Turing Machine $S$that will use $R$to decide $A_{TM}$.

$S=Oninput\left(M,w\right)$

• Convert $M$to $M\text{'}$such that $M\text{'}$firstly moves input from one cell to the right and will enter new symbol ‘$\#$’ on the left-most cell of tape.

Then run $M\text{'}$will make $M$to run on the input.

If $M\text{'}$come across symbol ‘$\#$’, then $M\text{'}$moves its head one cell to the right and remain in same state.

So if $M$accepts, $M\text{'}$ moves its head to the left.

• Run $R$on input $\left(M\text{'},w\right)$
• If $R$accepts, then $M\text{'}$accepts, else reject.

Since $R$is decider of $A_{TM}$and define $S$with help of $R$, so $S$must also decide $A_{TM}$.

But $A_{TM}$is undecidable, and $S$is decider of $L_{TM}$.

Therefore,$L_{TM}$ is undecidable.