Universal Turing Machine And Decidability

TM and Computable Functions

• Let a function $f:\Sigma^*\to \Sigma^*$ be a function over strings. We say that a Turing Machine $M$ implements the function if:

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

  1. Initialize the tape with $x$.

  2. If $f(x)$ is defined, then the TM $M$ will halt in an accepting state, and the final tape content must be exactly $f(y)$ followed by blanks.

• Decision problem:

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

• Computable functions:

  box

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

• Decidable functions:

  box

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

• An important theorem: the Church-Turing Thesis

  box

  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

• Given some algorithm $\mathcal{A}$, we can ask of its TM implementation $\mathbf{TM}(\mathcal{A})$.

  1. Each different algorithm will require its own TM.
  2. In order to have different algorithms, we will need to build infinitely many different TM each with its own distinct control logic.

• The profound genius of Alan Turing:

  box

  1. Simulation of TM is computable.

  2. Turing Machines can simulate Turing Machines.

• Let's define simulation

  • The input is a TM $M$, and the initial content of its tape.
  • The problem is "what is the final tape content"?

• Simulation is computable.

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

• $U = \mathbf{TM}(\mathbf{SIM})$ is called the universal Turing Machine.

Simluation and UTM

• UTM is the only TM we ever need to build.

  If we want to build a TM $M$. We can also encode its logic $\mathrm{logic}(M)$ and initializes the UTM tape with it.

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

• Whenever we need to execute $M$ on some input, we will need to add $\mathrm{input}(M)$ to the tape of $U$:

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

• Now, we can start executing the universal TM $U$. When it halts, it will produce the output of $M$ on its tape.

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

Programming and UTM

• Programming

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

• Compilation

  The control logic of $M$ needs to be encoded so that it can be placed on the tape of the universal TM. This is the process of compilation.

• Runtime execution

  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 Problems

• Remember how computation started?

  box

  Entscheidungsproblem

  If a problem can be described formally in mathematical logic, can it always be decided by mechanical reasoning?

• TM settles the entscheidungsproblem with a negative answer.

  box

  The Accepting Problem

  Given a TM $M$ and an initial content $x$ of its tape, will $M$ accept $x$?

  We defin the function:

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

• Undecidability of the Accepting Problem

  box

  Theorem:

  There does not exist a TM that implements the function $\mathbf{accept}$.

The proof

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

1. Let's consider $\mathbf{accept}$ be a program since by assumption it is computable.

2. We can construct another computable function:

   $$D(M) = \neg\mathbf{accept}(M, \mathrm{logic}(M))$$

3. Let's try to evaluate $D(D)$.

4. Does $D(D) = 0$ ?

   $$ \begin{eqnarray} && D(D) = 0 \\ &\Rightarrow& \mathbf{accept}(D, \mathrm{logic}(D)) = 1 \\ &\Rightarrow& D(D) = 1 \\ &\Rightarrow& \mathrm{contradition} \end{eqnarray} $$

5. Does $D(D) = 1$ ?

   $$ \begin{eqnarray} && D(D) = 1 \\ &\Rightarrow& \mathbf{accept}(D, \mathrm{logic}(D)) = 0 \\ &\Rightarrow& D(D) = 0 \\ &\Rightarrow& \mathrm{contradition} \end{eqnarray} $$

6. Conclusion:

   box

   The function $\mathbf{accept}(M, x)$ cannot possible be a program.