Aké sú príklady neurčiacich rozpoznateľných jazykov a ako sa líšia od Turingových jazykov?

Dobre, preskúmajme ríšu neradných rozpoznateľných jazykov a to, ako sa líšia od Turingu, uznávaných (rekurzívne vymenovaných) a odškodnených (rekurzívnych) jazykov. Je to krajina toho, čo počítače * nemôžu robiť, a je to celkom zaujímavé!

Pochopenie krajiny ako prvé

Predtým, ako sa ponoríte do príkladov, objastme kategórie:

* Turing dedectable (rekurzívne) jazyky: Toto sú jazyky, pre ktoré môže Turingov stroj * vždy * zastaviť a správne odpovedať „áno“ (akceptujte), ak je vstupný reťazec v jazyku alebo „nie“ (odmietnuť), ak vstupný reťazec nie je v jazyku. Turingov stroj vždy poskytuje definitívnu odpoveď.

* Turing-uznávateľné (rekurzívne vymeniteľné) jazyky: Toto sú jazyky, pre ktoré Turingov stroj zastaví a akceptuje, ak je vstupný reťazec * v jazyku *. Ak však vstupný reťazec nie je * v jazyku *, Turingov stroj by mohol buď zastaviť a odmietnuť, alebo by mohol bežať navždy (slučka). Kľúčom je, že to * nakoniec * hovorí „áno“ pre reťazce v jazyku.

* Neuznávacie rozpoznateľné (nerekurzívne vymenované) jazyky: Toto sú jazyky, pre ktoré * Žiadny * Turing stroj môže byť navrhnutý tak, aby spoľahlivo rozpoznával reťazce v jazyku. Bez ohľadu na to, aký šikovný ste, nemôžete zostaviť Turingov stroj, ktorý prijme všetky reťazce v jazyku (a potenciálne sa zastaví, keď to tak nie je). Doplnok Turingu rozpoznateľného jazyka je nerozoznateľný.

Príklady neurčených rozpoznateľných jazykov

Najbežnejšie príklady nevyužiteľných rozpoznateľných jazykov často zahŕňajú doplnky známych nerozhodnuteľných problémov.

1. Doplnok problému s zastavením (¬halt):

* Problém s zastavením (Halt): Toto je jazyk obsahujúci všetky kódovanie Turingovho stroja `⟨m, w⟩`, kde Turing Machine` M` sa zastaví na vstupnom reťazci `w`. (Je to rozpoznateľné, ale * nie * dedecovateľné).

* ¬halt: Toto je jazyk obsahujúci všetky kódovanie Turingovho počítača `⟨m, w⟩`, kde Turing Machine` M` nezastavuje na vstupnom reťazci `w`.

* Prečo je to neurčiteľné rozpoznateľné: Keby ¬halt boli rozpoznateľné, potom by bol zastavený dec. Ale Halt je * osvedčený * nerečovateľný. Pretože Halt je rozpoznateľná, ale nie je demontovateľná, jeho doplnok, ¬halt, musí byť rozpoznateľný. Keby bol zastavenie rozhodovateľný, potom by to bolo rozpoznateľné.

2. ):

* Problém s akceptáciou (a _{tm ):} Toto je jazyk obsahujúci všetky kódovanie Turing Machine `⟨m, w⟩`, kde Turing Machine` M` prijíma vstupný reťazec `w`. (Je to rozpoznateľné, ale nie je demontovateľné).

* ¬a tm : Toto je jazyk obsahujúci všetky kódovanie Turingovho počítača `⟨m, w⟩`, kde Turing Machine` M` * neakceptuje vstupný reťazec `w`. `M` môže odmietnuť alebo slučku.

* Prečo je to neurčiteľné rozpoznateľné: Podobné zdôvodnenie ako pri ¬halte. Ak ¬a _{tm boli rozpoznateľné, potom tm by bolo dedecovateľné, čo by bolo v rozpore so známym nerealizovateľnosťou TM .}

3. ):

