Universelle Turing-Maschine

Eine Universelle Turing-Maschine $M^U$ ist eine Turing-Maschine, die als Eingabe die Kodierung einer beliebigen Turing-Maschine $M_w$ und eine Eingabe $x$ erhält. $M^U$ simuliert das Verhalten von $M_w$ auf $x$.
Zeitkomplexität: Wenn $M_w$ in $t$ Schritten hält, hält $M^U$ in $O(t\cdot \log t)$ Schritten.