91Ó°ÊÓ

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.

A single tape Turing Machine is a type of Turing Machine which consists of only one tape on which different symbols are present on each block.

a).

Given,

is a single-tape TM that never modifies the portion of the tape that contains the input w$\left.\right\}$

We will reduce x from $A_{TM}$as: $A_{TM}≤{}_{m}X$

The reduction f is constructed as follows:

f=on input

Construct $M_0$as:

• We will move the head of the tape past x and write $ and w
• Run M on w on the space following $
• If M accepts w, move the tape head to the left of $ and write any character on x.
• If M rejects w ,$M_0$ will reject.

Output:

Now, we know that if and only if

So, if M accepts w, then$M_0$ will modify the tape and input string, else$M_0$ will reject the string without modifying input.

Now, Since $A_{TM}≤{}_{m}X$and is undecidable.

Therefore, is undecidable.