===== Universal Turing machine =====
==== Set ====
| @#FFBB00: $ M\in U\mathrm{TM} $ |

| @#AAFFAA: $ M\subset\mathrm{TM}_2$ |

| @#DDDDDD: $ x,\alpha $ ... bit string |
| @#DDDDDD: $ M_\alpha $ ... Turing machine |

| @#55EE55: $ \forall M'.\ \exists\alpha.\ \forall x.\ M[x,\alpha]=M_\alpha[x] $ |

==== Discussion ====
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. [[http://www.youtube.com/watch?v=E3keLeMwfHY|This video]] is from a nerd who wanted to build himself a hands on realization of a universal Turing machine.

=== Theorems ===
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)$. 

==== Parents ====
=== Subset of ===
[[k-tape Turing machine]]