Universal Turing machine


$ M\in U\mathrm{TM} $
$ M\subset\mathrm{TM}_2$
$ x,\alpha $ … bit string
$ M_\alpha $ … Turing machine
$ \forall M'.\ \exists\alpha.\ \forall x.\ M[x,\alpha]=M_\alpha[x] $


Turing showed that there indeed exist such universal Turing machines which are capable of running any other Turing machine $M$ when given in machine code format: We ecode the original Turing machine $M_\alpha$ into a string $\alpha$ itself, i.e. $\triangleright\ \alpha\ \Box\ \Box\ \dots$, where $\mathrm{\alpha}$ is the so called “machine code” of the machine $M_\alpha$. Now have another machine $M$ (designed for taking other Turing machines as additional input and copy what they would do) and simulate the machine code together with some normal input for $\mathrm{\alpha}$. Without going into detail, the idea is the following. Remember that a general transition function is of the type:

$ \delta: Q\times\Gamma^k \to Q \times \Gamma^k \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^k$

Consider a transition function $\delta$ for a Turing machine $M$ we want to simulate:

$ \delta: Q\times\Gamma \to Q \times \Gamma \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}$

The art in designing the universal Turing machine $M'$ (and in particular $\delta'$, which by construction has access to $Q$ and $\delta$) in terms of $M$. One key is to story $Q$ and $\delta$ of $M$ on $M'$'s tapes $\Gamma_Q, \Gamma_\delta$. Roughly

“$ \delta': Q'\times\Gamma \times \Gamma_Q \times \Gamma_\delta \to Q' \times \Gamma \times \Gamma_Q \times \Gamma_\delta \times \{\mathrm{L},\mathrm{S},\mathrm{R}\}^3$”

After this 3-tape Turing machine is constructed we can concert is to a 1-tape Turing machine, if necessary.

Such a universal machine can be physically realized via hardware (like a PC, designed for executing $\delta$ with 3 Gigahertz) and the machine code might then come from a computer program written by a 6 year old fat girl from Ohio. This video is from a nerd who wanted to build himself a hands on realization of a universal Turing machine.


The described process changes the runtime only as $\mathcal O\left(T(n)\right)\to \mathcal O\left(\lceil\log T(n)\rceil\cdot T(n)\right)$.


Subset of

Link to graph
Log In
Improvements of the human condition