Hier die Beschreibung einer Maschine, die Palindrome erkennt (d.h. die Sprache der Palindrome entscheidet.). 

Eingabealphabet Gamma = {0,1}
Arbeitsalphabet Sigma = {0,1,#}
Zustandsmenge Q = {qi,q1,q2,q3,qa,qr}
Baenderanzahl k=2
Maschinentafel = {
(qi, (b,b), (S,S), (#,#), qa) /* Leere Eingabe wird akzeptiert */
(qi, (0,b), (S,R), (0,#), q1)
(qi, (1,b), (S,R), (1,#), q1) /* Auf dem Arbeitsband ein # schreiben, 
				 Arbeitskopf eins nach rechts */
(q1, (0,b), (R,R), (0,0), q1)
(q1, (1,b), (R,R), (1,1), q1) /* 0en und 1en auf Eingabeband auf Arbeitsband
				 kopieren (aber rechts vom bereits 
				 geschriebenen #-Symbol) */ 
(q1, (b,b), (L,L), (#,#), q2) /* Wird ein b erreicht, in q2 uebergehen und 
				 auf das letzte nicht-b-Zeichen
				  zurueckfahren. */
(q2, (0,0), (S,R), (0,0), q2)
(q2, (0,1), (S,R), (0,1), q2)
(q2, (1,0), (S,R), (1,0), q2)
(q2, (1,1), (S,R), (1,1), q2)
(q2, (0,#), (S,L), (0,#), q3)
(q2, (1,#), (S,L), (1,#), q3) /* Zurueckfahren des Arbeitskopfes auf das 
				 erste Symbol nach dem # */
(q3, (0,0), (L,R), (#,#), q3)
(q3, (1,1), (L,R), (#,#), q3)
(q3, (0,1), (S,S), (#,#), qr)
(q3, (1,0), (S,S), (#,#), qr)
(q3, (0,#), (S,S), (#,#), qa)
(q3, (1,#), (S,S), (#,#), qa) /* Vergleichen des i-ten Eingabesymbols 
				 mit dem n-i-1-ten Arbeitssymbol, von i=0..n-1.
				 Akzeptiert, falls limitierendes # auf 
				 Arbeitsband erreicht. Zurueckgewiesen, falls 
				 Nichtuebereinstimmung. */
}



Bei Eingabewort 0011000 ist die Startkonfiguration 
("0011000", "", qi, (0,0)) in der Form 
(Bandbeschriftung1, Bandbeschriftung2, Zustand, Kopfpositionen). 

Wir gelangen mit einem Uebergang in die Konfiguration
("0011000", "#", q1, (0,1))

Nach weiteren acht Uebergaengen gelangen wir zu
("0011000#", "#0011000#", q2, (6,7))

Nach dem Zurueckfahren des Arbeitskopfes erreichen wir
("0011000#", "#0011000#", q3, (6,1))

und jetzt geht's richtig los: 

-> ("0011000#", "#0011000#", q3, (5,2)) -> ("0011000#", "#0011000#", q3, (4,3))
-> ("0011#00#", "#00#1000#", qr, (4,3)). Also wird das Wort zurueckgewiesen.