Turingov stroj
z Wikipédie, slobodnej encyklopédie
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,Σ,Γ,δ,q0,F) nazývame Turingov stroj, kde význam symbolov je:
- K je množina stavov,
- Σ je vstupná abeceda
- Γ je pásková abeceda
- δ je prechodová funkcia,
- q0 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é Turongové stroje.
- Turongove stroje s read-only (R/O) vstupnou páskou a 2 zásobníkmi.
- Počítadlové Turongové 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.
