Question

Let is a single-tape TM that never modifies the portion of the tape that contains the input w. Is X decidable? Prove your answer.

Short answer

X is undecidable.

Step-by-step solution

Single Tape 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.

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.

Checking decidability of X.

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}\le {}_{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}\le {}_{m}X$and is undecidable.

Therefore, is undecidable.