Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky

Domáce Hardware Siete Programovanie Softvér Otázka Systémy

Aké sú príklady nerozhodnuteľných jazykov a ako sa líšia od rozhodovateľných jazykov?

Neprelé jazyky sú jazyky, pre ktoré nemôže existovať žiadny algoritmus (Turing Machine), ktorý správne rozhoduje pre každý vstupný reťazec, či je tento reťazec členom jazyka. Naproti tomu rozhodné jazyky, * majú taký algoritmus. Kľúčový rozdiel spočíva v existencii zaručeného algoritmu zastavenia.

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.

Najnovšie články

Copyright © počítačové znalosti Všetky práva vyhradené