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. The simulation is realized by using an appropriate transition function. The universality 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.

Universality of Turing Machines

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}$$ 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\circ s) =F_T(s)$. The Turing machine $U$ is called universal, if it can simulate every Turing machine $T$.

Existence of a universal Turing Machine

Via Gödelization it can be proven that a universal Turing machine exists. The basic idea is as follows: The components of $T$ are coded in $\Sigma^\ast$ giving a Gödel number $g(T)$ (W.r.o.g we assume here that $\Sigma\subset^{\text{fin}}\mathbb{N}$. Furthermore remember, that $\delta$ can be represented as a table). The same strategy is used to code 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)}=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ 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 on $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$
• Update $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)\circ 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 general-purpose property, i.e. the adaptability to all algorithmical problem-solving tasks by using a corresponding program as input.

On the other hand, universality means a strong limitation as well. It exist uncountable many 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