Zastavení problému - Halting problem

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Září 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie vypočítatelnosti, zastavení problému je problém určit z popisu libovolného počítačový program a vstup, zda program dokončí běh, nebo bude pokračovat navždy. Alan Turing v roce 1936 dokázal, že generál algoritmus k vyřešení problému zastavení u všech možných párů vstupů programu nemůže existovat.

Pro jakýkoli program F to by mohlo určit, zda se programy zastaví, „patologický“ program G, volaný s nějakým vstupem, může předat svůj vlastní zdroj a svůj vstup F a pak konkrétně udělat opak toho, co F předpovídá G udělám. Ne F může existovat, která tento případ řeší. Klíčovou součástí důkazu je matematická definice počítače a programu, která je známá jako Turingův stroj; problém s zastavením je nerozhodnutelný přes Turingovy stroje. Je to jeden z prvních případů rozhodovací problémy se ukázala jako neřešitelná. Tento důkaz je důležitý pro praktické výpočetní úsilí a definuje třídu aplikací, které žádný programovací vynález nemůže dokonale fungovat.

Jack Copeland (2004) připisuje zavedení tohoto pojmu zastavení problému k práci Martin Davis v padesátých letech.^[1]

Pozadí

Problém zastavení je problém rozhodnutí o vlastnostech počítačových programů na pevném Turing-kompletní model výpočtu, tj. všechny programy, které lze psát v daném programovací jazyk to je dostatečně obecné, aby to bylo ekvivalentní Turingovu stroji. Problémem je určit, vzhledem k programu a vstupu do programu, zda se program při spuštění s tímto vstupem nakonec zastaví. V tomto abstraktním rámci neexistují žádná omezení zdrojů týkající se množství paměti nebo času potřebného pro spuštění programu; může trvat libovolně dlouho a před zastavením využít libovolné množství úložného prostoru. Otázkou je jednoduše, zda se daný program někdy zastaví na konkrétním vstupu.

Například v pseudo kód, Program

while (true) continue

nezastaví se; spíše to jde navždy v nekonečná smyčka. Na druhou stranu program

tisk "Ahoj, svět!"

zastaví se.

Při rozhodování, zda je zastavení těchto programů jednoduché, se složitější programy ukázaly jako problematické. Jedním z přístupů k problému může být spuštění programu pro určitý počet kroků a kontrola, zda se zastaví. Pokud se však program nezastaví, není známo, zda se program nakonec zastaví nebo bude fungovat navždy. Turing dokázal, že neexistuje žádný algoritmus, který vždy správně rozhodne, zda se pro daný libovolný program a vstup program zastaví, když je spuštěn s tímto vstupem. Podstatou Turingova důkazu je, že jakýkoli takový algoritmus lze udělat, aby si odporoval, a proto nemůže být správný.

Důsledky programování

Nějaký nekonečné smyčky může být docela užitečné. Například, smyčky událostí jsou obvykle kódovány jako nekonečné smyčky.^[2]Většina podprogramů je však určena k dokončení (zastavení).^[3]Zejména v tvrdé výpočet v reálném čase, programátoři se pokoušejí psát podprogramy, u nichž je zaručeno nejen dokončení (zastavení), ale také dokončení před daným termínem.^[4]

Někdy tito programátoři používají nějaký programovací jazyk pro všeobecné účely (Turing-complete), ale pokoušejí se psát omezeným stylem - například MISRA C nebo JISKRA —To usnadňuje prokázání, že výsledné podprogramy končí před daným termínem.^{[Citace je zapotřebí ]}

Jindy tito programátoři použijí pravidlo nejmenší moci - záměrně používají počítačový jazyk, který není zcela Turingův-úplný. Často se jedná o jazyky, které zaručují dokončení všech podprogramů, například Coq.^{[Citace je zapotřebí ]}

Běžné úskalí

Problém s problémem spočívajícím v zastavení spočívá v požadavku, že rozhodovací postup musí fungovat u všech programů a vstupů. Konkrétní program se buď zastaví na daném vstupu, nebo se nezastaví. Zvažte jeden algoritmus, který vždy odpovídá „zastaví“, a druhý, který vždy odpovídá „nezastaví“. U každého konkrétního programu a vstupu odpovídá jeden z těchto dvou algoritmů správně, i když nikdo nemusí vědět, který z nich. Ani jeden algoritmus však problém zastavení obecně nevyřeší.

Existují programy (tlumočníci ), které simulují provádění jakéhokoli zdrojového kódu, který dostanou. Takové programy mohou prokázat, že se program zastaví, pokud tomu tak je: samotný tlumočník nakonec zastaví svou simulaci, což ukazuje, že původní program byl zastaven. Tlumočník se však nezastaví, pokud se nezastaví jeho vstupní program, takže tento přístup nemůže vyřešit problém zastavení, jak je uvedeno; neodpovídá úspěšně na „nezastaví se“ u programů, které se nezastaví.

