Problém zastavení

V teorii vyčíslitelnosti je problém zastavení je rozhodovací problém, který může být neformálně řečeno takto:

Alan Turing v roce 1936 dokázal, že obecný algoritmus pro řešení problému haltingu pro všechny možné dvojice programů a vstupů nemůže existovat. Říkáme, že problém haltingu je nerozhodnutelný nad Turingovými stroji. (Viz s ohledem na přičtení problému haltingu Turingovi.)

Rozhodovací problém je množina přirozených čísel, „problém“ je určit, zda určité číslo je v množině.

Vzhledem k tomu, Gödel číslování vypočitatelných funkcí (jako je Turingova čísla popisu) a párování funkce, zastavení problém (také volal halting soubor) je rozhodnutí problém pro soubor

s i-tého vypočitatelné funkce v rámci Gödel číslování .

Přestože je množina K rekurzivně spočitatelná, problém haltingu není řešitelný pomocí výpočetní funkce.

Význam a důsledky

Historický význam zastavující problém spočívá ve skutečnosti, že to byl jeden z prvních problémů, které mají být prokázáno jako nerozhodnutelné. (Turingův důkaz šel do tisku v květnu 1936, zatímco církev je důkaz o nerozhodnutelnost problému v lambda kalkulu již byla zveřejněna v dubnu 1936.) Následně, mnoho dalších takových problémů byly popsány; typický způsob prokázání problému být nerozhodnutelný je s technikou snížení. Chcete-li to, počítačový vědec ukazuje, že pokud řešení nového problému bylo nalezeno, to by mohlo být použito k rozhodnutí nerozhodnutelný problém (tím, že transformuje případy nerozhodnutelné problém do instancí nového problému). Vzhledem k tomu, že už víme, že žádná metoda může rozhodnout starý problém, žádná metoda může rozhodnout nový problém buď.

Jedním z takových důsledků nerozhodnutelnosti zastavujícího problému je, že nemůže existovat obecný algoritmus, který by rozhodoval o tom, zda daný výrok o přirozených číslech je pravdivý, nebo ne. Důvodem je, že výrok, který říká, že určitý algoritmus zastaví určitý vstup, může být převeden na ekvivalentní výrok o přirozených číslech. Kdybychom měli algoritmus, který by vyřešil každý výrok o přirozených číslech, určitě by vyřešil i tento; ale to by rozhodlo o tom, zda se původní program zastaví, což je nemožné, protože zastavující problém je nerozhodnutelný.

Dalším důsledkem nerozhodnutelnosti zastavujícího problému je Riceova věta, která říká, že pravdivost jakéhokoliv netriviálního výroku o funkci, která je definována algoritmem, je nerozhodnutelná. Takže například rozhodovací problém „zastaví se tento algoritmus pro vstup 0“ je již nerozhodnutelný. Všimněte si, že tato věta platí pro funkci definovanou algoritmem a ne pro algoritmus samotný. Je například docela možné rozhodnout, zda se algoritmus zastaví do 100 kroků, ale toto není výrok o funkci, která je definována algoritmem.

Gregory Chaitin definoval pravděpodobnost zastavení, reprezentovanou symbolem Ω, typem reálného čísla, o kterém se neformálně říká, že reprezentuje pravděpodobnost, že náhodně vytvořený program se zastaví. Tato čísla mají stejný Turingův stupeň jako problém zastavení. Je to normální a transcendentální číslo, které může být definováno, ale nemůže být kompletně vypočteno. To znamená, že lze dokázat, že neexistuje algoritmus, který produkuje číslice Ω, i když jeho prvních několik číslic může být vypočteno v jednoduchých případech.

Zatímco Turingův důkaz ukazuje, že nemůže existovat žádná obecná metoda nebo algoritmus, který by určil, zda se algoritmy zastaví, jednotlivé případy tohoto problému mohou být velmi dobře náchylné k útoku. Vzhledem ke konkrétnímu algoritmu lze často ukázat, že se musí zastavit pro jakýkoli vstup, a ve skutečnosti to počítačoví vědci často dělají jako součást důkazu správnosti. Ale každý důkaz musí být vyvinut speciálně pro daný algoritmus; neexistuje žádný mechanický, obecný způsob, jak určit, zda se algoritmy na Turingově stroji zastaví. Nicméně existují některé heuristiky, které mohou být použity automatizovaným způsobem, aby se pokusily vytvořit důkaz, což se často daří na typických programech. Tato oblast výzkumu je známá jako automatizovaná terminační analýza.

