Turingov stroj

Turingov stroj (TS) je jeden z najdôležitejších modelov na opis formálnych jazykov.

Stroj dostane na vstup zapísané vstupné slovo na páske, hlava stojí nad prvým políčkom. Páska je dostatočne dlhá (hovorí sa že je nekonečne dlhá). Stroj sa nachádza v počiatočnom stave. Podľa prechodovej funkcie pracuje na vstupnom slove, pričom jednotlivé symboly môže aj prepisovať. Stroj akceptuje slovo, ak sa dostane do akceptujúceho stavu.

Usporiadanú 9-ticu  nazývame Turingov stroj, kde význam symbolov je:
  je konečná množina stavov,
  je vstupná abeceda
  je pásková abeceda, obsahujúca ako svoju podmnožinu abecedu 
  je prechodová funkcia,
  je počiatočný stav
  je ľavá koncová značka
  je symbol označujúci prázdne políčko
  je akceptujúci stav
  je zamietajúci stav

Modifikácie Turingových strojov
 Turingov stroj s 1-smerne nekonečnou páskou.
 m-páskové Turingové stroje.
 Turingové stroje s read-only (R/O) vstupnou páskou a 2 zásobníkmi.
 Počítadlové Turingové stroje.

Existuje viacero variantov Turingovho stroja, napríklad:
 Deterministický TS
 Nedeterministický TS
 Alternujúci TS (paralelne pracujúci)
 k-páskový TS

Turingov stroj rozpoznáva triedu rekurzívne vyčísliteľných jazykov.

Formálne jazyky
Teória automatov
Vyčísliteľnosť
Eponymické termíny
Alan Turing