Problém zastavení je teoreticky rozhodnutelný pro lineárně ohraničené automaty (LBA) nebo deterministické stroje s konečnou pamětí. Stroj s konečnou pamětí má konečný počet konfigurací, a proto jakýkoli deterministický program na něm musí nakonec buď zastavit, nebo opakovat předchozí konfiguraci:

...jakýkoli stroj v konečném stavu, pokud je zcela ponechán sám sobě, nakonec spadne do dokonale periodického opakujícího se vzoru. Doba trvání tohoto opakujícího se vzoru nesmí překročit počet vnitřních stavů stroje ... (kurzíva v originále, Minsky 1967, s. 24)

Minsky však poznamenává, že počítač s milionem malých částí, každý se dvěma stavy, by měl alespoň 2^1,000,000 možné stavy:

Toto je 1 následované asi třemi stovkami nul ... I kdyby takový stroj pracoval na frekvencích kosmického záření, věky galaktického vývoje by byly ve srovnání s dobou cesty takovým cyklem jako nic ( Minsky 1967 s. 25):

Minsky uvádí, že i když stroj může být konečný, a konečné automaty „mají řadu teoretických omezení“:

... zúčastněné veličiny by měly vést k podezření, že věty a argumenty založené hlavně na pouhé konečnosti stavového diagramu nemusí mít velký význam. (Minsky str.25)

Rovněž lze automaticky rozhodnout, zda nedeterministický stroj s konečnou pamětí zastaví na žádném, na některých nebo na všech možných posloupnostech nedeterministických rozhodnutí, vyčíslením stavů po každém možném rozhodnutí.

Dějiny

Tato sekce je v seznam formát, ale může číst lépe jako próza. Můžete pomoci převod této části, Pokud je to vhodné. Nápověda k úpravám je k dispozici. (Únor 2020)

Problém zastavení je historicky důležitý, protože to byl jeden z prvních problémů, který se prokázal nerozhodnutelný. (Turingův důkaz byl uveden do tisku v květnu 1936) Alonzo Church Důkaz nerozhodnutelnosti problému v EU lambda kalkul byly již publikovány v dubnu 1936 [Church, 1936].) Následně bylo popsáno mnoho dalších nerozhodnutelných problémů.

Časová osa

• 1900: David Hilbert klade svých "23 otázek" (nyní známých jako Hilbertovy problémy ) ve druhém Mezinárodní kongres matematiků v Paříži. „Druhým z nich bylo prokazování konzistence„Peanoovy axiomy „na kterém, jak ukázal, závisela přísnost matematiky“. (Hodges s. 83, Davisův komentář v Davis, 1965, s. 108)
• 1920–1921: Emil Post zkoumá problém zastavení pro značkovací systémy, považovat to za kandidáta na neřešitelnost. (Absolutně neřešitelné problémy a relativně nerozhodné návrhy - účet s očekáváním, Davis, 1965, str. 340–433.) Jeho neřešitelnost byla prokázána až mnohem později, a Marvin Minsky (1967).
• 1928: Hilbert přepracoval svůj „druhý problém“ na Boloňském mezinárodním kongresu. (Reid s. 188–189) Hodges tvrdí, že položil tři otázky: tj. # 1: Byla matematika kompletní? # 2: Byla matematika konzistentní? # 3: Byla matematika rozhodnutelné? (Hodges, str.91). Třetí otázka je známá jako Entscheidungsproblem (Problém s rozhodnutím). (Hodges str. 91, Penrose str. 34)
• 1930: Kurt Gödel oznamuje důkaz jako odpověď na první dvě Hilbertovy otázky z roku 1928 [srov. Reid str. 198]. „Nejprve byl [Hilbert] jen naštvaný a frustrovaný, ale pak se začal s tímto problémem pokoušet konstruktivně ... Gödel sám cítil - a ve svém příspěvku vyjádřil myšlenku -, že jeho práce nebyla v rozporu s Hilbertovým formalistickým bodem zobrazit "(Reid str. 199)
• 1931: Gödel vydává „K formálně nerozhodnutelným návrhům Principia Mathematica a souvisejících systémů I“ (přetištěno v Davis, 1965, s. 5 a dále)
• 19. dubna 1935: Alonzo Church publikuje „Neřešitelný problém teorie elementárních čísel“, ve kterém identifikuje, co to znamená pro funkci efektivně vypočítatelné. Taková funkce bude mít algoritmus a „... skutečnost, že algoritmus byl ukončen, se stane účinně známou ...“ (Davis, 1965, s. 100)
• 1936: Církev vydává první důkaz, že Entscheidungsproblem je neřešitelný. (Poznámka k problému Entscheidungs, přetištěno v Davis, 1965, str. 110.)
• 7. října 1936: Emil Post Je přijat článek "Konečné kombinované procesy. Formulace I". Post přidává do svého „zpracování“ instrukci „(C) Stop“. Nazval takový proces „typ 1 ... pokud proces, který určuje, končí pro každý konkrétní problém.“ (Davis, 1965, s. 289 a dále)
• 1937: Alan Turing papír O vypočítatelných číslech s aplikací na Entscheidungsproblem dosáhne tisku v lednu 1937 (přetištěno v Davis, 1965, s. 115). Turingův důkaz se odchyluje od výpočtu rekurzivní funkce a zavádí pojem výpočtu strojem. Stephen Kleene (1952) o tom hovoří jako o jednom z „prvních příkladů problémů s rozhodováním, které se ukázaly jako neřešitelné“.
• 1939: J. Barkley Rosser dodržuje zásadní rovnocennost „efektivní metody“ definované Gödelem, Churchem a Turingem (Rosser in Davis, 1965, s. 273, „Neformální expozice důkazů Gödelovy věty a církevní věty“)
• 1943: V novinách Stephen Kleene uvádí, že „Při sestavování úplné algoritmické teorie to, co děláme, je popsat postup ... který postup nutně končí a takovým způsobem, že z výsledku můžeme vyčíst definitivní odpověď„ Ano “nebo„ Ne “na otázka: ‚Je predikátová hodnota pravdivá? '.“
• 1952: Kleene (1952) Kapitola XIII („Computable Functions“) zahrnuje diskusi o neřešitelnosti problému zastavení u Turingových strojů a přeformuluje jej ve smyslu strojů, které se „nakonec zastaví“, tj. Zastaví: „... neexistuje žádný algoritmus pro rozhodování, zda kterýkoli daný stroj při spuštění z dané situace nakonec se zastaví. “(Kleene (1952) str. 382)
• 1952: "Martin Davis považuje za pravděpodobné, že poprvé použil výraz „problém zastavení“ v řadě přednášek, které přednesl v Control Systems Laboratory na University of Illinois v roce 1952 (dopis Davise Copelandovi ze dne 12. prosince 2001). “(poznámka pod čarou 61 v Copeland (2004), str. 40 a více)

