Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Tu je niekoľko príkladov nerozhodnuteľných jazykov, ktoré ilustrujú rôzne spôsoby neopodstatnosti:Vznikajú:
1. Problém zastavenia (h):
* Popis jazyka: H ={⟨m, w⟩ | Turing Stroj sa zastavuje pri vstupe w}. Tento jazyk pozostáva zo všetkých párov kódovania Turingovho stroja (⟨M⟩) a vstupného reťazca (w) tak, aby sa stroj zastavil, keď je uvedený ako vstup.
* Nepreplateľnosť: Je dokázané, že žiadny algoritmus nemôže existovať, ktorý správne určuje, pre každé ⟨m, w⟩, či sa m zastaví na w. Toto je zásadný výsledok v teórii výpočtu. Akýkoľvek pokus o vybudovanie takéhoto algoritmu vedie k rozporu (zvyčajne prostredníctvom diagonalizácie).
* Prečo je to nerozhodnuteľné: Neupraviteľnosť problému s zastavením pramení z inherentnej samohodnotenej povahy strojov Turing. Hypotetický algoritmus, ktorý rieši problém zastavenia, by sa mohol použiť na vytvorenie paradoxného stroja, ktorý je v rozpore s jeho vlastným predpokladaným správaním.
2. Problém s akceptáciou (a):
* Popis jazyka: A ={⟨m, w⟩ | Turing Machine M prijíma W}. Je to podobné ako problém s zastavením, ale zameriava sa konkrétne na prijatie (stroj sa zastaví v akceptujúcom stave).
* Nepreplateľnosť: To je tiež nerozhodnuteľné. Keby sme sa mohli rozhodnúť, mohli by sme sa tiež rozhodnúť H (pretože ak M prijme w, jednoznačne sa zastaví na w). Pretože H je nerozhodnuteľný, musí byť tiež nerozhodnuteľný.
3. Problém prázdnoty pre stroje Turing (E):
* Popis jazyka: E ={⟨m⟩ | L (m) =∅}, kde l (m) je jazyk akceptovaný Turingovom strojom M. Tento jazyk obsahuje kódovanie všetkých Turingových strojov, ktoré neakceptujú vôbec žiadne reťazce (ich jazyk je prázdny).
* Nepreplateľnosť: Neexistuje žiadny algoritmus, ktorý by mohol určiť, pre každý Turing stroj M, či je L (M) prázdny. To súvisí s problémom zastavenia; Keby sme mohli vyriešiť E, mohli by sme vyriešiť problém zastavenia vytvorením stroja M ', ktorý sa zastaví, ak a iba vtedy, ak sa zastaví a akceptuje w.
4. Problém s korešpondenciou (PCP):
* Popis jazyka: Toto je zložitejší príklad zahŕňajúci páry reťazcov. Je nerozhodné určiť, či má daná sada reťazcových párov riešenie (zreťazenie reťazcov z párov, ktoré sa zhodujú).
* Nepreplateľnosť: Neurčiteľnosť PCP sa preukáže pomocou zníženia (ukazuje, že ak by bol PCP rozhodný, problém zastavenia by bol tiež rozhodujúci - protirečenie).
Decidable Languages - Contrast:
Na druhej strane rozhodné jazyky * majú * algoritmy, ktoré vždy zastavujú a správne klasifikujú reťazce ako patriace k jazyku alebo nie. Príklady zahŕňajú:
* Jazyk palindromes: Algoritmus môže ľahko skontrolovať, či je daný reťazec rovnaký a dozadu.
* Jazyk reťazcov obsahujúcich „ABC“: Jednoduchý algoritmus môže naskenovať reťazec a skontrolovať podrestčku „ABC“.
* Jazyk binárnych reťazcov rovnomerných: Algoritmus môže skontrolovať dĺžku reťazca.
Rozdiel sa v podstate scvrkáva na to, či môže byť algoritmus navrhnutý tak, aby * vždy * dáva správnu odpoveď áno/nie v konečnom čase. V prípade nerozhodnuteľných jazykov je možné takéto algoritmus preukázať. Existencia takéhoto algoritmu je určujúca vlastnosť, ktorá sa odlišuje od nerozhodnuteľných jazykov.