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 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 $A (K, \Sigma, \Gamma, \delta, q_0, F)$ nazývame Turingov stroj, kde význam symbolov je:

• $K$ je množina stavov,
• $\Sigma$ je vstupná abeceda
• $\Gamma$ je pásková abeceda
• $\delta$ je prechodová funkcia,
• $q_0$ je počiatočný stav
• $F$ je množina koncových stavov

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, automaty a gramatiky
Chomského hierarchia	Gramatiky	Jazyky	Minimálny automat
Typ-0	Frázová	Rekurzívne vyčísliteľný	Turingov stroj
		Rekurzívny	Vždy zastavujúci Turingov stroj
Typ-1	Kontextová	Kontextový	(Nedeterministický) lineárne ohraničený
Typ-2	Bezkontextová	Bezkontextový	(Nedeterministický) zásobníkový
Typ-3	Regulárna	Regulárny	Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.