Formalizace

Ve svém původním důkazu Turing formalizoval koncept algoritmus zavedením Turingovy stroje. Výsledek však pro ně není nijak specifický; platí stejně pro jakýkoli jiný model výpočet to je ekvivalentní ve své výpočetní síle s Turingovými stroji, jako např Markovovy algoritmy, Lambda kalkul, Poštovní systémy, registrovat stroje nebo značkovací systémy.

Důležité je, že formalizace umožňuje přímé mapování algoritmů na některé datový typ že algoritmus může operovat. Například pokud formalismus umožňuje algoritmům definovat funkce přes řetězce (například Turingovy stroje), pak by mělo existovat mapování těchto algoritmů na řetězce, a pokud formalismus umožňuje algoritmům definovat funkce přes přirozená čísla (například vypočítatelné funkce ) pak by mělo existovat mapování algoritmů na přirozená čísla. Mapování na řetězce je obvykle nejpřímější, ale řetězce nad abeceda s n postavy lze také namapovat na čísla jejich interpretací jako čísel v n-ary číselná soustava.

Reprezentace jako sada

Konvenčním znázorněním problémů s rozhodováním je sada objektů, které vlastní dotyčnou vlastnost. The zastavovací sada

K. = {(i, X) | program i zastaví se při spuštění na vstupu X}

představuje problém zastavení.

Tato sada je rekurzivně spočetné, což znamená, že existuje vypočítatelná funkce, která uvádí všechny páry (i, X) obsahuje. Doplněk této sady však není rekurzivně vyčíslitelný.^[5]

Existuje mnoho ekvivalentních formulací problému zastavení; jakákoli sada, jejíž Turingův stupeň odpovídá formulaci problému zastavení. Mezi příklady takových sad patří:

• {i | program i nakonec se zastaví při spuštění se vstupem 0}
• {i | existuje vstup X takový ten program i nakonec se zastaví při spuštění se vstupem X}.

Důkazní koncept

Důkaz, že problém zastavení není řešitelný, je a důkaz rozporem. Pro ilustraci pojmu důkazu předpokládejme, že existuje a celkový vypočítatelná funkce zastaví (f) který vrátí true, pokud je podprogram F zastaví (pokud je spuštěn bez vstupů) a v opačném případě vrátí hodnotu false. Nyní zvažte následující podprogram:

def G():    -li zastaví(G):        loop_forever()

