Question

Question: Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol 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 type of Turing Machine is undecidable which is mentioned in the question.

Step-by-step solution

Introduction to 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.

Proving the problem is undecidable

Assume that:

$L=\left\{\left(M\right)\text{|}Misasingle-tapeTuringmachine\right\}$

M writes a blank symbol over a non-blank symbol on any input

By proving$A_{TM}$ is reduced to L.

Assume that L is decidable, and let R be a Turing Machine that decides L.

Use R to build a Turing Machine S that decides $A_{TM}$.

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

• Use M and w to construct Turing Machine $T_M$

On any input $T_M$:

1. Run M on w.
2. If M accepts, write a true blank symbol

• Run R on $T_M$to check if $T_M$can write a blank.
• If R accepts, Then M will accept w. Thus accepted.
• But if R rejects, then M will reject w.

Now since R and S both are decider and S work like R, thus S act as decider of $A_{TM}$

But this is contradiction as$A_{TM}$ is undecidable.

So, L becomes undecidable.