Turingov stroj

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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

Existuje viacero variantov Turingovho stroja, napríklad:

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.