zastaví (g) musí buď vrátit true nebo false, protože zastaví bylo považováno za celkový. Li zastaví (g) pak se vrátí true G zavolá loop_forever a nikdy se nezastaví, což je rozpor. Li zastaví (g) potom vrátí hodnotu false G zastaví, protože to nezavolá loop_forever; to je také rozpor. Celkově, zastaví (g) nemůže vrátit hodnotu pravdy, která je v souladu s tím, zda G zastaví. Proto je původní předpoklad, že zastaví is a total computable function must be false.

Volá se metoda použitá v důkazu diagonalizace - G dělá opak toho, co zastaví říká G měl by udělat. Rozdíl mezi tímto náčrtkem a skutečným důkazem je v tom, že ve skutečném důkazu je vypočítatelná funkce zastaví nebere přímo podprogram jako argument; místo toho přebírá zdrojový kód programu. Skutečný důkaz vyžaduje další práci s řešením tohoto problému. Skutečný důkaz se navíc vyhýbá přímému použití rekurze uvedené v definici G.

Náčrt důkazu

Koncept výše ukazuje obecnou metodu důkazu; v této části budou uvedeny další podrobnosti. Celkovým cílem je ukázat, že neexistuje celkový vypočítatelná funkce který rozhodne, zda je libovolný program i zastaví se při libovolném vstupu X; tj. následující funkce h nelze vypočítat (Penrose 1990, s. 57–63):

${displaystyle h (i, x) = {egin {cases} 1 & {ext {if}} {ext {program}} i {ext {zastaví se na vstupu}} x, 0 a {ext {jinak.}} konec {případů }}}$

Tady program i Odkazuje na i th program v výčet všech programů pevné Turing-kompletní model výpočtu.

Důkaz probíhá přímým stanovením, že požadovanou funkcí nemůže být žádná celková vypočítatelná funkce se dvěma argumenty h. Stejně jako v náčrtu konceptu, vzhledem k jakékoli celkové vypočítatelné binární funkci F, následující částečná funkce G je také vypočítatelný nějakým programem E:

${displaystyle g (i) = {egin {cases} 0 & {ext {if}} f (i, i) = 0, {ext {undefined}} & {ext {jinak.}} end {cases}}}$

Ověření G is computable spoléhá na následující konstrukty (nebo jejich ekvivalenty):

• vypočítatelné podprogramy (program, který počítá F je podprogram v programu E),
• duplikace hodnot (program E počítá vstupy i,i pro F ze vstupu i pro G),
• podmíněné větvení (program E vybere mezi dvěma výsledky v závislosti na hodnotě, kterou vypočítá F(i,i)),
• neprodukovat definovaný výsledek (například opakováním navždy),
• vrácení hodnoty 0.

Následující pseudo kód ilustruje přímý způsob výpočtu G:

postup compute_g(i):    -li F(i, i) == 0 pak        vrátit se 0    jiný        smyčka navždy

Protože G je částečně vypočítatelný, musí existovat program E který počítá G, za předpokladu, že model výpočtu je Turingův úplný. Tento program je jedním ze všech programů, u nichž funkce zastavení h je definováno. Další krok důkazu to ukazuje h(E,E) nebude mít stejnou hodnotu jako F(E,E).

Vyplývá to z definice G že přesně jeden z následujících dvou případů musí platit:

• F(E,E) = 0 a tak G(E) = 0. V tomto případě h(E,E) = 1, protože program E zastaví se na vstupu E.
• F(E,E) ≠ 0 a tak G(E) není definováno. V tomto případě h(E,E) = 0, protože program E nezastaví se na vstupu E.

V obou případech F nemůže být stejná funkce jako h. Protože F byl libovolný celkem vypočítatelná funkce se dvěma argumenty, všechny tyto funkce se musí lišit od h.

Tento důkaz je analogický k Cantorův diagonální argument. Jeden může vizualizovat dvourozměrné pole s jedním sloupcem a jedním řádkem pro každé přirozené číslo, jak je uvedeno v tabulce výše. Hodnota F(i,j) je umístěn ve sloupci i, řádek j. Protože F se předpokládá, že je celkem vypočítatelnou funkcí, lze jakýkoli prvek pole vypočítat pomocí F. Konstrukce funkce G lze vizualizovat pomocí hlavní úhlopříčky tohoto pole. Pokud má pole 0 na pozici (i,i), pak G(i) je 0. Jinak, G(i) není definováno. Rozpor vychází ze skutečnosti, že existuje nějaký sloupec E pole odpovídající G sám. Nyní předpokládejme F byla funkce zastavení h, pokud G(E) je definováno (G(E) = 0 v tomto případě), G(E) zastaví se F(e, e) = 1. Ale G(E) = 0, pouze když F(e, e) = 0, je v rozporu F(e, e) = 1. Podobně, pokud G(E) není definován, pak funkce zastavení F(e, e) = 0, což vede k G(E) = 0 pod G's konstrukcí. To je v rozporu s předpokladem G(E) není definován. V obou případech vzniká rozpor. Proto libovolná vypočítatelná funkce F nemůže být funkce zastavení h.

