Die Kantenkennzeichnung ist ein Tripel aus (anstehendem Zeichen, geschriebenem Zeichen, Bandbewegung).
Eine Turingmaschine mit dieser Übergangsfunktion erkennt die Sprache {aibiai}.
Idee dabei: Die Maschine läuft i-Mal über die Eingabe und ersetzt dabei jeweils genau ein linkes a (im Zustand SA), ein b (im Zustand (SB) und ein rechtes a (im Zustand SA2), durch Hilfssymbole; Hilfssymbole werden jeweils überlesen. Dann spult die Maschine im Zustand LL zurück, nachdem sie in SA3 das rechte Ende gefunden hat.
Wenn alles nur noch aus Hilfssymbolen besteht, läuft SA durch und erreicht das Ende des Bands – die Maschine landet in OK, sonst “stürzt sie ab”.
Den Zustand einer Turingmaschine stellen wir dar als ein Wort k∈Σ*∙Φ ∙Σ*, so dass links und rechts der Bandinhalt links und rechts vom Kopf steht und in der Mitte der augenblickliche Zustand.
Wir leiten aabbaa ab:
| S | #aabbaa# | → | # | SA | aabbaa# | → | ||
| #* | SB | abbaa# | → | # *a | SB | bbaa# | → | |
| # *a△ | SA2 | baa# | → | # *a△b | SA2 | aa# | → | |
| # *a△b⊥ | SA3 | a# | → | # *a△b⊥a | SA3 | # | → | |
| # *a△b⊥ | LL | a# | → | # *a△b | LL | ⊥a# | → | |
| # *a△ | LL | b⊥a# | → | # *a | LL | △b⊥a# | → | |
| #* | LL | a△b⊥a# | → | # | LL | *a△b⊥a# | → | |
| #* | SA | a△b⊥a# | → | # ** | SB | △b⊥a# | → | |
| # **△ | SB | b⊥a# | → | # **△△ | SA2 | ⊥a# | → | |
| # **△△⊥ | SA2 | a# | → | # **△△⊥⊥ | SA3 | # | → | |
| # **△△⊥ | LL | ⊥# | → | # **△△ | LL | ⊥⊥# | → | |
| # **△ | LL | △⊥⊥# | → | # ** | LL | △△⊥⊥# | → | |
| #* | LL | *△△⊥⊥# | → | # | SA | **△△⊥⊥# | → | |
| #* | SA | *△△⊥⊥# | → | # ** | SA | △△⊥⊥# | → | |
| # **△ | SA | △⊥⊥# | → | # **△△ | SA | ⊥⊥# | → | |
| # **△△⊥ | SA | ⊥# | → | # **△△⊥⊥ | SA | # | → | |
| # * *△△⊥⊥ | OK | # |