Definice: Turingův stroj (TS) je šestice
M = (Q, S, G, R, s, F),
kde
• Q je konečná množina stavů
• S je vstupní
abeceda
• G je pásková
abeceda; D
Î
G; S Í G
• R je konečná množina pravidel tvaru: pa ® qbt,
kde p, q Î Q, a, b Î G, t Î {S, R, L}
• s Î Q je počáteční stav
• F Í Q je množina koncových stavů
• Čistě matematicky, R
je relace z Q ´ G do Q
´ G´ {S, R, L}
• Místo relačního zápisu
(pa, qbt) Î
R zapisujeme pa ® qbt
Î R