Teorie vypočítatelnosti

Typickou metodou prokázání nerozhodnutelnosti problému je technika snížení^{[je zapotřebí objasnění ]}. K tomu stačí ukázat, že pokud by bylo nalezeno řešení nového problému, mohlo by být použito k rozhodnutí o nerozhodnutelném problému transformací instancí nerozhodnutelného problému na instance nového problému. Protože to už víme Ne metoda může rozhodnout o starém problému, žádná metoda nemůže rozhodnout ani o novém problému. Nový problém se často redukuje na řešení problému zastavení. (Stejná technika se používá k prokázání, že problém je NP kompletní, pouze v tomto případě namísto prokázání, že neexistuje žádné řešení, prokazuje, že žádné neexistuje polynomiální čas řešení za předpokladu P ≠ NP.)

Například jedním z důsledků nerozhodnutelnosti problému zastavení je, že nemůže existovat obecný algoritmus to rozhoduje, zda dané prohlášení o přirozená čísla je pravda nebo nepravda. Důvodem je to, že tvrzení tvrzení, že určitý program se zastaví s určitým vstupem, lze převést na ekvivalentní prohlášení o přirozených číslech. Pokud bychom měli algoritmus, který by dokázal najít pravdivostní hodnotu každého výroku o přirozených číslech, určitě by našel pravdivostní hodnotu tohoto; ale to by určovalo, zda se původní program zastaví, což je nemožné, protože problém se zastavením je nerozhodnutelný.

Riceova věta zobecňuje teorém, že problém zastavení je neřešitelný. Uvádí se v něm, že žádný netriviální vlastnost, neexistuje žádný obecný rozhodovací postup, který by pro všechny programy rozhodoval, zda má dílčí funkce implementovaná vstupním programem tuto vlastnost. (Částečná funkce je funkce, která nemusí vždy přinést výsledek, a tak se používá k modelování programů, které mohou přinést výsledky nebo se nezastaví.) Například vlastnost „halt pro vstup 0“ je nerozhodnutelná. Zde „netriviální“ znamená, že množina dílčích funkcí, které splňují vlastnost, není ani prázdnou množinou, ani množinou všech dílčích funkcí. Například „zastaví nebo se nezastaví na vstupu 0“ jasně platí pro všechny dílčí funkce, je to tedy triviální vlastnost a lze o něm rozhodnout pomocí algoritmu, který jednoduše nahlásí „true“. Tato věta platí pouze pro vlastnosti částečné funkce implementované programem; Riceova věta se nevztahuje na vlastnosti samotného programu. Například „zastavit na vstupu 0 do 100 kroků“ je ne vlastnost částečné funkce, která je implementována programem - je to vlastnost programu implementujícího částečnou funkci a je velmi rozhodovatelná.

Gregory Chaitin definoval a pravděpodobnost zastavení, představovaný symbolem Ω, typ reálného čísla, o kterém se neformálně říká, že představuje pravděpodobnost že náhodně vytvořený program zastaví. Tato čísla jsou stejná Turingův stupeň jako problém zastavení. Je to normální a transcendentní číslo který může být definována ale nemůže být úplně vypočítané. To znamená, že lze dokázat, že žádný neexistuje algoritmus který vytváří číslice Ω, i když prvních několik číslic lze vypočítat v jednoduchých případech.

Zatímco Turingův důkaz ukazuje, že nemůže existovat žádná obecná metoda nebo algoritmus k určení, zda se algoritmy zastaví, jednotlivé instance tohoto problému mohou být velmi dobře náchylné k útoku. Vzhledem k určitému algoritmu lze často ukázat, že se musí zastavit pro jakýkoli vstup a ve skutečnosti počítačoví vědci často to dělají jen jako součást a důkaz správnosti. Ale každý důkaz musí být vyvinut speciálně pro daný algoritmus; tady není žádný mechanickým, obecným způsobem k určení, zda se algoritmy na Turingově stroji zastaví. Existují však některé heuristika které lze automatizovaným způsobem použít k pokusu o vytvoření důkazu, který na typických programech často uspěje. Tato oblast výzkumu je známá jako automatizovaná analýza ukončení.

