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 poč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

Turingov stroj rozpoznáva triedu rekurzívne vyčísliteľných jazykov. Deterministická a nedeterministická verzia turingovho stroja sú čo do rozpoznávacej sily zhodné.