Question

Question: Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left at any point during its computation on w. Formulate this problem as a language and show that it is decidable.

Short answer

The given problem in the question is undecidable.

Step-by-step solution

Introduction to Turing Machine and Undecidability

Turing Machine

A Turing Machine is a computational model concept that runs on the unrestricted grammar of Type-0. It accepts a recursive enumerable language and comprises of an infinite tape length, where reading and writing operations can be performed accordingly.

Undecidable

A problem is undecidable if no Turing Machine exists, which will halt in an finite amount of time.

Proving the language is undecidable

Assume a language that is expressed according to the given question:

$L{M}_{TM}=\left\{\left(M,w\right)|MisTuringMachinethatmovesleftwhilecomputingw\right\}.$

It is known that$L{M}_{TM}$is decidable.

Now, construct a Turing Machine$Lef{t}_{TM}$that will decide $L{M}_{TM}$.

Assume that for any $TM$, which makes a left move, must do so at most$\left(w+n_M+1\right)$counts or steps.

Here,$n_M=NumberofstatesofMandwisthesizeofinput.$

Now, construct$Lef{t}_{TM}$as shown below:

$Lef{t}_{TM}=oninput\left(M,w\right):$

• Run M on w for$\left(w+n_M+1\right)$steps.
• If M makes a left move, accept, otherwise reject.

Since successful TM is created for$Lef{t}_{TM}$,$Lef{t}_{TM}$is decidable for$L{M}_{TM},$which is decidable as mentioned at the start of the solution.

Hence, the above problem is decidable.