Vzhledem k tomu, že negativní odpověď na problém zastavení ukazuje, že existují problémy, které nelze vyřešit Turingovým strojem, Církev – Turingova teze omezuje to, čeho lze dosáhnout jakýmkoli strojem, který implementuje efektivní metody. Ne všechny stroje myslitelné lidskou představivostí však podléhají téze Church-Turing (např. věštecké stroje ). Je otevřenou otázkou, zda mohou existovat skutečné deterministické fyzikální procesy že v dlouhodobém horizontu uniká simulaci Turingovým strojem, a zejména zda lze jakýkoli takový hypotetický proces užitečně využít ve formě počítacího stroje (a hyperpočítač ), který by mohl mimo jiné vyřešit problém zastavení u Turingova stroje. Je také otevřenou otázkou, zda jsou do práce systému zapojeny nějaké takové neznámé fyzikální procesy lidský mozek a zda mohou lidé vyřešit problém zastavení (Copeland 2004, s. 15).

Gödelovy věty o neúplnosti

Koncepty vznesené Gödelovy věty o neúplnosti jsou velmi podobné těm, které vznesl problém zastavení, a důkazy jsou docela podobné. Slabší forma věty o první neúplnosti je ve skutečnosti snadným důsledkem nerozhodnutelnosti problému zastavení. Tato slabší forma se liší od standardního tvrzení věty o neúplnosti tvrzením, že an axiomatizace z přirozených čísel, která je úplná i zvuk je nemožné. „Zvukovou“ částí je oslabení: to znamená, že požadujeme pouze prokázání příslušného axiomatického systému skutečný výroky o přirozených číslech. Protože to naznačuje zdravost konzistence, na tuto slabší formu lze pohlížet jako na důsledek silné formy. Je důležité poznamenat, že tvrzení o standardní formě Gödelovy věty o první neúplnosti se zcela netýká pravdivostní hodnoty tvrzení, ale týká se pouze otázky, zda je možné jej najít prostřednictvím matematický důkaz.

Slabší formu věty lze prokázat z nerozhodnutelnosti problému zastavení následovně. Předpokládejme, že máme zdravý (a tedy konzistentní) a úplný axiomatizace pravda logika prvního řádu prohlášení o přirozená čísla. Pak můžeme vytvořit algoritmus, který vyjmenuje všechny tyto příkazy. To znamená, že existuje algoritmus N(n) že vzhledem k přirozenému číslu n, spočítá pravdivý logický příkaz prvního řádu o přirozených číslech a pro všechny pravdivé příkazy existuje alespoň jeden n takhle N(n) poskytuje toto prohlášení. Nyní předpokládejme, že se chceme rozhodnout, zda algoritmus s reprezentací A zastaví se na vstupu i. Víme, že toto tvrzení lze vyjádřit například logickým příkazem prvního řádu H(A, i). Protože je axiomatizace úplná, vyplývá z toho, že buď existuje n takhle N(n) = H(A, i) nebo existuje n ' takhle N(n ') = ¬ H(A, i). Takže pokud opakovat nade vše n dokud buď nenajdeme H(A, i) nebo jeho popření, vždy se zastavíme a navíc odpověď, kterou nám dá, bude pravdivá (podle spolehlivosti). To znamená, že nám to dává algoritmus k rozhodnutí o problému zastavení. Jelikož víme, že takový algoritmus nemůže existovat, vyplývá z toho, že předpoklad, že existuje konzistentní a úplná axiomatizace všech pravdivých logických tvrzení prvního řádu o přirozených číslech, musí být nepravdivý.

Zobecnění

Mnoho variant problému zastavení lze nalézt v učebnicích vypočítatelnosti (např.Sipser 2006, Davis 1958, Minsky 1967, Hopcroft a Ullman 1979, Börger 1989). Jejich nerozhodnutelnost obvykle následuje snížení ze standardního problému zastavení. Některé z nich však mají vyšší stupeň neřešitelnosti. Další dva příklady jsou typické.

Zastavení na všech vstupech

