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.

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, 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