Turingov stroj
Z Wikipédie
Turingov stroj (TS) je jeden z najdôležitejších modelov na popis 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 začiatočný stav
- F je množina koncových stavov
Existuje viacero variantov turingovho stroja, napríklad:
- Deterministický TS
- Nedeterministický TS
- Alternujúci TS (paralelne pracujúci)
- k-páskový TS
