Die universelle Turingmaschine kann jede beliebige Ein-Band Turingmaschine mit dem Alphabet A={0,1,#} simulieren. Das Alphabet der universellen Turingmaschine enthält neben den Symbolen der zu simulierenden TM zusätzlich die Pfeilsymbole:

Die zu simulierende TM muss vollständig (alle Übergänge und die Ausgangslage) in die Welt der universellen TM codiert werden. Diese Codierung soll am Beispiel des einfachen Inverters erklärt werden (Bilder 1 und 2).


Bild 1: Zustandsdiagram des Inverters


Bild 2: Ausgangslage in der Welt

Bild 3 zeigt die allgemeine Definition eines Übergangs der zu simulierenden TM. Das Blank ("_") ist dabei nicht als "dont-care" zu verstehen, sondern entspricht dem leeren Feld, welches wie ein normales Symbol gelesen und geschrieben werden kann.


Bild 3: allgemeine Definition eines Übergangs

Um einen Übergang mit Hilfe des Alphabets der universellen Turingmaschine in der Welt darstellen zu können, müssen zuerst die Zustände und die Bewegungen codiert werden. Dazu werden die Zustände nummeriert und erhalten als Codierung die Binärdarstellung ihres Indizes zugewiesen. Sämtliche Codierungen müssen gleich lang sein, deshalb werden falls nötig die höheren Stellen mit Nullen aufgefüllt. Die Bewegungen werden mit Hilfe der Pfeilsymbole und des Blanks codiert. Ein Übergang wird wie folgt in die Welt der universellen Turingmaschine geschrieben:

Beispiel:


Bild 4: Codierung des ersten Übergangs des Invertierers


Bild 5: Die gesamte Welt der universellen Turingmaschine vor der Ausführung.