✓ 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:

  1. Every computable function has an algorithm.

  2. 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

  1. Simulating TM is computable.

  2. There is a TM that can simulate all TMs.



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


SIMULATION is computable.

  1. The logic of any TM can be encoded into a string \(x\).

  2. 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:

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

| logic(M) | 
  1. Then write the input to the algorithm on the UTM tape.

| logic(M) | input(M) |
  1. Execute UTM. When it halts, it will produce the output of \(M\):

| output(M) | 



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.


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.


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

  1. Code memory region

  2. 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\))


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


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

  1. (Hypothesis) Suppose that \(M_\mathrm{accept}\) implements accept.

  2. Then, we can define another function \(D\) that is a predicate on TMs: $\(D(M) = \neg\mathbf{accept}(M, \mathrm{logic}(M))\)$

  3. 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}\]


  • \(D(M_D)\) is not defined. Thus, it is not computable.

  • Therefore, \(\mathbf{accept}\) cannot have a TM implementation, and thus not decidable.