Turingovy stroje: Definice
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
Matematická poznámka:
3/45