Turingov stroj
From Wikipedia, the free encyclopedia
Remove ads
Turingov stroj (TS) je jeden z najdôležitejších modelov na opis formálnych jazykov.
Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje. |
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 nazývame Turingov stroj, kde význam symbolov je:
- je konečná množina stavov,
- je vstupná abeceda
- je pásková abeceda, obsahujúca ako svoju podmnožinu abecedu
- je prechodová funkcia,
- je počiatočný stav
- je ľavá koncová značka
- je symbol označujúci prázdne políčko
- je akceptujúci stav
- 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.
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads