Nerozhodnutelný problém

Nerozhodnutelný problém je v teorii vyčíslitelnosti a teorii složitosti takový rozhodovací problém, pro který není možné zkonstruovat algoritmus, který vždy vydá správnou odpověď ano nebo ne. Příkladem je problém zastavení: lze dokázat, že neexistuje žádný algoritmus, který o libovolném programu rozhodne, zda se po svém spuštění na daných datech zastaví.

Protože pojem algoritmus není přesně definován, tvrzení o existenci nerozhodnutelných problémů zpravidla používají nějakou dobře definovanou formu algoritmu, např. Turingův stroj. +more Na druhou stranu princip jejich důkazu (důkaz diagonalizací) vychází ze zjištění, že existuje mnoho problémů a jen určitá část z nich jsou rozhodnutelné problémy.

Pozadí

Rozhodovací problém je libovolná otázka s parametrem nabývajícím nekonečně mnoha hodnot, na níž je odpověď „ano“ nebo „ne“, která závisí na hodnotě parametru. Rozhodovací problém se tradičně definuje jako množina hodnot parametru (neboli vstupů), pro které je odpověď ano. +more Parametrem (vstupem) může být přirozené číslo nebo hodnota jiného druhu, například textové řetězce formálního jazyka. Pomocí nějakého kódování, například Gödelova číslování, lze však řetězce vždy kódovat pomocí přirozených čísel. Rozhodovací problém neformálně formulovaný pomocí formálního jazyka je tedy ekvivalentní s množinou přirozených čísel. Pro zjednodušení formální definice se používá terminologie podmnožin přirozených čísel.

Každý rozhodovací problém lze formálně chápat jako problém náležení do nějaké podmnožiny množiny přirozených čísel. Odpovídajícím neformálním problémem je rozhodování, zda dané číslo patří do určité množiny. +more Rozhodovací problém A se nazývá rozhodnutelný nebo efektivně řešitelný, pokud A je rekurzivní množina, a nerozhodnutelný jinak. Problém se nazývá částečně rozhodnutelný, semi-rozhodnutelný, řešitelný nebo dokazatelný, pokud A je rekurzivně spočetná množina.

Příklad: problém zastavení v teorii vyčíslitelnosti

V teorii vyčíslitelnosti je problém zastavení rozhodovací problém, který lze formulovat takto:

:Pro popis libovolného programu a konečný vstup rozhodnout, zda výpočet programu na daném vstupu skončí nebo bude pokračovat donekonečna.

Alan Turing v roce 1936 dokázal, že je možné sestrojit univerzální Turingův stroj, který simuluje činnost libovolného Turingova stroje, že však není možné sestrojit Turingův stroj, který rozhoduje problém zastavení univerzálního Turingova stroje (Turingova věta). Tedy, že problém zastavení je pro Turingovy stroje nerozhodnutelný.

Vztah s Gödelovou větou o neúplnosti

Důsledky vyplývající z Gödelových vět o neúplnosti jsou velmi podobné problému zastavení, a důkazy jsou docela podobné. Slabší tvar první věty o neúplnosti je vlastně jednoduchým důsledkem nerozhodnutelnosti problému zastavení. +more Tento slabší tvar se odlišuje od standardního tvrzení věty o neúplnosti tvrzením, že není možná axiomatizace přirozených čísel, která by byla jak úplná tak korektní. Část o „korektnosti“ tvrzení oslabuje: znamená, že vyžadujeme, aby příslušný axiomatický systém dokazoval pouze pravdivá tvrzení o přirozených číslech. Protože korektnost implikuje bezespornost, lze tento slabší tvar chápat jako důsledek silného tvaru. Je důležité vědět, že tvrzení Gödelovy první věty o neúplnosti se vůbec nezabývá pravdivostní hodnotou tvrzení, ale pouze otázkou, zda je možné její nalezení matematickým důkazem.

Slabší tvar věty lze dokázat z nerozhodnutelnosti problému zastavení: Předpokládejme, že máme korektní (a tedy konzistentní) a úplnou axiomatizaci všech pravdivých tvrzení predikátové logiky prvního řádu o přirozených číslech. Pak můžeme vytvořit algoritmus, který všechna tato tvrzení vyčísluje. +more To znamená, že existuje algoritmus N(n), který, pro libovolné přirozené číslo n vrátí pravdivé tvrzení o přirozených číslech v logice prvního řádu, a že ke každému pravdivému tvrzení existuje alespoň jedno n takové, že N(n) dává toto tvrzení. Nyní předpokládejme, že chceme rozhodnout, zda algoritmus s reprezentací a zastaví na vstupu i. Víme, že toto tvrzení lze vyjádřit tvrzením v logice prvního řádu, např. H(A, i). Pokud je axiomatizace úplná, pak buď existuje n takové, že N(n) = H(A, i) anebo existuje n' takové, že N(n') = ¬ H(A, i). Můžeme tedy iterovat přes všechna n, dokud nedostaneme H(A, i) nebo jeho negaci; výpočet vždy skončí, a odpověď, kterou nám dává, bude pravdivá (díky korektnosti). To znamená, že máme algoritmus rozhodující problém zastavení. Protože víme, takový algoritmus nemůže existovat, znamená to, že předpoklad, že existuje konzistentní a úplná axiomatizace všech pravdivých tvrzení o přirozených číslech v logice prvního řádu, musí být nepravdivý.

Příklady nerozhodnutelných problémů

Nerozhodnutelné problémy se mohou týkat různých oborů, jako například logiky, abstraktních strojů nebo topologie. Protože existuje nespočetně mnoho nerozhodnutelných problémů,Existuje nespočetně mnoho podmnožin \{0,1\}^*, ale pouze spočetně mnoho z nich lze rozhodnout pomocí algoritmů. +more Ale v jakémkoli jazyce lze formulovat pouze spočetně mnoho rozhodovacích problémů. jakýkoli seznam, dokonce i seznam nekonečné délky, je nutně neúplný.

Příklady nerozhodnutelné tvrzení

V současnosti se používají dva různé významy slova „nerozhodnutelný“. První souvisí s Gödelovou větou, a týká se tvrzení, které v určitém deduktivním systému nelze ani dokázat ani vyvrátit. +more Druhý význam se používá v teorii vyčíslitelnosti a netýká se tvrzení, ale rozhodovacích problémů, což jsou spočetně nekonečné množiny otázek, které vyžadují odpověď ano nebo ne. Rozhodovací problém se nazývá nerozhodnutelný, pokud neexistuje žádná vyčíslitelná funkce, která správně odpovídá na každou otázku v sadě problémů. Spojení mezi těmito dvěma významy je, že pokud rozhodovací problém je nerozhodnutelný (v rekurzivně-teoretickém smyslu) pak neexistuje žádný konzistentní, efektivní formální systém, který umožňuje odpovědět na každou otázku A v problému buď „odpověď na A je ano“ anebo „odpověď na A je ne“.

Kvůli dvěma významům slova nerozhodnutelný se někdy místo nerozhodnutelný ve smyslu „ani dokazatelný ani vyvratitelný“ používá termín nezávislý. Použití slova „nezávislý“ je však také nejednoznačné. +more Může znamenat pouze „nedokazatelný“, přičemž zůstává otevřené, zda konkrétní nezávislé tvrzení je možné zamítnout.

Nerozhodnutelnost tvrzení v určitém deduktivním systém neodpovídá na otázku, zda je pravdivostní hodnota tvrzení dobře definovaná nebo zda o ní lze rozhodnout jinými prostředky. Nerozhodnutelnost pouze implikuje, že v rámci určitého deduktivního systému nelze pravdivost nebo nepravdivost určitého tvrzení dokázat. +more Zda existuje nějaké „absolutně nerozhodnutelné“ tvrzení, jehož pravdivostní hodnota nemůže být nikdy známa nebo je chybně zadané, je kontroverzním bodem různých filozofických škol.

Jedním z prvních problémů podezřelých, že jsou nerozhodnutelné ve druhém významu, byl slovní problém grup, který poprvé zmiňuje Max Dehn v roce 1911. Dehn položil otázku, zda existuje konečně prezentovaná grupa, pro kterou neexistuje žádný algoritmus, který by určil, zda dvě slova jsou ekvivalentní. +more Že jde o nerozhodnutelný problém, bylo dokázáno v roce 1955.

