DNA Mutation Problem

Input:

Start string, end string, possible mutations

Output:

The least of mutations to change the start string into the end string.

Example:

$$start = CATGAT$$

$$end = ATATG$$

Mutations:

$$AT \rightarrow CAT$$

$$CA \rightarrow A$$

$$GA \rightarrow TA$$

$$A \rightarrow G$$

Definition 2   Let $A$ and $B$ be problems: $A \leq B$¹¹ means there exists a program for $A$ that lacks only code for $B$¹².

In this class, we are going to show that we have no algorithm solving $\mathrm{DNA}$. The method adopted last class is ``prove by diagnalization''. Here, another method is used, that is to show that $\mathrm{HALT}\leq \mathrm{DNA}$.