Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Tu je niekoľko príkladov Turingu rozpoznateľných jazykov, ktoré sú v kontraste s inými jazykovými triedami:
Príklady Turing-rozpoznateľných jazykov:
* Jazyk všetkých strojov Turing, ktoré sa zastavili na prázdnom reťazci: Môžeme postaviť Turingov stroj, ktorý simuluje daný Turingový stroj na prázdnom reťazci. Ak simulovaný stroj zastaví, náš stroj akceptuje. Ak sa to navždy dostane, náš stroj navždy slučí. Toto je rozpoznateľne; Neexistuje spôsob, ako definitívne povedať, že stroj * sa nezastaví.
* Jazyk všetkých skutočných tvrdení v aritmetike prvého poriadku: Gödelova veta úplnosti ukazuje, že je možné dokázať všetky skutočné vyhlásenie. Turingový stroj môže systematicky vymenovať všetky možné dôkazy a ak sa nájdu dôkaz, akceptuje vyhlásenie. Ak je však vyhlásenie nepravdivé, stroj sa nikdy nezastavuje.
* Jazyk všetkých gramatických gramatík, ktoré generujú aspoň jeden reťazec dĺžky 10: Turingový stroj môže systematicky generovať všetky reťazce daného CFG a skontrolovať ich dĺžku. Ak nájde jednu z dĺžky 10, prijíma to. Ak CFG nevygeneruje žiadny taký reťazec, stroj by sa mohol bežať na neurčito a snažiť sa ho nájsť.
* Jazyk všetkých párov Turingov strojov (M1, M2) tak, že M1 sa zastavuje, keď sa dá kód M2 ako vstup: To ilustruje zložitosť. Môžeme postaviť stroj, ktorý simuluje M1 na kódovaní M2. Ak sa M1 zastaví, náš stroj prijíma. V opačnom prípade je slučky. To zdôrazňuje nerešpektovanie, ktorá je spojená s mnohými problémami, ktoré sú rozpoznateľné.
Ako sa líšia od iných typov jazykov:
Kľúčový rozdiel spočíva v správaní zastavenia:
* Turing dedectable (rekurzívne) jazyky: Toto sú jazyky, pre ktoré existuje Turingov stroj, ktorý sa vždy zastaví a správne rozhoduje, či je daný vstupný reťazec v jazyku alebo nie. Každý reťazec dostane definitívnu odpoveď „áno“ alebo „nie“. Príklady zahŕňajú bežné jazyky, jazyky bez kontextov (s niektorými obmedzeniami) a mnoho ďalších, o ktorých sa môžu rozhodnúť algoritmami so zaručeným ukončením.
* Turing-uznávateľné (rekurzívne vymeniteľné) jazyky: Ako je uvedené vyššie, tieto jazyky sú rozpoznávané Turingovými strojmi, ktoré sa môžu navždy opakovať na reťazcoch, ktoré nie sú v jazyku. Sú to * superset * z dedecovateľných jazykov; Každý rozhodujúci jazyk je tiež rozpoznateľný.
* Neuznávacie jazyky: Tieto jazyky nemožno rozpoznať ani Turingovcom strojom. Neexistuje žiadny algoritmus, hoci neefektívny, ktorý dokáže správne identifikovať všetky reťazce v jazyku. Príkladom je doplnok problému zastavenia (jazyk všetkých strojov Turing, ktoré * nezastavia na prázdnom reťazci).
Súhrn:
| Jazyková trieda Zastavovacie správanie Príklad |
|-------------------------|----------------------------------------------------|------------------------------------------------------------------------|
| Turing dedectable | Vždy sa zastaví, správne rozhoduje o členstve Pravidelné jazyky, jazyky bez kontextu (s obmedzeniami)
| Turing uznávateľný Zastavuje a prijíma reťazce v jazyku, môže inak slučka | Jazyk strojov Turing, ktoré sa zastavili na prázdnom reťazci
| Neuznávaná uznávaná | Žiadny Turingov stroj to nedokáže rozpoznať Doplnok problému s zastavením
Hierarchia je:Turing dec. Zahrnutie je prísne; Existujú rozpoznateľné jazyky, ktoré nie sú rozhodné. A existuje veľa jazykov, ktoré sú mimo rozpoznateľných jazykov.