91Ó°ÊÓ

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

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

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.