Je vám jasný rozdiel medzi rozhodujúcimi a rozpoznateľnými jazykmi v teoretickej informatike?

Áno, rozdiel medzi rozhodujúcimi a rozpoznateľnými jazykmi je úplne jasný. Rozdiel spočíva v správaní sa Turing Machine (TM), ktorý sa snaží určiť členstvo:

* Decidable Language (rekurzívny jazyk): Jazyk L je zložiteľný, ak existuje Turingov stroj, ktorý pre * každý * vstupný reťazec w, zastaví sa a správne odpovedá „áno“, ak w ∈ L a „nie“, ak w ∉ l. To znamená, že TM sa vždy zastaví, bez ohľadu na to, či je vstup v jazyku alebo nie.

* rozpoznateľný jazyk (rekurzívne vymeniteľný jazyk): Jazyk L je rozpoznateľný, ak existuje Turingov stroj, ktorý pre * každý * vstupný reťazec w, zastavuje a odpovedá „áno“, ak w ∈ L. Avšak, ak w ∉ l, môže TM zastaviť a odpovedať „nie“ alebo môže bežať navždy (slučka na neurčito). Kľúčom je, že vždy * dáva správnu odpoveď („Áno“), ak je reťazec v jazyku; Je povolené byť iba deterministický alebo neposkytnúť odpoveď, keď reťazec nie je * v jazyku *.

Zjednodušene povedané:

* Decidable: TM vždy dáva definitívnu odpoveď (áno alebo nie) v konečnom čase.

* rozpoznateľné: TM dáva odpoveď „áno“ v konečnom čase, ak je vstup v jazyku, ale nemusí dať odpoveď (navždy slučkou), ak vstup nie je v jazyku.

Každý rozhodujúci jazyk je tiež rozpoznateľný. Konverz však nie je pravdivý; Existujú rozpoznateľné jazyky, ktoré nie sú rozhodné. Problém s zastavením je klasickým príkladom jazyka, ktorý je rozpoznateľný, ale nie je možné. TM môže byť postavený, ktorý rozpoznáva reťazce predstavujúce zastavovacie stroje (simuluje stroj a odpovedá „áno“, ak sa zastaví), ale žiadny TM nemôže rozhodnúť, či sa ľubovoľný Turingov stroj zastaví na danom vstupe (pretože by to vyriešilo samotný problém zastavenia).

Rozdiel sa scvrkáva na to, či TM zaručuje ukončenie všetkých vstupov (rozhodovateľné) alebo iba zaručuje odpoveď „áno“ v konečnom čase pre vstupy v jazyku (rozpoznateľné). Rozdiel je zásadný v teórii výpočtu.

• Predchádzajúca strana: Ako môžeme navrhnúť PDA, ktorý akceptuje viac jazykov? 
• Ďalšia strana: Prijímajú iba kondičné kódy pre vstup programu?