View source for Universal Turing machine

{{MSC|68Q05}}

{{TEX|done}}

The universality property of Turing machines states that there exists a Turing machine, which can simulate the behaviour of any other Turing machine. This property is of great practical importance. It says that a Turing machine can be adapted to different tasks by ''programming''; from the viewpoint of computability it is not necessary to build special-purpose machines.

===Definition of Universality===

A [[Turing machine]] $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function
$$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto
\begin{cases} j &
\text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\
\bot & \text{otherwise} \end{cases}$$
The definition can be generalized to multiple arguments in a canonical way. Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ ''simulates'' a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t, s) =F_T(s)$. The Turing machine $U$ is called ''universal'', if it can simulate every Turing machine $T$.

===Existence of an Universal Turing Machine===

Via [[Gödelization]] it can be proven that a universal Turing machine $U$ exists. For reasons of simplicity we will assume that $U$ uses the same input/output- and band alphabet as the machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ to be simulated. The basic idea is for realizing $U$ is as follows: The components of $T$ are codified in $\Sigma^\ast$ giving a Gödel number $g(T)$ (W.r.o.g we assume here that the input alphatbet $\Sigma\subset^{\text{fin}}\mathbb{N}$ of $U$ is a finite subset .  Furthermore remember, that $\delta$ can be represented as a table).  The same strategy is used to codify configurations (of $T$) and computations steps (of $T$) in the alphabet $\Sigma$. 

We will designate the Turing machine $T$ with Gödel number $g(T)$ as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate $M_{g(T)}$ using its Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the machine $U$ translates $s$ to the corresponding start configuration $c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of $M_{g(T)}$ by looping over the following operation sequence 
* Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$ 
* Identify the transition operation to be applied to $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$ 
* Update the old configuration $c$ to the new configuration $c'$ using the identified transition operation 
* Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.  
Invalid Gödel numbers are assigned to a Turing machine looping for all inputs.  In effect, this gives $ U(g(T),s) = M_{g(T)}(s) $ for all $s\in\Sigma^\ast$.

===Interpretation of Universality===

The universality property shows that Turing machines are quite powerful instruments. A Turing machine equipped with a suitable transition function $\delta$ can simulate each other Turing machine. For the other members of the Chomsky-hierarchy this closure property does not hold. Universality has far-reaching consequences for practice. It assures the usability for general purposes, i.e. the adaptability to all possible computable tasks by using a corresponding ''program'' as input.

On the other hand, universality is a strong limitation as well. It exist an uncountable number of functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$, but for a universal machine only a countable subset of them is computable.  This is caused by the necessary usage of a [[Gödelization]].

===References===

{|
|-
|valign="top"|{{Ref|H77}}||valign="top"| F. Hennie, "Introduction to Computability", Addison-Wesley 1977
|-
|valign="top"|{{Ref|HU79}}||valign="top"| J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
|-
|valign="top"|{{Ref|P81}}||valign="top"| C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981
|-
|}