Turingova zavedení stroje model, který se stal známý jako Turingův stroj, představil v novinách, se ukázala jako vhodný model pro mnoho teoretické informatiky od.

Metoda dokazování je reductio ad absurdum. Je vám dán programovací jazyk, schéma, které spojuje každý program, který je realizovatelný na Turingově stroji, s řetězcem, který tento program popisuje. Předpokládejme, že někdo tvrdí, že našel program halt(p, i), který vrací true, pokud řetězec p popisuje program, který se zastaví, když je jako vstup zadán řetězec i, a vrací false, pokud p popisuje program, který se nezastaví na i. Zbytek důkazu ukazuje, jak sestrojit program, na kterém se halt nemůže chovat tak, jak se tvrdí.

Jsou-li dva programy realizovatelné na Turingově stroji, pak je realizovatelné i provedení obou programů v pořadí, a stejně tak je možné provést jeden v závislosti na podmínce. To znamená, že můžete zkonstruovat program zvaný potíže, přičemž vezmete jeden vstup, který provede následující:

Protože všechny programy mají popisy řetězců, existuje řetězec t, který představuje potíže programu. Zastaví se potíže, když je jeho vstup t?

V obou případech dochází k závěru, že halt neposkytlo správnou odpověď, na rozdíl od původního tvrzení. Vzhledem k tomu, že stejná úvaha platí pro jakýkoli program, který by někdo mohl nabídnout jako řešení problému halting, nemůže existovat žádné řešení.

Tento klasický důkaz je obvykle označován jako důkaz diagonalizace, tak zvaný proto, že pokud si člověk představí mřížku obsahující všechny hodnoty halt(p, i), přičemž každá možná hodnota p má svůj vlastní řádek, a každá možná hodnota i má svůj vlastní sloupec, pak hodnoty halt(s, s) jsou uspořádány podél hlavní diagonály této mřížky. Důkaz lze zarámovat do podoby otázky: který řádek mřížky odpovídá řetězci t? Odpověď je taková, že problémová funkce je vymyšlena tak, že halt(t, i) se liší od každého řádku v mřížce alespoň v jedné poloze: konkrétně v hlavní diagonále, kde t=i. To je v rozporu s požadavkem, že mřížka obsahuje řádek pro každou možnou hodnotu p, a proto představuje důkaz rozporem, že problém zastavení je nerozhodnutelný.

Mnoho studentů se po analýze výše uvedeného důkazu ptá, zda by mohl existovat algoritmus, který by mohl pro některé programy vrátit třetí možnost, například „nerozhodnutelný“ nebo „by vedl k rozporu“. To odráží nepochopení rozhodnosti. Je snadné sestrojit jeden algoritmus, který vždy odpovídá „zastavuje“ a jiný, který vždy odpovídá „nezastavuje“. Pro každý konkrétní program a vstup jeden z těchto dvou algoritmů odpovídá správně, i když nikdo nemusí vědět který. Obtížnost problému zastavení nespočívá v konkrétních programech, ale v požadavku, že řešení musí fungovat pro všechny programy.

Zastavovací problém je teoreticky, ne-li v praxi, pro deterministické stroje s konečnou pamětí rozhodnutelný. Stroj s konečnou pamětí má konečný počet stavů, a proto každý deterministický program na něm musí nakonec buď zastavit, nebo zopakovat předchozí stav:

Minsky nabádá čtenáře, aby byl podezíravý – i když stroj může být konečný a konečné automaty „mají řadu teoretických omezení“:

Více o této problematice „neřešitelnosti“ najdete v článku Zaneprázdněný bobr.

Může být také automaticky rozhodnuto, zda nedeterministický stroj s konečnou pamětí zastaví na ne, některé, nebo všechny možné sekvence nedeterministických rozhodnutí, výčtem stavů po každém možném rozhodnutí.

Formalizace problému haltingu

Ve svém původním důkazu Turing formalizoval koncept algoritmu zavedením Turingových strojů. Výsledek však není v žádném případě specifický pro ně; platí stejně pro jakýkoli jiný model výpočtu, který je rovnocenný svým výpočetním výkonem Turingovým strojům, jako jsou Markovovy algoritmy, Lambda kalkul, Post systémy nebo registr stroje.

