User:Joachim Draeger/sandbox

2020 Mathematics Subject Classification: Primary: 68Q05 [MSN][ZBL]

The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each 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

[H77]	F. Hennie, "Introduction to Computability", Addison-Wesley 1977
[HU79]	J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
[P81]	C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981