✓ Univesal Turing Machine And Computability¶

TM and Computable Functions¶

TM as functions over strings¶

Let a function $f: \Sigma^*\to\Sigma^*$ be a function over strings. A TM $M$ implements $f$ if:

Given a string $x\in\Sigma$*,

Initialize the tape with $x$ and execute $M$.
Whenever $f(x)$ is defined, $M$ will halt in an accepting state, and the final tape content is exactly $f(x)$, followed by blanks.

TM for decision problems¶

Let $f:\Sigma^*\to\{0, 1\}$, we call such function predicates because they only return true or false for any input.

Any TM $M$ that implements predicates will have either 0 or 1 on the tape at termination.

Computable functions¶

If a function $f$ has a TM implementation, then we call $f$ computable.

If a predicate $f$ is computable, we call $f$ decidable.

The Church-Turing Thesis¶

Church-Turing Thesis (1936-1938)

Modern day computers are equivalent to Turing Machine in the sense that:

Every computable function has an algorithm.
Every algorithm implements some computable function.

The Universal TM¶

Practical considerations¶

Given some algorithm $\mathcal{A}$, suppose it has a TM implementation $M(\mathcal{A})$ (with respect to some well-known encoding and decoding functions).

Each algorithm requires its own TM $M(\mathcal{A})$.
In order to implement different algorithms, do we need to build infinitely many physical machines, each with its own distinct control logic?

Alan Turing’s vision¶

Simulating TM is computable.
There is a TM that can simulate all TMs.

Simulation¶

Problem:

Given a TM $M$ specified by its control logic, and its initial tape content, if $M$ terminates, what is the final tape content?

Theorem

SIMULATION is computable.

The logic of any TM can be encoded into a string $x$.
There exists an algorithm $\mathbf{SIM}$ that can simulate the logic of $M$. Thus by Church-Turing thesis, we know there exists a TM $M(\mathbf{SIM})$ that implements the algorithm.

Universal TM

The TM that implements SIM is called the Universal Turing Machine:

\[U = M(\mathbf{SIM})\]

Applications of UTM¶

Using UTM for simulation¶

The UTM is the only TM we will ever need to build. To simulate any other TM, $M$, do the following:

First encode the logic $\mathrm{logic}(M)$ as a string, and initialize the UTM tape.

+----------+---------------------
| logic(M) | 
+----------+---------------------

Then write the input to the algorithm on the UTM tape.

+----------+----------+----------
| logic(M) | input(M) |
+----------+----------+----------

Execute UTM. When it halts, it will produce the output of $M$:

+-----------+---------------------
| output(M) | 
+-----------+---------------------

Programming¶

Coding

Given an algorithm $\mathcal{A}$, programming is producing the control logic of $M(\mathcal{A})$. This is the source code to be produced by the programmers.

Compilation

The control logic of $M(\mathcal{A})$ needs to be encoded so that it can be placed on the tape of the universal TM. This is the process of compilation.

Runtime

During the execution of the universal TM, the tape is divided to two regions $\mathrm{logic}(M)$ and $\mathrm{input}(M)$. This corresponds to:

Code memory region
Data memory region

Undecidable Problem¶

Entscheidungsproblem revisited¶

David Hilbert asked in 1928:

If a problem can be formally defined, it is always true that every instance of the problem be decided by mechanical reasoning?

Formal definition = Mathematical logic
Mechanical reasoning = Turing machine

Turing’s negative answer¶

Alan Turing showed in 1936 that it is possible to:

formally define a problem,
but there is no TM that can solve it all its instances.

The Accepting Problem

Given a TM $M$ and an initial content $x$ of its tape, will $M$ accept $x$? Namely, $M$ writes $1$ on the tape at termination.

The solution to the accepting problem requies us to implement the following function:

\[\begin{split} \mathbf{accept}(M, x) = \left\{ \begin{array}{ll} 1 & \textrm{if } M \textrm{ accepts input}\ x \\ 0 & \textrm{else} \end{array} \right. \end{split}\]

The undecidability of accept($M, x$)¶

Theorem

$\mathbf{accept}(M, x)$ cannot be implemented by any TM.

Proof

The proof is by contradition. Let assume that $\mathbf{accept}(M, x)$ is decidable, and show that it leads to a contradition.

(Hypothesis) Suppose that $M_\mathrm{accept}$ implements accept.
Then, we can define another function $D$ that is a predicate on TMs: $$D(M) = \neg\mathbf{accept}(M, \mathrm{logic}(M))$$
Since $\mathbf{accept}$ is decidable (by hypothesis), we can see that $D$ is also decidable, thus has a TM $M_D$.

Let’s try to evaluate $D(M_D)$.

Does $D(M_D) = 0$?

\[\begin{split}\begin{eqnarray*} && D(M_D) = 0 \\ &\implies& \mathrm{accept}(M_D, \mathrm{logic}(M_D)) = 1 \\ &\implies& M_D \textrm{ accepts } M_D \\ &\implies& D(M_D) = 1 \\ &\implies& contradition. \end{eqnarray*}\end{split}\]
Does $D(M_D) = 1$?

\[\begin{split}\begin{eqnarray*} && D(M_D) = 1 \\ &\implies& \mathrm{accept}(M_D, \mathrm{logic}(M_D)) = 0 \\ &\implies& M_D \textrm{ does not accepts } M_D \\ &\implies& D(M_D) = 0 \\ &\implies& contradition. \end{eqnarray*}\end{split}\]

Conclusion

$D(M_D)$ is not defined. Thus, it is not computable.
Therefore, $\mathbf{accept}$ cannot have a TM implementation, and thus not decidable.