Stop problém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. listopadu 2021; kontroly vyžadují 4 úpravy .

Problém zastavení je jedním z problémů v teorii  algoritmů [1] , který lze neformálně říci jako:

Je uveden popis procedury a její počáteční vstupní data. Je třeba určit: zda provedení procedury s těmito údaji někdy skončí; nebo že procedura poběží celou dobu bez zastavení.

Alan Turing v roce 1936 dokázal , že problém zastavení je na Turingově stroji nerozhodnutelný . Jinými slovy, neexistuje žádný obecný algoritmus pro řešení tohoto problému. [2]

Problém zastavení je ústředním bodem teorie vyčíslitelnosti, protože je prvním příkladem problému, který nelze vyřešit algoritmicky.

Z hlediska funkcí lze problém snadno popsat takto:

Pro jakoukoli funkci F(G, start_state), která dokáže určit, zda se jiná funkce zastaví, můžete vždy napsat funkci G(start_state), která po předání F bude mít opačný výsledek provedení, než F předpovídá.

Pro mnoho dalších úkolů[ co? ] lze prokázat jejich algoritmickou nerozhodnutelnost tím, že se je pokusíme zredukovat na problém zastavení. Děje se tak podle schématu „naopak“: nechť existuje určitý problém, u kterého je třeba zjistit jeho neřešitelnost. Pak předpokládáme, že je to řešitelné a pokusíme se s využitím této skutečnosti napsat algoritmus pro řešení problému zastavení pro tento problém. Pokud se to podaří, dojdeme k rozporu, protože je známo, že neexistuje žádný algoritmus pro řešení problému zastavení. To znamená, že předpoklad byl chybný a původní problém je také neřešitelný.

Důkaz

Zvažte sadu algoritmů, které berou přirozené číslo jako vstup a také dávají přirozené číslo jako výstup. Vyberme si nějaký Turingův kompletní programovací jazyk. Každý algoritmus lze v tomto jazyce zapsat jako konečnou posloupnost znaků. Uspořádejme množinu (to je možné, protože se jedná o množinu konečných posloupností prvků konečné množiny a tedy spočetné ) a každý algoritmus dostane své vlastní pořadové číslo. Nazvěme analyzátor hypotetický algoritmus, který přijímá dvojici přirozených čísel jako vstup a:

Problém zastavení lze přeformulovat následovně: Existuje analyzátor?

Teorém. Analyzátor neexistuje.

Dokažme to kontradikcí. Řekněme, že analyzátor existuje. Pojďme napsat algoritmus Diagonalizer, který vezme jako vstup číslo , předá pár argumentů analyzátoru a vrátí výsledek své práce. Jinými slovy, Diagonalizer se zastaví tehdy a pouze tehdy, když se algoritmus s číslem nezastaví po přijetí čísla jako vstupu . Nechť  je pořadové číslo Diagonalizer v sadě . Spusťte Diagonalizer tak, že mu předáte toto číslo . Diagonalizátor se zastaví právě tehdy, když se algoritmus s číslem (tedy on sám) nezastaví, když obdrží jako vstup číslo (které jsme mu předali). Z tohoto rozporu vyplývá, že náš předpoklad je chybný: Analyzátor neexistuje, což bylo třeba dokázat.

Viz také

Poznámky

  1. ↑ N.K. Vereshchagin, A. Shen Přednášky o matematické logice a teorii algoritmů. Část 3. Vyčíslitelné funkce Archivováno 12. listopadu 2015 na Wayback Machine
  2. ↑ Turing A. On Computable Numbers, with the Application to the Entscheidungsproblem  // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - S. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230 (v této publikaci Turing zavádí definici Turingova stroje , formuluje problém zablokování a ukazuje, že je stejně jako problém rozlišení neřešitelný).

Odkazy