Unser Bandalphabet soll B = {a,b,z} sein, und anfangs steht auf dem Band die Angabe "x - y" in folgender Form: x-mal das Zeichen a, mindestens ein Trennzeichen b, y-mal das Zeichen a; rechts und links davon stehen beliebig viele Leerzeichen z (tatsächlich genügt hier jeweils eines davon).
Die Maschine nutzt aus, daß gilt:
x - y = x falls y = 0Die Zustände haben folgende Bedeutung:
x - y = (x-1) - (y-1) sonst
q0 = nimm ein Zeichen a von x weg (bilde x-1)Als "Programm" haben wir die Tafel
q1 = laufe nach rechts bis zur Trennung b
q2 = laufe nach rechts bis y und nimm dort ein a weg (bilde y-1)
q3 = prüfe, ob jetzt y=0 ist
q4 = laufe nach links bis an den Anfang von x
q5 = ebenso, aber lösche alle b
q6 = fertig!
| a | b | z | |
| q0 | q1 z R | ||
| q1 | q1 a R | q2 b R | |
| q2 | q3 b R | q2 b R | |
| q3 | q4 a L | q5 z L | |
| q4 | q4 a L | q4 b L | q0 z R |
| q5 | q5 a L | q5 z L | q6 z R |
| q6 | q0 a H |