Mir war langweilig, darum habe ich das ganze mal eben als Bandmaschine mit dazugehörigem Simulator in Delphi implementiert.
Die Bandmaschine ist die Maschine M=({0,1,...,11}, {0, 1}, {0, 1, B}, σ, 0,
EC, AC), wobei
EC: Z->Σ* und AC: Σ*->Z die Eingabe-/Ausgabekodierungen sind, die aus einer ganzen Zahl Z ihre binäre Repräsentierung als Wort erstellen bzw. umgekehrt.
σ ist dabei wie folgt definiert:
σ(1)=(R, 2)
σ(2)=(B, 3, 1)
σ(3)=(L, 4)
σ(4)=(0?, 3, 5)
σ(5)=(L, 6)
σ(6)=(1?, 7, 8)
σ(7)=(0, 10)
σ(8)=(0?, 9, 11)
σ(9)=(1, 10)
σ(10)=(L, 6)
σ(11)=HALT
(L ist eine Linksbewegung des Kopfes, R eine Rechtsbewegung. Ein Symbol steht für das Schreiben des Symbols, ein Symbol mit einem Fragezeichen für einen Vergleich des Symbols mit dem unter dem Lesekopf. Die Zahlen danach stehen für den Folgezustand bzw. bei einem Vergleich den Folgezustand, wenn er zutrifft und wenn er es nicht tut)
Die Negation ist dann die Funktion fM: Z->Z, die durch die Ausführung von M entsteht.
Delphi-Implementierung im Anhang.