Prove the undecidability of DNA Mutation Problem

Theorem 5   there is no algorithm for the DNA mutation problem.

Proof. Reduction from $\mathrm{HALT}$.

Program for $\mathrm{HALT}$ read program $P$ and input $I$. $Q$ is defined as the program that is like $P$, except that after $P$ halts, $Q$ will continue running to erase all its contents on the tape, then move to the left end of the tape, and halt.

To show the idea of this proof, here is an example.

Turing Machine:

States:

$p$ is the start state, $h$ is halting state.

Input symbols:

0, 1, $\sqcup$.

Transition function:

$$(p, 0) \rightarrow (q, 0, right)$$

$$(p, 1) \rightarrow (q, \sqcup , right)$$

$$(q, 0) \rightarrow (p, 0, left)$$

$$(q, 1) \rightarrow (h, 1, left)$$

$$(h, 0) \rightarrow (p, \sqcup , right)$$

Input:

$0110$.

Now, we can transform the input to $\mathrm{HALT}$ into the input of $\mathrm{DNA}$. For this example, the Start String would be $>p0110<$. Mutation rule according to the first rule: $p0\rightarrow 0q$.
next: $p1 \rightarrow \sqcup p$.
next: $0q0 \rightarrow p00$, $1q0 \rightarrow p10$, $\sqcup q 0 \rightarrow p\sqcup 0$. $> q0 \rightarrow \ldots$¹³
Something more: $<\rightarrow \sqcup <$, $\sqcup < \rightarrow <$¹⁴.

End State: $>\ldots h \ldots <$. We can assume the Turing Machine can erase all the content on the tape before halting, in fact, that is the goal of constructing $Q$ using $P$.

If we can solve $\mathrm{DNA}$, $\mathrm{HALT}$ can be solved: if DNA mutation gives a finite answer, then $P$ halts, vice versa. $\qedsymbol$