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 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

Assume a language that is expressed according to the question:

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

It is known that is decidable.

Now construct Turing Machine that will decide .

Assume that for any, which makes a left move must do so at most count or step.

Here,.

Now construct as below:

• Run on for steps.
• If makes a left move, Accept

Else Reject.

Since successful is created for , is decidable for which is itself decidable as mention at starting of the solution.

Hence, above problem is decidable.A