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 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 stavu z množiny koncových stavov.
Usporiadanú šesticu 
nazývame Turingov stroj, kde význam symbolov je:
je množina stavov,
je vstupná abeceda
je pásková abeceda
je prechodová funkcia,
je počiatočný stav
je množina koncových stavov
je množina stavov,
je vstupná abeceda
je pásková abeceda
je prechodová funkcia,
je 
je množina koncových stavovčítajte viac o Turingov stroj