* Problém s prázdnotou (e _{tm ):} Toto je jazyk obsahujúci všetky kódovanie Turing Machine `⟨M⟩`, kde jazyk rozpoznávaný Turingovou strojom` M` je prázdny (t. J. `l (m) =∅`). (Toto nie je * rozpoznateľné).

* ¬e tm : Toto je jazyk obsahujúci všetky kódovanie Turing Machine `⟨m⟩`, kde jazyk rozpoznávaný Turingovou strojom` m` nie je * prázdny (t. J. `l (m) ≠ ∅`).

* Prečo je to rozpoznateľné: Turingový stroj dokáže rozpoznať tento jazyk simuláciou stroja `M` na všetkých možných vstupoch, kým neakceptuje` M`.

4. Jazyk Turingov strojov, ktoré sa nezastavujú na * žiaden * vstup:

* Zoberme si jazyk Turingov strojov, ktoré, keď sa začnú na * akýmkoľvek * vstupným reťazcom, nikdy nezastavia. Neexistuje žiadny všeobecný algoritmus, ktorý by to určil.

* Mohli by ste skúsiť spustiť stroj na mnohých rôznych vstupoch, ale nikdy si nebudete istí, že sa nezastavuje na inom, netestovanom vstupe.

Ako sa líšia jazyky, ktoré sa netýkajú,

Kľúčový rozdiel spočíva v schopnosti vytvoriť Turingov stroj, ktorý * spoľahlivo * rozpoznáva reťazce v jazyku:

* Turing dec.: Turingov stroj * vždy * dáva správnu odpoveď („áno“ alebo „nie“) a zastavuje sa.

* Turing uznávateľné: Turingov stroj dáva odpoveď „áno“, ak je reťazec v jazyku, ale ak je reťazec v jazyku * nie *.

* Neuznávacie rozpoznateľné: * Žiadny* Turing stroj sa nedá skonštruovať tak, aby spoľahlivo rozpoznal reťazce v jazyku. Akýkoľvek Turingov stroj, ktorý vyskúšate, buď akceptuje niektoré reťazce, ktoré * nie sú * v jazyku, navždy slučky na reťazcoch, ktoré sú * v jazyku, alebo zlyhávajú iným zásadným spôsobom.

intuícia

Pomysli na to takto:

* Decidable: Máte dokonale spoľahlivý test, ktorý vám vždy dáva správnu odpoveď.

* rozpoznateľné: Máte test, ktorý * určite * povie „áno“, ak je to správna odpoveď, ale nemusí byť schopná povedať, či je odpoveď „nie“.

* Neoznávateľné: Nemôžete ani vytvoriť test, ktorý spoľahlivo identifikuje prípady „áno“. Akýkoľvek test, s ktorým prídete, bude chybný a môže vám poskytnúť nesprávne výsledky.

Dôležité dôsledky

Existencia nevyužitých rozpoznateľných jazykov má hlboké dôsledky pre informatiku a matematiku:

* Limity výpočtu: Ukazuje, že existujú vlastné obmedzenia toho, čo môžu počítače robiť, bez ohľadu na to, aké silné sú.

* Nepreplateľnosť: Zdôrazňuje existenciu problémov, ktoré sú zásadne nerozhodnuteľné - neexistuje žiadny algoritmus, ktorý ich dokáže vyriešiť vo všetkých prípadoch.

* Proof Techniques: Vyžaduje použitie sofistikovaných techník dôkazov (ako je diagonalizácia a redukcie), aby sa preukázala nepopierateľnosť alebo nerozpoznateľnosť určitých problémov.

Stručne povedané, neurčené rozpoznateľné jazyky definujú hranicu toho, čo je zásadne nekomplikovateľné. Sú kľúčovou súčasťou porozumenia teoretických limitov výpočtu.

• Predchádzajúca strana: Aké sú príklady logických operátorov používaných v programovacích jazykoch? 
• Ďalšia strana: Aké sú príklady pravidelných jazykov a ako sa definujú v kontextovej teórii formálneho jazyka?