Kombinace prací Gödela a Paula Cohena dala dva konkrétní příklady nerozhodnutelných tvrzení (v prvním významu): hypotézu kontinua nelze dokázat ani vyvrátit ve standardní axiomatizaci teorie množin - Zermelově-Fraenkelově teorii množin (značené ZFC), a v Zermelově-Fraenkelově teorii množin bez axiomu výběru (značené ZF) nelze dokázat ani zamítnout axiom výběru. Žádný z těchto výsledků nevyžaduje větu o neúplnosti. +more Gödel v roce 1940 dokázal, že žádné z těchto tvrzení nelze vyvrátit v ZF nebo ZFC. V 60. letech 20. století dokázal Cohen, že ani jedno nelze dokázat z ZF, a že hypotézu kontinua nelze ověřit v ZFC.

V roce 1970 ruský matematik Jurij Vladimirovič Matijasevič zjistil, že Hilbertův desátý problém, který byl v roce 1900 představen jako jedna z výzev pro matematiky dalšího století, není možné vyřešit. Hilbertův desátý problém se týká algoritmu, který by hledal všechna řešení Diofantické rovnice. +more Diofantická rovnice je obecnějším případem Velké Fermatovy věta; hledáme celočíselné kořeny polynomu s celočíselnými koeficienty s jakýmkoli počtem proměnných. Protože máme pouze jednu rovnici s n neznámými, v komplexní rovině existuje nekonečně mnoho řešení (která lze snadno nalézt); pokud však hledáme pouze celočíselná řešení, problém se stane neřešitelným. Matijasevič zobrazením Diofantické rovnice na rekurzivně spočetnou množinu a použitím Gödelovy věty o neúplnosti dokázal, že tento problém je neřešitelný.

Alan Turing v roce 1936 dokázal, že Problém zastavení - otázka, zda Turingův stroj zastaví na daném vstupu - je nerozhodnutelná ve druhém významu. Tento výsledek byl později zobecněn v Riceově větě.

V roce 1973, Saharon Šelach dokázal, že Whiteheadův problém v teorii grup je ve standardní teorii množin nerozhodnutelný v prvním významu.

Paris a Harrington dokázali v roce 1977, že Parisův-Harringtonův princip, což je verze Ramseyovy věty, je nerozhodnutelný v axiomatizaci aritmetiky pomocí Peanových axiomů, ale lze jej dokázat ve větším systému aritmetiky druhého řádu.

Kruskalova věta o stromě, která má aplikace v matematické informatice, je také nerozhodnutelná z Peanových axiomů, ale je dokazatelná v teorii množin. Kruskalova věta o stromě (nebo její konečný tvar) je nerozhodnutelná také v mnohem silnějším systému, který kodifikuje principy přijatelné na základě filozofie matematiky nazývané predikativismus.

Goodsteinova věta je tvrzení Ramseyho teorie o přirozených číslech, o kterém Kirby a Paris dokázali, že je nerozhodnutelné v Peanově aritmetice.

Gregory Chaitin vytvořil nerozhodnutelné tvrzení v algoritmické teorii informace a dokázal jinou větu o neúplnosti pro tento případ. Chaitinova věta tvrdí, že pro jakoukoli teorii, které může dostatečně reprezentovat aritmetiku, existuje horní mez c taková, že pro žádné určité číslo nelze v této teorii dokázat, že má Kolmogorovskou složitost větší než c. +more Zatímco Gödelova věta je příbuzný s paradoxem lháře, Chaitinův výsledek je příbuzný s paradoxem sta slov.

Kurtz a Simon v roce 2007 na základě dřívější práce J. H. +more Conwaye ze 70. let 20. století dokázali, že přirozené zobecnění Collatzova problému je nerozhodnutelné.

Odkazy

Reference

Literatura

Související články

Rozhodnutelnost * Entscheidungsproblem * Důkaz nemožnosti * Zapeklitý problém

Kategorie:Matematická logika Kategorie:Vyčíslitelnost Kategorie:Teorie složitosti Kategorie:Teoretická informatika