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 ${\displaystyle M=(Q,\Sigma ,\Gamma ,\triangleright ,\Box \!\,,\delta ,q_{0},q_{accept},q_{reject})}$ nazývame Turingov stroj, kde význam symbolov je:

• ${\displaystyle Q}$ je konečná množina stavov,
• ${\displaystyle \Sigma }$ je vstupná abeceda
• ${\displaystyle \Gamma }$ je pásková abeceda, obsahujúca ako svoju podmnožinu abecedu ${\displaystyle \Sigma }$
• ${\displaystyle \delta }$ je prechodová funkcia,
• ${\displaystyle q_{0}}$ je počiatočný stav
• ${\displaystyle \triangleright \in \Gamma \setminus \Sigma }$ je ľavá koncová značka
• ${\displaystyle \Box \in \Gamma \setminus \Sigma }$ je symbol označujúci prázdne políčko
• ${\displaystyle q_{accept}}$ je akceptujúci stav
• ${\displaystyle q_{reject}}$ 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, automaty a gramatiky
Chomského hierarchia	Gramatika	Jazyk	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.