Die Kodierung einer Turingmaschine M = (Q, Σ, Γ, δ, □, z₀, S) kann erreicht werden, indem das Tupel M = (Q, Σ, Γ, δ, □, z₀, S) und die Tabelle, die die Überführungsfunktion δ definiert, kodiert werden. Dadurch entsteht der Code(M), der eine Zeichenkette aus {0, 1}* ist. Um den Anfang eines Codes vom Ende aus erkennen zu können, könnte man beispielsweise zwei Nullen am Anfang platzieren und dann sicherstellen, dass nie wieder zwei Nullen hintereinander auftreten. Das bedeutet entweder keine Null an ungeraden Positionen oder keine Null an geraden Positionen, je nach Länge des Codes. Eine mögliche Regel könnte sein:
\( \operatorname{Code}(M) \in \bigcup_{n \geq 1}\left\{00 c_{1} \ldots c_{n} \mid\left(\forall i<\frac{n}{2}\right)\left(c_{n-2 i}=1\right)\right\} \)
Alle Symbole, die in die formale Definition einer Turingmaschine einfließen, sowie die Trennsymbole in der Tabelle können durch gleich lange Wörter kodiert werden. Diese Wörter werden gemäß eines festgelegten Systems hintereinander gesetzt. Dadurch kann die Frage, ob eine gegebene Zeichenkette aus Nullen und Einsen der Code einer Maschine ist, durch eine einzige Turingmaschine entschieden werden.
Hey, könnte mir jemand bitte ein Beispiel dazu geben, damit ich es gut verstehen kann? :)
