Namespaces
Variants
Actions

Universal Turing machine

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

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

[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
How to Cite This Entry:
Universal Turing machine. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Universal_Turing_machine&oldid=30057