Důležité je, že formalizace umožňuje přímočaré mapování algoritmů na nějaký datový typ, se kterým může algoritmus pracovat. Pokud například formalismus nechá algoritmy definovat funkce nad řetězci (jako Turingovy stroje), pak by mělo dojít k mapování těchto algoritmů na řetězce, a pokud formalismus nechá algoritmy definovat funkce nad přirozenými čísly (jako jsou vypočitatelné funkce), pak by mělo dojít k mapování algoritmů na přirozená čísla. Mapování na řetězce je obvykle nejjednodušší, ale řetězce nad abecedou s n znaky mohou být také mapovány na čísla tím, že je interpretují jako čísla v n-ární číselné soustavě.

Vztah ke Gödelově větě o neúplnosti

Pojmy vyvolané Gödelovými větami o neúplnosti jsou velmi podobné těm, které vyvolal problém haltingu, a důkazy jsou si dost podobné. Ve skutečnosti je slabší forma První věty o neúplnosti snadným důsledkem nerozhodnutelnosti problému haltingu. Tato slabší forma se liší od standardního tvrzení věty o neúplnosti tvrzením, že úplná, konzistentní a zdravá axiomatizace všech tvrzení o přirozených číslech je nedosažitelná. Ta „zdravá“ část je oslabení: znamená to, že požadujeme, aby daný axiomatický systém dokazoval pouze pravdivá tvrzení o přirozených číslech (je velmi důležité poznamenat, že tvrzení o standardní formě Gödelovy První věty o neúplnosti se vůbec nezabývá otázkou pravdy, ale týká se pouze otázky, zda to může být dokázáno).

Slabší forma věta může být prokázáno z nerozhodnutelnost na halting problém takto. Předpokládejme, že máme konzistentní a úplnou axiomatizaci všech pravdivých logických výroků prvního řádu o přirozených číslech. Pak můžeme sestavit algoritmus, který všechny tyto příkazy vyjmenovává. To znamená, že existuje algoritmus N(n), který vzhledem k přirozenému číslu n vypočítá pravdivý logický výrok prvního řádu o přirozených číslech tak, že pro všechny pravdivé výroky existuje alespoň jedno n takové, že N(n) dává tento výrok. Nyní předpokládejme, že chceme rozhodnout, zda algoritmus s reprezentací a zastaví na vstupu i. Víme, že tento výrok lze vyjádřit logickým výrokem prvního řádu, řekněme H(a, i). Vzhledem k tomu, že axiomatizace je kompletní vyplývá, že buď existuje n taková, že N (n) = H (a, i) nebo existuje n‘ taková, že N (n‘) = ¬ H (a, i). Pokud tedy budeme iterovat přes všechna n, dokud nenajdeme buď H(a, i) nebo jeho negaci, vždy se zastavíme. To znamená, že nám to dává algoritmus, který rozhodne o problému zastavení. Protože víme, že takový algoritmus nemůže existovat, vyplývá z toho, že předpoklad, že existuje důsledná a úplná axiomatizace všech pravdivých logických tvrzení prvního řádu o přirozených číslech, musí být nepravdivý.

Dokážou lidé vyřešit problém zastavení?

Mohlo by se zdát, že problém zastavení by mohli vyřešit lidé. Programátor se koneckonců může často podívat na program a říct, zda se zastaví. Je užitečné pochopit, proč to nemůže být pravda. Pro zjednodušení zvážíme problém zastavení programů bez vstupu, který je také nerozhodnutelný.

„Vyřešit“ problém zastavení znamená být schopen podívat se na jakýkoli program a říct, zda se zastaví. Nestačí být schopen podívat se na některé programy a rozhodnout se. Lidé také nemusí být schopni vyřešit problém zastavení, kvůli samotné velikosti vstupu (program s miliony řádků kódu). Ani u krátkých programů není jasné, zda lidé vždy poznají, zda se zastaví. Například bychom se mohli zeptat, zda se tato pseudokódová funkce, která odpovídá konkrétnímu Turingovu stroji, někdy zastaví:

Tento program hledá, dokud nenajde liché dokonalé číslo, pak se zastaví. Zastaví se tehdy a jen tehdy, pokud takové číslo existuje, což je v matematice hlavní otevřená otázka. Po staletích práce tedy matematici ještě neobjevili, zda se jednoduchý desetiřádkový program zastaví. Proto je obtížné pochopit, jak by lidé mohli problém zastavení vyřešit.

