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.

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

Assume a language that is expressed according to the question:

$L{M}_{TM}=\left\{\left\{M,w\right\}|MisTuringMachineththatmovesleftwhilecomputingw\right\}$

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

Now construct 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)$count or step.

Here,$n_m=NumberofstatesofMandwisthesizeofinput.$.

Now construct $Lef{t}_{TM}$as 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

Else Reject.

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

Hence, above problem is decidable.