The univerzální problém zastavení, také známý (v teorie rekurze ) tak jako celek, je problém určit, zda se daný počítačový program zastaví pro každý vstup (název celek pochází z ekvivalentní otázky, zda je vypočítaná funkce celkový Tento problém je nejen nerozhodnutelný jako problém zastavení, ale také vysoce nerozhodnutelný. Z hlediska aritmetická hierarchie, to je ${displaystyle Pi _ {2} ^ {0}}$- kompletní (Börger 1989, s. 121).

To zejména znamená, že o něm nelze rozhodnout ani s věštec za problém zastavení.

Uznáváme dílčí řešení

Existuje mnoho programů, které u některých vstupů vracejí správnou odpověď na problém zastavení, zatímco u jiných vstupů vůbec nevracejí odpověď. Problém je však „daný program p, je to řešení částečného zastavení "(v popsaném smyslu) je přinejmenším stejně těžké jako problém zastavení. Chcete-li to vidět, předpokládejte, že k tomu existuje algoritmus PHSR (" rozpoznávač řešení částečného zastavení "). Pak to může použít k vyřešení problému zastavení, a to následovně: Otestovat, zda je zadán program X zastaví se y, vytvořit program p že na vstupu (X,y) zprávy skutečný a odchyluje se od všech ostatních vstupů. Poté proveďte test p s PHSR.

Výše uvedený argument je a snížení zastavení problému s PHS rozpoznáním a stejným způsobem i těžší problémy jako např zastavení na všech vstupech lze také snížit, což znamená, že rozpoznávání PHS je nejen nerozhodnutelné, ale vyšší v EU aritmetická hierarchie konkrétně ${displaystyle Pi _ {2} ^ {0}}$-kompletní.

Ztrátový výpočet

A ztrátový Turingův stroj je Turingův stroj, ve kterém může část pásky nedeterministicky zmizet. Problém se zastavením je rozhodnutelný pro ztrátový Turingův stroj, ale neprimitivní rekurzivní.^[6]:92

Stroje Oracle

Stroj s věštec pro problém zastavení lze určit, zda se konkrétní Turingovy stroje zastaví na konkrétních vstupech, ale obecně nemohou určit, zda se zastaví stroje rovnocenné sobě samým.

Viz také

• Zaneprázdněný bobr
• Gödelova věta o neúplnosti
• Brouwer-Hilbert kontroverze
• Kolmogorovova složitost
• Problém P versus NP
• Analýza ukončení
• Nejhorší doba provedení

Poznámky

Reference

• Alan Turing, Na vypočítatelných číslech, s aplikací na Entscheidungsproblem, Sborník řízení London Mathematical Society, Série 2, svazek 42 (1937), str. 230–265, doi:10.1112 / plms / s2-42.1.230. - Alan Turing, Na vypočítatelných číslech s aplikací na problém Entscheidungs. Oprava, Proceedings of the London Mathematical Society, Series 2, svazek 43 (1938), str. 544–546, doi:10,1112 / plms / s2-43,6,544 . Bezplatná online verze obou částí Toto je epochální papír, který definuje Turing Turingovy stroje, formuluje problém zastavení a ukazuje, že jej (stejně jako Entscheidungsproblem ) je neřešitelný.
• Sipser, Michael (2006). „Část 4.2: Problém zastavení“. Úvod do teorie výpočtu (Druhé vydání.). PWS Publishing. str.173–182. ISBN  0-534-94728-X.
• c2: HaltingProblem
• Church, Alonzo (1936). "Neřešitelný problém elementární teorie čísel". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR  2371045.
• B. Jack Copeland vyd. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN  0-19-825079-7.
• Davis, Martin (1965). Nerozhodnutelné, základní příspěvky k nerozhodnutelným návrhům, nevyřešitelným problémům a vypočítatelným funkcím. New York: Raven Press.. Turingův papír je v tomto svazku číslo 3. Články zahrnují příspěvky od Godel, Church, Rosser, Kleene a Post.
• Davis, Martin (1958). Vyčíslitelnost a neřešitelnost. New York: McGraw-Hill..
• Alfred North Whitehead a Bertrand Russell, Principia Mathematica to * 56, Cambridge at the University Press, 1962. Re: Problém paradoxů, autoři diskutují o problému množiny, která nesmí být předmětem žádné z jejích „určujících funkcí“, zejména „Úvod, kap. 1 s. 24 „... obtíže, které vyvstávají ve formální logice“, a kapitola 2.I. „Princip začarovaného kruhu“ s. 37 a následující, kap. 2.VIII. „Protiklady“ s. 60 a další.
• Martin Davis "Co je to výpočet", v Matematika dnes, Lynn Arthur Steen, Vintage Books (Random House), 1980. Nádherný malý papír, možná vůbec nejlepší napsaný o Turingových strojích pro neodborníky. Davis redukuje Turingův stroj na mnohem jednodušší model založený na Postově modelu výpočtu. Diskutuje Chaitin důkaz. Zahrnuje malé biografie Emil Post, Julia Robinson.
• Marvin Minsky, Výpočet: Konečné a nekonečné stroje„Prentice-Hall, Inc., N.J., 1967. Viz kapitola 8, část 8.2„ Neřešitelnost problému zastavení “.
• Roger Penrose, Císařova nová mysl: Co se týče počítačů, myslí a zákonů fyziky, Oxford University Press, Oxford England, 1990 (s opravami). Srov. Kapitola 2, „Algoritmy a Turingovy stroje“. Příliš komplikovaná prezentace (lepší model viz Davisův článek), ale důkladná prezentace Turingových strojů a problému zastavení a Churchova Lambda kalkulu.
• John Hopcroft a Jeffrey Ullman, Úvod do teorie automatů, jazyků a výpočtu„Addison-Wesley, Reading Mass, 1979. Viz kapitola 7„ Turing Machines “. Kniha zaměřená na strojovou interpretaci „jazyků“, NP-úplnost atd.
• Andrew Hodges, Alan Turing: Záhada, Simon a Schuster, New York. Srov. Kapitola „Duch pravdy“ pro historii vedoucí k jeho důkazu a diskusi o něm.
• Constance Reid, Hilbert„Copernicus: Springer-Verlag, New York, 1996 (poprvé publikováno v roce 1970). Fascinující historie německé matematiky a fyziky od 80. do 30. let. Na jejích stránkách se objevují stovky známých matematiků, fyziků a inženýrů. Možná poznamenáno žádnými zjevnými odkazy a několika poznámkami pod čarou: Reid uvádí, že jejími zdroji byly četné rozhovory s těmi, kteří osobně znali Hilberta, a Hilbertovy dopisy a noviny.
• Edward Beltrami, Co je to Random? Šance a pořádek v matematice a životě„Copernicus: Springer-Verlag, New York, 1999. Pěkné, jemné čtení pro matematicky nakloněného neodborníka, přináší na konec tvrdší věci. Má model Turingova stroje. Diskutuje o Chaitin příspěvky.
• Moore, Cristopher; Mertens, Stephan (2011), Povaha výpočtu, Oxford University Press, ISBN  9780191620805
• Ernest Nagel a James R. Newman, Godelův důkaz„New York University Press, 1958. Úžasné psaní o velmi obtížném tématu. Pro matematicky inklinujícího neodborníka. Diskutuje Gentzen důkaz na stranách 96–97 a poznámky pod čarou. Dodatky pojednávají o Peanoovy axiomy stručně, jemně seznamte čtenáře s formální logikou.
• Taylor Booth, Sekvenční stroje a teorie automatů, Wiley, New York, 1967. Srov. Kapitola 9, Turingovy stroje. Obtížná kniha určená pro elektrotechniky a technické specialisty. Diskutuje o rekurzi, částečné rekurzi s odkazem na Turingovy stroje, zastavení problému. Má Turingův stroj model v něm. Odkazy na konci kapitoly 9 zachycují většinu starších knih (tj. 1952 až 1967 včetně autorů Martina Davise, F. C. Hennieho, H. Hermese, S. C. Kleeneho, M. Minskyho, T. Rada) a různé technické práce. Viz poznámka pod programy Busy-Beaver.
• Busy Bobr Programy jsou popsány v časopise Scientific American, srpen 1984, také březen 1985 str. 23. Odkaz v Boothovi je připisuje Radovi, T. (1962), On non-computable functions, Bell Systems Tech. J. 41. Booth také definuje Radův problém Busy Beaver v úlohách 3, 4, 5, 6 kapitoly 9, s. 396.
• David Bolter, Turing’s Man: Western Culture in the Computer Age„The University of North Carolina Press, Chapel Hill, 1984. Pro běžného čtenáře. Může být datováno. Má ještě další (velmi jednoduchý) model Turing Machine.
• Egon Börger. "Vyčíslitelnost, složitost, logika". Severní Holandsko, 1989.
• Stephen Kleene, Úvod do matematiky„North-Holland, 1952. Kapitola XIII („ Computable Functions “) zahrnuje diskusi o neřešitelnosti problému zastavení u Turingových strojů. Na rozdíl od Turingovy terminologie bezkruhových nonhaltingových strojů Kleene místo toho odkazuje na stroje, které se „zastaví“, tj. Zastaví.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, O aproximaci problémů se zastavením v reálném světě, str. 454-466 (2005) ISBN  3540281932 Springer Lecture Notes in Computer Science volume 3623: Nerozhodnutelnost problému zastavení znamená, že ne všechny instance mohou být zodpovězeny správně; ale možná „někteří“, „mnozí“ nebo „většina“ mohou? Na jedné straně bude neustálá odpověď „ano“ nekonečně často správná a nesprávná také nekonečně často. Aby byla otázka přiměřená, zvažte hustota případů, které lze vyřešit. Ukázalo se, že to významně závisí na Programovací systém v úvahu.
• Logická omezení etiky strojů s důsledky smrtících autonomních zbraní - příspěvek diskutovaný v: Znamená problém se zastavením žádné morální roboty?
• Nicholas J. Daras a Themistocles M. Rassias, Moderní diskrétní matematika a analýza: s aplikacemi v kryptografii, informačních systémech a modelování Springer, 2018. ISBN  978-3319743240. Chapter 3 Section 1 contains a quality description of the halting problem, a proof by contradiction, and a helpful graphic representation of the Halting Problem.

externí odkazy

• Scooping the loop snooper - a poetic proof of undecidability of the halting problem
• animovaný film - an animation explaining the proof of the undecidability of the halting problem
• A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium - a proof in only 13 lines