Question

Question: Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

Short answer

The two-tape Turing Machine is undecidable.

Step-by-step solution

Introduction about Turing Machine

A Turing Machine is a computational model concept that runs on the unrestricted grammar of Type-0. It accepts recursive enumerable languages and comprises of an infinite tape length, where read and write operations can be performed accordingly.

To show this problem is undecidable

Let there be a language defined as:

$C=\left\{\left(M\right)\text{|}Mbeingtwo-tapedTuringMachine\left(TM\right)\right\}.$

Here, M is TM that writes a non-blank symbol on the second tape for some input string.

First, show that $A_{TM}$is reduced to C, then prove that C is undecidable.

Assume that a Turing Machine R will decide C.

Construct a Turing Machine S that uses R to decide $A_{TM}$:

$S=oninput\left(M,w\right)$

• A Tuning machine with any input string w is used to construct a two-tape TM,$T_M$ .

$T_M=oninput$ :

Run M on w on first tape.

If M accepts, then write non-blank symbol on the second tape.

• Now, run R on $T_M$ to find out whether$T_M$can write a non-blank symbol on the second tape.
• If R accepts, then M will accept w. This means that$T_M$accepted. Otherwise,$T_M$is rejected.

Now, since S decides $A_{TM}$ and $A_{TM}$ is undesirable, this makes R undecidable.