Die folgende Turingmaschine berechnet die Summe zweier Zahlen in Binärdarstellung. Bei Eingabe von bin(x)#bin(y)$ und Start im Zustand q_{0} hält die Maschine im Zustand q_{F} mit der Ausgabe bin(x + y)#bin(y)$ und dem Kopf auf dem ersten Eingabesymbol. (Die Notation bin(x) ∈ {0, 1}^{∗} ist eine Darstellung von x ∈ ℕ in Binärdarstellung.) Der Bandinhalt rechts vom $-Zeichen bleibt dabei unverändert stehen.

Beginnend von rechts, wird jeweils das erste nicht markierte Bit von y und von x markiert. Wenn dieses Bit von y gleich 1 ist, wird es zur entsprechenden Stelle von x addiert, und gegebenenfalls ein Übertrag nach links weitergereicht. Ein B-Symbol am Anfang von x wird dabei wie eine 0 behandelt. Wenn alle Stellen von y markiert sind, werden alle Markierungen gelöscht, und der Automat hält.

δ  0  1  ¯0  ¯1  #  $  B  Kommentar
q_{0} (q_{0}, 0, R) (q_{0}, 1, R) (q_{0}, ¯0, R) (q_{0}, ¯1, R) (q_{0}, #, R) (q_{1}, $, L) −  fahre nach rechts
q_{1} (q_{2}, ¯0, L) (q_{4}, ¯1, L) (q_{1}, ¯0, L) (q_{1}, ¯1, L) (q_{7}, #, R) − − finde erstes nicht markiertes

Bit y_{0} von y und markiere es

q_{2} (q_{2}, 0, L) (q_{2}, 1, L) −  − (q_{3}, #, L) −  −  falls y_{0} = 0, finde erstes unmar-
q_{3} (q_{0}, ¯0, N) (q_{0}, ¯1, N) (q_{3}, ¯0, L) (q_{3}, ¯1, L)  −  − (q_{0}, ¯0, N) kiertes Bit von x, markiere es.
q_{4} (q_{4}, 0, L) (q_{4}, 1, L) −  − (q_{5}, #, L) −  −  falls y_{0} = 1, finde erstes Bit
q_{5} (q_{0}, ¯1, N) (q_{6}, ¯0, L) (q_{5}, ¯0, L) (q_{5}, ¯1, L)  −  − (q_{0}, ¯1, N) von x, markiere es, addiere 1,
q_{6} (q_{0}, 1, N) (q_{6}, 0, L) −  −  −  − (q_{0}, 1, N) gegebenenfalls Übertrag
q_{7}  −  − (q_{7}, ¯0, R) (q_{7}, ¯1, R)  −  (q_{8}, $, L) −  Ende, fahre ganz nach rechts
q_{8} (q_{8}, 0, L) (q_{8}, 1, L) (q_{8}, 0, L) (q_{8}, 1, L) (q_{8}, #, L) − (q_{F} , B, R) nach links, lösche Markierungen

q_{0}101#11$ ⊢ 1q_{0}01#11$ ⊢ 10q_{0}1#11$ ⊢ 101q_{0}#11$ ⊢ 101#q_{0}11$ ⊢ 101#1q_{0}1$
⊢ 101#11q_{0}$ ⊢ 101#1q_{1}1$ ⊢ 101#q_{4}1¯1$ ⊢ 101q_{4}#1¯1$ ⊢ 10q_{5}1#1¯1$ ⊢ 1q_{6}0¯0#1¯1$
⊢ 1q_{0}0¯0#1¯1$ ⊢ 11q_{0}¯0#1¯1$ ⊢ 11¯0q_{0}#1¯1$ ⊢ 11¯0#q_{0}1¯1$ ⊢ 11¯0#1q_{0}¯1$ ⊢ · · · ⊢
10¯0¯0#¯1¯1q_{0}$ ⊢ 10¯0¯0#¯1q_{1}¯1$ ⊢ 10¯0¯0#q_{1}¯1¯1$ ⊢ 10¯0¯0q_{1}#¯1¯1$ ⊢ 10¯0¯0#q_{7}¯1¯1$ ⊢ 10¯0¯0#¯1q_{7}¯1$
⊢ 10¯0¯0#¯1¯1q_{7}$ ⊢ 10¯0¯0#¯1q_{8}¯1$ ⊢ 10¯0¯0#q_{8}¯11$ ⊢ 10¯0¯0q_{8}#11$ ⊢ 10¯0q_{8}¯0#11$ ⊢ 10q_{8}¯00#11$
⊢ 1q_{8}000#11$ ⊢ q_{8}1000#11$ ⊢ q_{8}B1000#11$ ⊢ q_{F}1000#11$.