Question

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

Short answer

The assume language L is undecidable.

Step-by-step solution

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Defining Language L according to question

Let’s define a language L such that:

$\text{L}=\left\{\left(\text{M},\text{w}\right)|MisaturingmachinethattakeswasinputstringWritesanon-blanksymbolonsecondtape\right.$

Let there be two taped Turing machine $M_1$.

It takes input pair$\left(M,w\right)$ here,$w=anystring$ and $M=Turingmachine$.

M'runs M by the use of first tape on input w.

There are following two situations:

• If M accepts w, then$M_1$ writes a non-blank character from the alphabets on second tape.
• If the M halts or rejects, then we need to stop here only.

Proving L is undecidable

Now prove L is undecidable by reducing $A_{TM}$.

$A_{TM}$is undecidable as there exist no Turing Machine which halts in any input of a language A.

Let us assume that Tdecides L. In this case, T'constructT' which decides $A_{TM}$. On input (M,w), it runs the machine$M_1$ as stated above manner. Then we run T on $M_1$, and accept if T accepts or reject if Trejects.

Thus T' accepts if and only if T accepts$\left(M_1,\left(M,w\right)\right)$ if$M_1$ writes on second tape if and only if M accepts string w.

Thus T' will decide $A_{TM}$.

But,$A_{TM}$ cannot have decider as it itself is not decidable so, there is no T exist that decides L.

Thus, L is undesidable.