V obecnější rovině je obvykle snadné zjistit, jak napsat jednoduchý vyhledávací program hrubou silou, který hledá protipříklady k nějaké konkrétní domněnce v teorii čísel; pokud program protipříklad najde, zastaví se a protipříklad vytiskne, a jinak pokračuje v hledání navždy. Vezměme si například slavnou (a dosud nevyřešenou) dvojitou prvočíselnou domněnku. Ta se ptá, zda existují libovolně velká prvočísla p a q s p+2 = q. Nyní si vezměme následující program, který přijímá vstup N:

Tento program hledá dvojitá prvočísla p a p+2 alespoň tak velká jako N. Pokud existují libovolně velká dvojitá prvočísla, zastaví se pro všechny možné vstupy. Pokud však existuje dvojice dvojitých prvočísel P a P+2 větší než všechna ostatní dvojitá prvočísla, pak se program nikdy nezastaví, pokud je zadán vstup N větší než P. Pokud bychom tedy mohli odpovědět na otázku, zda se tento program zastaví na všech vstupech, měli bychom dlouho hledanou odpověď na dvojitou prvočíselnou domněnku. Podobně jednoduché je psát programy, které se zastaví v závislosti na pravdě nebo nepravdě pro mnoho dalších domněnek teorie čísel.

Kvůli tomu by se dalo říci, že neřešitelnost zastavujícího problému není nijak překvapivá. Pokud by existoval mechanický způsob, jak rozhodnout, zda se libovolné programy zastaví, pak by mu podlehlo mnoho na první pohled obtížných matematických problémů. Protiargument k tomu ovšem je, že i kdyby byl zastavující problém rozhodnutelný přes Turingovy stroje, jako je tomu u fyzických počítačů a jiných LBA, v praxi by mohl být stále neproveditelný, protože jeho vykonání zabere příliš mnoho času nebo paměti. Například v teorii čísel existují velmi velké horní meze čísel s určitými vlastnostmi (převládajícím příkladem je Grahamovo číslo), ale není možné naivně kontrolovat všechny hodnoty pod touto hranicí s počítačem – ta dokonce některá z těchto čísel neudrží v paměti.

Rozpoznání dílčích řešení

Existuje mnoho programů, které buď vrátí správnou odpověď na problém zastavení, nebo odpověď nevrátí vůbec. Pokud by bylo možné rozhodnout, zda program dává pouze správné odpovědi, dalo by se doufat, že se podaří shromáždit velké množství takových programů a spustit je souběžně v naději, že se podaří zjistit, zda se mnoho programů zastaví. Rozpoznat takové částečně zastavující řešitele (PHS) je však stejně těžké jako samotný problém zastavení.

Předpokládejme, že někdo tvrdí, že program PHSR je částečně zastavující řešitel rozpoznávač. Sestrojit program H:

Pokud PHSR rozpozná konstruovaný program X jako řešitel částečného zastavení, znamená to, že P, jediný vstup, pro který X vytváří výsledek, se zastaví. Pokud PHSR nerozpozná X, pak to musí být proto, že P se nezastaví. Proto H může rozhodnout, zda se libovolný program P zastaví; vyřeší problém zastavení. Protože to není možné, program PHSR nemohl být řešitelem částečného zastavení, jak se tvrdilo. Proto žádný program nemůže být řešitelem částečného zastavení.

Další příklad, HT, Turingova stroje, který dává správné odpovědi pouze pro některé případy problému zastavení lze popsat požadavkem, že pokud HT začne skenovat pole, které nese první z konečných řetězců po sobě jdoucích „1“, následuje jedno pole se symbolem „0“ (tj. prázdné pole) a následuje po něm konečný řetězec i po sobě jdoucích „1“, na jinak prázdné pásce, pak

Zatímco jeho existence nebyla vyvrácena (v podstatě: protože neexistuje Turingův stroj, který by se zastavil pouze při startu na prázdné pásce), takový Turingův stroj HT by problém zastavení vyřešil pouze částečně (protože nemusí nutně skenovat symbol „1“ v konečném stavu, pokud Turingův stroj reprezentovaný a se zastaví při daném startovním stavu a vstupu reprezentovaném i, jak mohou explicitní prohlášení problému zastavení pro Turingovy stroje vyžadovat).

Historie problému zastavení

