Čo je príkladom nerečiteľného jazyka?

Jedným z najslávnejších príkladov nerečiteľného jazyka je problém s zastavením .

Problém s zastavením:

Problémom zastavenia je problém určenia, vzhľadom na opis ľubovoľného počítačového programu a vstup, či program dokončí spustenie alebo bude pokračovať v behu navždy. Formálnejšie sa pýta:

* Vstup: `` kde:

* `P` je Turingov stroj (alebo reprezentácia akéhokoľvek všeobecného počítačového programu).

* `I's je vstup do Turingovho stroja` p`.

* výstup:

* „Áno“, ak sa Turingov stroj `p` zastavuje (dokončí vykonanie), keď je daný vstup` i`.

* „Nie“, ak Turing Machine `p` nezastavuje (slučky navždy), keď je daný vstup` i`.

Prečo je to nerozhodnuteľné:

Problém zastavenia je nerozhodnutý, čo znamená, že existuje * žiadny * Turingov stroj (alebo algoritmus), ktorý dokáže správne vyriešiť problém zastavenia pre * všetky * možné vstupy ``.

Dôkaz sa zvyčajne vykonáva rozporom. Predpokladajme, že * existuje * Turingov stroj `H`, ktorý rieši problém zastavenia. `H` berie` `ako vstup a výstupy" áno ", ak" P` sa zastaví na "i" a "nie", ak `p` navždy slučku na` i '.

Potom môžeme zostaviť ďalší Turingov stroj (často nazývaný „diagonalizátor“), ktorý používa ako podprogram „H`:H`:

`` `

Turing Stroj D (P):

1. Run H (p, p) // spustite h s p ako program aj vstup

2. Ak H (p, p) vráti „áno“ (P sa zastaví pri vstupe p):

Potom navždy slučku.

3. Ak H (p, p) vráti „no“ (P slučky navždy pri vstupe p):

Potom zastavte.

`` `

Čo sa stane, keď spustíme `d` so sebou ako vstup:` d (d) `?

* scenár 1:Predpokladajme `d (d)` SAMTS.

- To znamená, že v kroku 1, `H (d, d)„ vrátené „áno“ (pretože `d` zastavuje, iba ak` h (d, d) `hovorí, že` d` zastavuje pri vstupe `d`).

- Ale ak `h (d, d)„ vrátil sa „áno“, potom bol „d` navrhnutý tak, aby navždy slučoval (v kroku 2). To je v rozpore s naším predpokladom, že `d (d) sa zastavuje.

* scenár 2:Predpokladajme `d (d)` slučky navždy.

- To znamená, že v kroku 1, `h (d, d)` vrátené „nie“ (pretože `d` slučky navždy, iba ak` h (d, d) `hovorí, že` d` slučky na vstupe `d`).

- ale ak `h (d, d)„ vrátil sa „nie“, potom bol „d` navrhnutý tak, aby sa zastavil (v kroku 3). To je v rozpore s naším predpokladom, že `d (d)„ navždy slučky.

Pretože oba scenáre vedú k rozporu, náš počiatočný predpoklad, že existuje Turingov stroj „H`, ktorý rieši problém zastavenia, musí byť nepravdivý. Preto je problém s zastavením nerozhodnuteľný.

Zjednodušene povedané: Nemôžete napísať program, ktorý môže vždy spoľahlivo predpovedať, či iný program sa nakoniec zastaví alebo spustí navždy.

Význam:

Neurčitosť problému s zastavením má hlboké dôsledky pre informatiku. Ukazuje, že existujú zásadné limity pre to, čo môžu počítače vypočítať. Slúži tiež ako základ na preukázanie nerešpektovania mnohých ďalších problémov. Ak dokážete ukázať, že riešenie iného problému by vám umožnilo vyriešiť problém s zastavením, potom tento problém musí byť tiež nerozhodnutý.

• Predchádzajúca strana: Čo je príklad rozhodujúceho jazyka? 
• Ďalšia strana: Čo je jazyk zostavovateľ a ako sa používa v počítačovom programovaní?