1900 — Hilbert představuje jeho „23 otázek“ cf Hilbert problémy na druhém mezinárodním kongresu matematiků v Paříži, „Z nich druhý byl, že na prokázání konzistence z ‚Peano axiomy‘, na které, jak byl prokázán, důslednost matematiky závislé“ (Hodges s. 83, Davis‘ komentář v U s. 108).

1928 – Hilbert přepracoval svůj „Druhý problém“ na Boloňském mezinárodním kongresu (srov. Reid s. 188-189). Hodges tvrdí, že položil tři otázky: tj. #1: Byla matematika úplná? #2: Byla matematika konzistentní? #3: Byla matematika rozhodnutelná? (Hodges s. 91). Třetí otázka je známá jako Entscheidungsproblem (Rozhodovací problém) (Hodges s. 91, Penrose s. 34)

1930 – Gödel oznamuje důkaz jako odpověď na první dvě Hilbertovy otázky z roku 1928 [srov. Reid s. 198]. „Zpočátku byl [Hilbert] jen naštvaný a frustrovaný, ale pak se začal snažit konstruktivně řešit problém… Gödel sám cítil – a vyjádřil myšlenku ve své práci – že jeho práce není v rozporu s Hilbertovým formalistickým názorem“ (Reid s. 199).

1931 – Objevuje se práce Kurta Gödela: „O formálně nerozhodnutelných návrzích Principia Mathematica a souvisejících systémů I“ (přetištěno v U s. 5ff)

19. dubna 1935 – Papír Alonza Churche „Neřešitelný problém teorie elementárního čísla“ identifikuje, co to znamená, aby funkce byla efektivní vypočitatelná. Taková funkce bude mít algoritmus a „…skutečnost, že algoritmus skončil, se stane fakticky známou …“ (kurziva přidána, U s. 100).

1936 – Alonzo Church zveřejňuje první důkaz, že Entscheidungsproblem je neřešitelný [Poznámka k Entsheidungsproblem, přetištěná v U s. 110].

7. října 1936 — Článek Emila Posta „Konečné kombinační procesy. Přijata formulace I“. Post přidává ke svému „procesu“ instrukci „(C) Stop“. Takový proces nazval „typ 1 … jestliže proces, který určuje, skončí pro každý konkrétní problém.“ (U. p.289ff)

1937 – Alan Turingův článek O vypočitatelných číslech s aplikací na Entscheidungsproblem se dočká tisku v lednu 1937 (přetištěný v U, str. 115). Turingův důkaz se odchyluje od výpočtu rekurzivními funkcemi a zavádí pojem výpočtu pomocí stroje. Stephen Kleene (1952) se o tom zmiňuje jako o jednom z „prvních příkladů problémů s rozhodnutím, které se ukázaly jako neřešitelné“.

1939 – J.B. Rosser pozoruje zásadní ekvivalenci „efektivní metody“ definované Gödelem, Churchem a Turingem (Rosser v U s. 273, „Neformální expozice důkazů Gödelova teorému a Církevního teorému“).

1943 – Stephen Kleene ve své práci z roku 1943 uvádí, že „Při vytváření kompletní algoritmické teorie, co děláme, je popis postupu … který postup nutně končí a takovým způsobem, že z výsledku můžeme číst definitivní odpověď, „Ano“ nebo „Ne“, na otázku, „Je predikátová hodnota pravda?“.

1952 — Stephen Kleene (1952) Kapitola XIII („Vypočítatelné funkce“) obsahuje diskusi o neřešitelnosti problému zastavení pro Turingovy stroje a přeformuluje jej ve smyslu strojů, které se „nakonec zastaví“, tj. zastaví: „… neexistuje žádný algoritmus pro rozhodování, zda se daný stroj při startu z dané situace nakonec zastaví.“ (Kleene (1952) s. 382)

1952 — „Davis [ Martin Davis ] se domnívá, že je pravděpodobné, že poprvé použil termín ‚haltingový problém‘ v sérii přednášek, které přednášel v laboratoři řídicích systémů na University of Illinois v roce 1952 (dopis Davise Copelandovi, 12. prosince 2001.)“ (Poznámka pod čarou 61 v Copelandovi (2004) s. 40ff)

Nejhorší doba provedení

Larry Wall jednou poznamenal: „Je snadné vyřešit problém zastavení brokovnicí.“ (Larry Wall v <199801151836.KAA14656@wall.org>)