Vyčíslitelnost A Složitost

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Toto je soubor v archivech Stanfordské encyklopedie filozofie.

Vyčíslitelnost a složitost

První publikováno Čt 24. června 2004; věcná revize po 28. července 2008

Matematický problém lze vypočítat, pokud jej lze v zásadě vyřešit pomocí výpočetního zařízení. Některé běžné synonyma pro „kompatibilní“jsou „řešitelné“, „rozhodnutelné“a „rekurzivní“. Hilbert věřil, že všechny matematické problémy jsou řešitelné, ale ve 30. letech 20. století Gödel, Turing a Church ukázali, že tomu tak není. Existuje rozsáhlá studie a klasifikace, z nichž matematické problémy lze vyčíslit a které nikoli. Kromě toho existuje rozsáhlá klasifikace vypočítatelných problémů do tříd výpočetní složitosti podle toho, kolik výpočtů - jako funkce velikosti problémové instance - je potřeba k zodpovězení této instance. Je překvapující, jak jasně, elegantně a přesně tyto klasifikace byly vypracovány.

• 1. Co lze v zásadě spočítat? Úvod a historie

• 2. Turingovy stroje

  • 2.1 Univerzální stroje
  • 2.2 Problém zastavení
  • 2.3 Kompatibilní funkce a vyčíslitelnost
  • 2.4 Nevyřešitelnost problému zastavení
• 3. Primitivní rekurzivní funkce

• 3.1 Rekurzivní funkce

• 4. Výpočetní složitost: Funkce kompatibilní v praxi
• Bibliografie
• Další internetové zdroje
• Související záznamy

1. Co lze v zásadě spočítat? Úvod a historie

Ve třicátých letech, dávno předtím, než existovaly počítače, vymysleli různí matematici z celého světa přesné a nezávislé definice toho, co znamená být kompatibilní. Alonzo Church definoval Lambda počet, Kurt Gödel definoval rekurzivní funkce, Stephen Kleene definoval Formální systémy, Markov definoval to, co se stalo známým jako Markovovy algoritmy, Emil Post a Alan Turing definovaly abstraktní stroje nyní známé jako Post stroje a Turingovy stroje.

Je překvapivé, že všechny tyto modely jsou naprosto rovnocenné: cokoli, co je možné spočítat v lambda kalkulu, lze vypočítat Turingovým strojem a podobně pro jakékoli jiné páry výše uvedených výpočetních systémů. Poté, co bylo toto prokázáno, církev vyjádřila přesvědčení, že intuitivní pojem „v zásadě spočítatelný“je totožný s výše uvedenými přesnými pojmy. Tato víra, nyní nazývaná „církevní Turingova práce“, je matematiky jednotně přijímána.

Část podnětu pro kodifikaci toho, co je možné spočítat, přišel od matematika Davida Hilberta. Hilbert věřil, že veškerá matematika může být přesně axiomatizována. Cítil, že jakmile to bude hotovo, bude existovat „efektivní postup“, tj. Algoritmus, který bude brát jako vstup jakýkoli přesný matematický výrok, a po konečném počtu kroků rozhodne, zda je výrok pravdivý nebo nepravdivý. Hilbert žádal o to, co by se nyní nazývalo rozhodovací procedurou pro celou matematiku.

Jako zvláštní případ tohoto rozhodovacího problému zvažoval Hilbert problém platnosti pro logiku prvního řádu. Logika prvního řádu je matematický jazyk, ve kterém lze formulovat většinu matematických prohlášení. Každý výrok v logice prvního řádu má v každé vhodné logické struktuře přesný význam, tj. V každé takové struktuře je pravdivý nebo nepravdivý. Tato tvrzení, která jsou pravdivá v každé vhodné struktuře, se nazývají platná. Tato tvrzení, která jsou v určité struktuře pravdivá, se nazývají uspokojivá. Všimněte si, že vzorec Φ je platný, pokud jeho negace ¬Φ není uspokojivá.

Hilbert nazval problém platnosti pro logiku prvního řádu, entscheidungsproblem. V učebnici Principy matematické logiky Hilberta a Ackermanna autoři napsali: „Entscheidungsproblem je vyřešen, když známe proceduru, která umožňuje každému danému logickému výrazu rozhodnout konečně mnoha operacemi o jeho platnosti nebo uspokojivosti.… Entscheidungsproblem musí být považován za hlavní problém matematické logiky. “(Böerger, Grädel a Gurevich 1997).

V jeho 1930 Ph. D. práce, Gödel představil úplnou axiomatizaci logiky prvního řádu, založenou na Principia Mathematica Whiteheadem a Russellem (Gödel 1930). Gödel prokázal svou teorii úplnosti, a to, že vzorec je prokazatelný z axiomů pouze tehdy, je-li platný. Gödelova věta o úplnosti byla krokem k vyřešení Hilbertovy entscheidungsproblemu.

Zejména, protože axiomy jsou snadno rozpoznatelné a pravidla odvozování velmi jednoduchá, existuje mechanický postup, který může vyjmenovat všechny důkazy. Všimněte si, že každý řádek v důkazu je buď axiom, nebo vyplývá z předchozích řádků jedním z jednoduchých pravidel. U libovolného řetězce znaků můžeme zjistit, zda se jedná o důkaz. Můžeme tedy systematicky vypsat všechny řetězce znaků délky 1, 2, 3 atd. A zkontrolovat, zda je každý z nich důkazem. Pokud ano, můžeme přidat poslední řádek důkazu do našeho seznamu vět. Tímto způsobem můžeme vyjmenovat všechny věty, tj. Přesně všechny platné vzorce logiky prvního řádu lze vyjmenovat jednoduchým mechanickým postupem. Přesněji řečeno, sada platných vzorců je rozsahem funkce, kterou lze vypočítat. V moderní terminologii říkáme, že množina platných vzorců logiky prvního řádu je rekurzivně vyčíslitelná (re).

Gödelova věta o úplnosti však nestačila k pozitivnímu řešení problému entscheidungsproblem. Vzhledem k tomu, že vzorec Φ, pokud valid je platný, by výše uvedený postup nakonec vyjmenoval a mohl by tedy odpovědět: „Ano, Φ je platný.“Pokud by však Φ nebyly platné, pak bychom tuto skutečnost nikdy neměli zjistit. Co chybělo, byl postup pro vyjmenování všech neplatných vzorců nebo ekvivalentní vyjmenování všech vyhovujících vzorců.

O rok později, v roce 1931, Gödel šokoval matematický svět tím, že prokázal svou teorii neúplnosti: neexistuje úplná a srovnatelná axiomatizace teorie prvního řádu přirozených čísel. To znamená, že neexistuje rozumný seznam axiomů, ze kterých můžeme přesně prokázat všechna pravdivá tvrzení teorie čísel (Gödel 1931).

O několik let později, církev a Turing nezávisle prokázali, že entscheidungsproblem je neřešitelný. Církev to provedla pomocí metod Gödelovy věty o neúplnosti, aby ukázala, že množina uspokojivých vzorců logiky prvního řádu není re, tj. Nemohou být systematicky vyjmenována funkcí, kterou lze spočítat lambda. Turing představil jeho stroje a ukázal mnoho zajímavých vět, z nichž některé budeme diskutovat v další části. Zejména prokázal nevyřešitelnost problému zastavení. Nevyřešitelnost problému entscheidungsproblem získal jako důsledek.

Hilbert byl velmi zklamaný, protože jeho program směřující k rozhodovací proceduře pro celou matematiku se ukázal jako nemožný. Jak však uvidíme podrobněji ve zbývající části tohoto článku, dozvěděli jsme se velké množství informací o základní povaze výpočtu.

2. Turingovy stroje

Ve svém článku z roku 1936 „O kompatibilních číslech s aplikací u Entscheidungsproblem“představil Alan Turing své stroje a stanovil jejich základní vlastnosti.

Jasně a abstraktně přemýšlel o tom, co by to pro stroj znamenalo vykonat výpočetní úkol. Turing definoval jeho stroje sestávat z následujících:

• konečná množina Q možných stavů, protože jakékoli zařízení musí být v jednom z konečně mnoha možných stavů;

• potenciálně nekonečná páska, sestávající z po sobě jdoucích buněk, σ ₁, σ ₂, σ ₃, z nějaké konečné abecedy, Σ;

  (Σ může být libovolná konečná množina obsahující alespoň dva symboly. Je vhodné opravit Σ = {0, 1, b} skládající se z binární abecedy plus symbolu prázdné buňky. Obvykle předpokládáme, že konečný počáteční úsek pásky obsahuje binární symboly a zbytek je prázdný.)

• čtecí / zapisovací pásková hlava, h ≥ 1, skenovací pásková buňka σ _h; a nakonec,

• přechodová funkce, δ: Q × Σ → Q × Σ × {-1,0,1}.

  (Význam přechodové funkce je ten, že z jakéhokoli daného stavu, q, při pohledu na jakýkoli daný symbol, σ _h, δ nám říká nový stav, do kterého by měl stroj vstoupit, nový symbol, který by měl být zapsán na aktuální čtverec, a nová poloha hlavy, h '= h + d, kde d ∈ {-1,0,1} je posun udaný δ.)

Lineární povaha její paměťové pásky, na rozdíl od paměti s nezávislým přístupem, je omezením rychlosti výpočtu, ale nikoli výkonu: Turingův stroj může najít libovolné umístění paměti, tj. Páskovou buňku, ale to může být časově náročné, protože se musí pohybovat jeho hlava krok za krokem podél její pásky.

Krása Turingových strojů spočívá v tom, že model je extrémně jednoduchý, přesto přesto velmi silný. Turingův stroj má potenciálně nekonečný pracovní prostor, takže může zpracovávat libovolně velké vstupy, např. Znásobit dvě obrovská čísla, ale dokáže číst nebo zapisovat pouze omezené množství informací, tj. Jeden symbol, na krok. Ještě předtím, než byly Turingovy stroje a všechny ostatní matematické modely výpočtu rovnocenné, a před jakýmkoli vyjádřením teze o církvi-Turingovi Turing přesvědčivě argumentoval, že jeho stroje jsou stejně výkonné jako jakékoli jiné výpočetní zařízení.

2.1 Univerzální stroje

Každý Turingův stroj může být jedinečně popsán svou tabulkou přechodu: pro každý stav je q, a každý symbol, σ, δ (q, σ) nový stav, nový symbol a posunutí hlavy. Tyto přechodové tabulky lze napsat jako konečný řetězec symbolů, což dává kompletní sadu pokynů pro každý Turingův stroj. Dále mohou být tyto řetězce symbolů uvedeny v lexikografickém pořadí následovně: M ₁, M ₂, M ₃,…, kde M _i je přechodová tabulka, tj. Kompletní sada instrukcí, pro Turingův stroj číslo i. Přechodová tabulka pro M _i je program pro Turingův stroj i, nebo jednodušeji i-   ^tý program.

Turing ukázal, že by mohl postavit Turingův stroj, U, který byl univerzální, v tom smyslu, že mohl spustit program jakéhokoli jiného Turingova stroje. Přesněji řečeno, pro jakýkoli i a jakýkoli vstup w, U na vstupech i a w by udělal přesně to, co M _i udělal na vstupu w, ve symbolech,

U (i, w) = M _i (w)

Turingova konstrukce univerzálního stroje poskytuje nejzákladnější vhled do výpočtu: jeden stroj může spouštět jakýkoli program. Bez ohledu na to, jaké výpočetní úkoly můžeme v budoucnu potřebovat, jediný stroj je může všechny provést. To je přehled, díky kterému je možné stavět a prodávat počítače. Jeden počítač může spouštět jakýkoli program. Nepotřebujeme kupovat nový počítač pokaždé, když máme nový problém vyřešit. Ve věku osobních počítačů je tato skutečnost samozřejmě základním předpokladem, že může být obtížné ustoupit a ocenit.

2.2 Problém zastavení

Protože byly navrženy tak, aby ztělesňovaly všechny možné výpočty, Turingovy stroje mají nevyhnutelnou chybu: některé Turingovy stroje na určitých vstupech se nikdy nezastaví. Některé Turingovy stroje se nezastaví z hloupých důvodů, například můžeme Turingův stroj nesprávně naprogramovat tak, že se dostane do těsné smyčky, například ve stavu 17 při pohledu na 1 může jít do stavu 17, napsat 1 a posuneme jeho hlavu o 0. Mírně méně hloupé, můžeme dosáhnout prázdného symbolu, který má pouze prázdné symboly vpravo, a přesto zůstáváme ve stejném stavu, pohybujeme o jeden krok doprava a hledáme „1“. Oba tyto případy nepřetržitého zastavení mohly být snadno detekovány a opraveny slušným překladačem. Zvažte však Turingův stroj M _F, který na vstupu "0" systematicky vyhledává první protiklad na Fermatovu poslední větu a po jeho nalezení vydá protiklad a zastaví se. Dokud Andrew Wiles relativně nedávno neprokázal Fermatovu poslední teorém, nebyli všichni matematici na světě, kteří pracovali déle než tři století, schopni rozhodnout, zda se _MF na vstupu „0“nakonec zastaví. Teď víme, že to nikdy neudělá.

2.3 Kompatibilní funkce a vyčíslitelnost

Vzhledem k tomu, že Turingův stroj nemusí na určitých vstupech zastavit, musíme být opatrní při definování funkcí, které Turingovy stroje lze vypočítat. Ať se přirozená čísla, N, je množina {0,1,2, …} a uvažujme TS jako dílčích funkcí od N k N.

Nechť M je Turingův stroj a na přirozené číslo. Říkáme, že páska M obsahuje číslo n, pokud páska M začíná začínající binární reprezentací čísla n (bez zbytečných úvodních 0), následovanou pouhými prázdnými symboly.

Pokud spustíme Turingův stroj M na pásku obsahující n a nakonec se zastaví svou páskou obsahující m, pak řekneme, že M na vstupu n vypočítá m: M (n) = m. Pokud, když začneme M na vstupu n, buď se nikdy nezastaví, nebo když se zastaví, jeho páska neobsahuje přirozené číslo, např. Protože má úvodní 0, nebo číslice rozprostřené prázdnými symboly, pak řekneme, že M (n) není definováno, ve symbolech: M (n) =

. Můžeme tedy asociovat s každým Turingovým strojem, M, dílčí funkci, M: N → N ∪ {

}. Říkáme, že funkce M je celková, pokud pro všechny n ∈ N, M (n) ∈ N, tj. M (n) je vždy definováno.

Nyní můžeme formálně definovat, co to znamená, že množina má být rekurzivně vyčíslitelná (re), kterou jsme dříve neformálně popsali. Nechť S ⊆ N. Pak S je znovu a jen tehdy, existuje-li nějaký Turingův stroj, M, takže S je obraz funkce vypočítané M, ve symbolech,

S = {M (n) | n ∈ N; M (n) ≠

}.

S je tedy opět jen tehdy, když může být uveden některým Turingovým strojem. Předpokládejme, že S je re a jeho prvky jsou vyjmenovány Turingovým strojem M, jak je uvedeno výše. Pak můžeme popsat další Turingův stroj, P, který na vstupu n provozuje M na všech svých vstupech M až do M výstupů n. Pokud k tomu dojde, pak se P zastaví a vydá "1", tj. P (n) = 1. Pokud n ∉ S, pak M nebude nikdy vydávat n, takže P (n) se nikdy nezastaví, tj. P (n) =

Nechť zápis P (n) ↓ znamená, že se Turingův stroj P na vstupu n zastaví. Pro Turingův stroj, P, definujte L (P), soubor akceptovaný P, tak, že čísla n taková, že P na vstupu n se nakonec zastaví,

L (P) = {n | P (n) ↓}.

Výše uvedený argument ukazuje, že pokud je množina S znovu, je akceptována některým Turingovým strojem, P, tj. S = L (P). Obrátí se i toto tvrzení. To znamená, že S je znovu a pouze tehdy, pokud je akceptován některým Turingovým strojem, P.

Říkáme, že množina S je rozhodující tehdy a pouze tehdy, existuje-li totální Turingův stroj M, který pro všechny n ∈ N rozhodne, zda n ∈ S. „1“považujte za „ano“a „0“za „ne“. Pro všechny n ∈ N, pokud n ∈ S, pak M (n) = 1, tj. M na vstupu n se nakonec zastaví a na výstupu „ano“, zatímco pokud n ∉ N, pak M (n) = 0, tj. M na vstupu n se nakonec zastaví a na výstupu „ne“. Synonyma pro rozhodnutelné jsou: kompatibilní, řešitelné a rekurzivní.

Pro S ⊆ N je doplňkem S N - S, tj. Množina všech přirozených čísel ne v S. Říkáme, že množina S je souběžná pouze tehdy, je-li její doplňkem, pokud je množina, S, je znovu a souběžná, pak můžeme vyjmenovat všechny její prvky v jednom sloupci a můžeme vyjmenovat všechny její prvky non-elements ve druhém sloupci. Tímto způsobem se můžeme rozhodnout, zda daný prvek, n, je v S: jen prohledejte dva sloupce a počkejte, až se n zobrazí. Pokud se zobrazí v prvním sloupci, pak n ∈ S. Jinak se zobrazí ve druhém sloupci a n ∉ S. Ve skutečnosti je sada rekurzivní, pokud je re a co-re

2.4 Nevyřešitelnost problému zastavení

Turing se zeptal, zda je každá sada přirozených čísel rozhodnutelná. Je snadné vidět, že odpověď je „ne“, a to pomocí následujícího argumentu pro počítání. Existuje nespočetně mnoho podmnožin N, ale protože existuje jen nespočetně mnoho Turingových strojů, může existovat jen nespočetně mnoho rozhodných sad. Takřka všechny sady jsou nerozhodnutelné.

Turing ve skutečnosti vytvořil nerozhodnutelný soubor. Jak uvidíme, udělal to pomocí úhlopříčného argumentu. Diagonální argument se vrací k Georgu Cantorovi, který jej použil, aby ukázal, že skutečná čísla jsou nespočetná. Gödel použil podobný diagonální argument ve svém důkazu o teorii neúplnosti, ve kterém vytvořil větu, J, v teorii čísel, jejíž význam lze chápat jako „J není věta“.

Turing vytvořil diagonální zastavovací sadu K takto:

K = {n | M _n (n) ↓}.

To znamená, že K se skládá z těch Turingových strojů, které se nakonec zastaví, když zadají své vlastní programy.

Není těžké pochopit, že K je znovu Předpokládejme v rozporu, že K je také spolutvůrcem, a nechť d je číslo Turingova stroje, který přijímá doplněk K. To znamená pro každé n

n ∉ K ⇔ M _d  (n) ↓.

Ale zvažte, co se stane, když ve výše uvedené rovnici nahradíme d za n:

d ∉ K ⇔ M _d  (d) ↓.

Definice K nám však říká, že:

d ∈ K ⇔ M _d  (d) ↓.

Tak to máme

d ∈ K ⇔ d ∉ K,

což je rozpor. Náš předpoklad, že K je co-re, je tedy chybný. K tedy není rekurzivní. Z toho plyne, že není dáno Turingova stroji a jeho vstupům vyčíslitelný problém a rozhodnout, zda se Turingův stroj nakonec na tomto vstupu zastaví, tj. Problém zastavení je neřešitelný.

3. Primitivní rekurzivní funkce

Dále definujeme třídu primitivních rekurzivních funkcí. Toto je velmi zajímavá třída funkcí definovaná Gödelem jako součást jeho důkazu o teorii neúplnosti. Zajímáme se o funkce f od N ^r na N, pro r = 0, 1, 2,…. Zde se r nazývá arity funkce f, tj. Počet argumentů, které bere. Gödel začal se třemi velmi jednoduchými funkcemi, počátečními funkcemi a dvěma přirozenými uzavíracími operacemi, kompozicí a primitivní rekurzí, z nichž každá má některé již definované funkce a používá je k definování nové. Dále podrobně vysvětlíme jeho definice. Tato část je technická a lze ji bezpečně přeskočit. Důležitou myšlenkou je, že primitivní rekurzivní funkce zahrnují velmi velkou a výkonnou třídu vypočítatelných funkcí, všechny generované extrémně jednoduchým způsobem.

Začneme třemi počátečními primitivními rekurzivními funkcemi:

• ζ, nulová funkce arity 0, ζ () = 0;
• η, identitní funkce arity 1, η (n) = n; a,
• σ, nástupnická funkce arity 1, σ (n) = n +1.

Nyní zvažte následující dvě operace:

• Složení: jestliže f je primitivní rekurzivní funkce arity a, a g ₁, …, g jsou primitivní rekurzivní funkce aritami r ₁, …, r, a k ∈ N, pak se vkládá je primitivní rekurzivní funkce arity k:

  h (x ₁, …, x _k) = f (g ₁ (w ₁), …, g _a (w _a)),

  kde každé w _i je seznam r _i argumentů, snad s opakováním, od x ₁, …, x _k; a,

• Primitivní rekurze: jsou-li f a g primitivní rekurzivní funkce arity k a k +2, potom existuje primitivní rekurzivní funkce h, arity k +1, která splňuje následující podmínky:

  • h (0, x ₁, …, x _k) = f (x ₁, …, x _k); a,
  • h (n +1, x ₁, …, x _k) = g (h (n, x ₁, …, x _k), n, x ₁, …, x _k).

Zde je složení přirozeným způsobem, jak kombinovat funkce, a primitivní rekurze je omezený druh rekurze, ve které je h s prvním argumentem n +1 definováno jako h s prvním argumentem n, a všechny ostatní argumenty zůstávají nezměněny.

Definujte primitivní rekurzivní funkce jako nejmenší třídu funkcí, která obsahuje Počáteční funkce a je uzavřena v části Složení a Primitivní rekurze. Sada primitivních rekurzivních funkcí se rovná sadě funkcí vypočítaných pomocí omezené iterace (Meyer & Ritchie 1967), tj. Sady funkcí definovatelných v jazyce Bloop from (Hofstadter 1979).

Primitivní rekurzivní funkce mají velmi jednoduchou definici a přesto jsou extrémně silné. Gödel indukčně dokázal, že každá primitivní rekurzivní funkce může být jednoduše reprezentována v teorii čísel prvního řádu. Poté použil primitivní rekurzivní funkce k zakódování vzorců a dokonce i sekvencí vzorců čísly. Nakonec použil primitivní rekurzivní funkce k výpočtu vlastností reprezentovaných vzorců včetně toho, že vzorec byl dobře formován, posloupnost vzorců byla důkazem a že vzorec byl věta.

Ukázka toho, jak mocné jsou primitivní rekurzivní funkce, trvá dlouhou řadu lemmat. Následuje několik příkladů, které ukazují, že sčítání, množení a exponentiace jsou primitivní rekurzivní.

Funkci sčítání P (x, y) definujte následovně:

• P (0, y) = η (y)
• P (n + 1, y) = σ (P (n, y))

(Všimněte si, že to zapadá do definice primitivní rekurze, protože funkce g (x ₁, x ₂, x ₃) = η (σ (x ₁)) je definovatelná z počátečních funkcí η a σ složením.)

Dále definujte multiplikační funkci T (x, y) takto:

• T (0, y) = ζ ()
• T (n +1, y) = P (T (n, y), y)

Dále definujeme exponenciální funkci E (x, y). (Obvykle 0 ⁰ je považováno za nedefinované, ale protože primitivní rekurzivní funkce musí být celkem, definujeme E (0,0) jako 1.) Protože primitivní rekurze nám umožňuje pouze rekurzovat na první argument, použijeme dva kroky k definování exponenciální funkce:

• R (0, y) = σ (ζ ())
• R (n +1, y) = T (R (n, y), y)

Nakonec můžeme definovat E (x, y) = R (η (y), η (x)) složením. (Připomeňme, že η je funkce identity, takže by to mohlo být jednodušší psáno jako E (x, y) = R (y, x).)

Exponenciální funkce E roste velmi rychle, například E (10,10) je deset miliard a E (50,50) je přes 10 ⁸⁴(a tedy výrazně více než odhadovaný počet atomů ve vesmíru). Existují však mnohem rychlejší primitivní rekurzivní funkce. Jak jsme viděli, E byla definována z pomalu rostoucí funkce σ pomocí tří aplikací primitivní rekurze: jedna pro sčítání, druhá pro násobení a druhá pro exponentiaci. Můžeme pokračovat v používání primitivní rekurze, abychom vytvořili řadu nepředstavitelně rychle rostoucích funkcí. Udělejme ještě jeden krok v řadě definující hyperexponenciální funkci, H (n, m) jako 2 až 2 až 2 až … až m, s věží n 2. H je primitivní rekurzivní, protože jej lze definovat z E pomocí jedné další aplikace primitivní rekurze:

• H (0, y) = y
• H (n +1, y) = E (2, H (n, y))

Tak H (2,2) = 2 ⁴ = 16, H (3,3) = 2, ²⁵⁶ je větší než 10 ⁷⁷ a srovnatelný s počtem atomů ve vesmíru. Pokud to pro vás není dost velké, zvažte H (4,4). Pro zápis tohoto čísla v desítkové notaci bychom potřebovali jedno, následované více nulami, než je počet částic ve vesmíru.

3.1 Rekurzivní funkce

Sada primitivních rekurzivních funkcí je obrovská třída kompatibilních funkcí. Ve skutečnosti je lze charakterizovat jako množinu funkcí vypočítatelných v čase, což je nějaká primitivní rekurzivní funkce n, kde n je délka vstupu. Například protože H (n, n) je primitivní rekurzivní funkce, zahrnují primitivní rekurzivní funkce veškerý TIME [H (n, n)]. (Viz následující část pro diskusi o výpočetní složitosti, včetně TIME.) Primitivní rekurzivní funkce tedy zahrnují všechny funkce, které jsou proveditelné pomocí jakékoli myslitelné míry proveditelnosti, a mnohem dále.

Primitivní rekurzivní funkce však nezahrnují v zásadě všechny funkce, které lze vypočítat. Abychom to viděli, můžeme znovu použít diagonalizaci. Můžeme systematicky kódovat všechny definice primitivních rekurzivních funkcí arity 1, které se nazývají p ₁, p ₂, p ₃ atd.

Potom můžeme sestavit Turingův stroj pro výpočet hodnoty následující diagonální funkce, D (n) = p _n (n) + 1.

Všimněte si, že D je celková, vypočítatelná funkce od N do N, ale není to primitivní rekurzivní. Proč? Předpokládejme kvůli rozporu, že D byly primitivní rekurzivní. Pak by D bylo pro některé d ∈ N rovné p _d. To by ale následovalo

p _d (d) = p _d  (d) 1,

což je rozpor. Proto D není primitivní rekurzivní.

Bohužel, výše uvedený diagonální argument funguje na jakékoli třídě celkových funkcí, které by mohly být považovány za kandidáta na třídu všech kompatibilních funkcí. Jediným způsobem, jak toho dosáhnout, pokud chceme, aby všechny funkce byly v zásadě vyčíslitelné, nejen v praxi, je přidat nějaký druh neomezené operace vyhledávání. To udělal Gödel k rozšíření primitivních rekurzivních funkcí na rekurzivní funkce.

Neomezený operátor minimalizace, μ, definujte následovně. Nechť f je možná částečná funkce arity k + 1. Pak μ [f] je definována jako následující funkce arity k. Na vstupu x ₁, …, x _k proveďte následující:

Pro i = 0 až ∞ do {

pokud f (i, x ₁, …, x _k) = 1, pak výstup i

}

Pokud je tedy f (i, x ₁,…, x _k) = 1 a pro všechny j <i, f (j, x ₁,…, x _k) je definováno, ale není rovno 1, pak μ [f] (x ₁, …, x _k) = i. Jinak μ [f] (x ₁, …, x _k) není definováno.

Gödel definoval sadu rekurzivních funkcí jako uzavření počátečních primitivních rekurzivních funkcí ve složení, primitivní rekurze a μ. S touto definicí jsou rekurzivní funkce naprosto stejné jako sada dílčích funkcí, které lze vypočítat pomocí Lambda počtu, systémů Kleene Formal, Markovových algoritmů, poštovních strojů a Turingových strojů.

4. Výpočetní složitost: Funkce kompatibilní v praxi

Během druhé světové války pomohl Turing navrhnout a postavit specializované výpočetní zařízení zvané Bombe v Bletchley Parku. Použil Bombe k rozbití německého kódu „Enigma“, což značně pomohlo spojenecké věci [Hodges, 1992]. Do 60. let byly počítače široce dostupné v průmyslu i na univerzitách. Protože byly vyvinuty algoritmy pro řešení nesčetných problémů, začali někteří matematici a vědci algoritmy klasifikovat podle jejich účinnosti a hledat nejlepší algoritmy pro určité problémy. To byl začátek moderní teorie výpočtu.

V této části se zabýváme složitostí namísto počítatelnosti a všechny Turingovy stroje, které považujeme, zastaví na všech svých vstupech. Spíše než přijímání zastavením, budeme předpokládat, že Turingův stroj přijímá výstupem "1" a odmítá výstupem "0", takže předefinujeme množinu akceptovanou celkovým strojem, M,

L (M) = {n | M (n) = 1}.

Čas, který algoritmus zabere, závisí na vstupu a stroji, na kterém je spuštěn. Prvním důležitým vhledem do teorie složitosti je, že dobrým měřítkem složitosti algoritmu je jeho asymptotická nejhorší složitost jako funkce velikosti vstupu, n.

Pro vstup, w, nechť n = | w | být délka w. Po [Hartmanis, 1989] říkáme, že Turingův stroj M běží v čase T (n), pokud pro všechny w délky n, M (w) trvá maximálně T (n) kroků a pak se zastaví. Tomu se říká nejhorší složitost, protože T (n) musí být stejně velké jako doba, kterou zabere jakýkoli vstup délky n.

Pro libovolnou funkci T: N → N nechte

ČAS [T (n)] = {A | A = L (M) pro některé M, které běží v čase T (n)}

Alan Cobham a Jack Edmonds označili třídu složitosti, P, problémů rozpoznatelných v nějakém polynomickém množství času, za vynikající matematický obal třídy proveditelných problémů - ty problémy, jejichž všechny středně velké případy lze snadno rozpoznat,

P = ∪ _{i = 1,2,…} ČAS [n ⁱ  ]

Jakýkoli problém, který není v P, rozhodně není proveditelný. Na druhé straně, přirozené problémy, které mají algoritmy v P, mají tendenci nakonec pro ně objevovat algoritmy, které jsou skutečně proveditelné.

Kromě P bylo definováno a studováno mnoho důležitých tříd složitosti; několik z nich jsou NP, PSPACE a EXPTIME. PSPACE sestává z těchto problémů řešitelných pomocí určitého množství polynomu v paměti. EXPTIME je množina problémů řešitelných v čase 2 ^{p (n)} pro některé polynomy, p.

Asi nejzajímavější z výše uvedených tříd je NP: nedeterministický polynomiální čas. Definice nepochází ze skutečného stroje, ale spíše z matematické abstrakce. Nedeterministický Turingův stroj, N, provádí volbu (hádání) jedné ze dvou možných akcí v každém kroku. Pokud na vstupu w vede některá posloupnost těchto voleb k přijetí, pak říkáme, že N přijímá w, a říkáme, že nedeterministický čas, který N zaujal na vstupu w, je pouze počet kroků provedených ve sledu, který vede k přijetí. Nedeterministický stroj není účtován za všechny ostatní možné volby, které mohl učinit, pouze za jednu sekvenci správných voleb.

NP je někdy popisována jako soubor problémů, S, které mají krátké důkazy o členství. Předpokládejme například, že jsme dostali seznam přirozených čísel m: a ₁,…, a _ma cílové číslo, t. Toto je příklad problému součtu podmnožiny: existuje podmnožina čísel m, jejichž součet je přesně t? Tento problém lze snadno vyřešit v nedeterministickém lineárním čase: u každého i hádáme, zda vzít _i. Dále sečteme všechna čísla, která jsme se rozhodli vzít, a pokud je součet roven t, přijmeme. Nondeterministický čas je tedy lineární, tj. Některé konstanty krát délka vstupu, n. Neexistuje však žádný známý (deterministický) způsob, jak vyřešit tento problém v čase méně než exponenciální v n.

Proběhla rozsáhlá studie algoritmů a je dobře pochopena složitost mnoha důležitých problémů. Zejména byla definována redukce mezi problémy a použita k porovnání relativní obtížnosti dvou problémů. Intuitivně říkáme, že A je redukovatelné na B (A ≤ B), pokud existuje jednoduchá transformace, τ, která mapuje instance A na instance B způsobem, který zachovává členství, tj. Τ (w) ∈ B ⇔ w ∈ A.

Je pozoruhodné, že vysoké procento přirozeně se vyskytujících výpočetních problémů se u jedné z výše uvedených tříd ukázalo jako úplné. (Problém A je dokončen pro třídu složitosti C, pokud A je členem C a všechny ostatní problémy B v C nejsou obtížnější než A, tj. B ≤ A. Dva úplné problémy pro stejnou třídu mají stejnou složitost.)

Důvod tohoto jevu úplnosti nebyl dostatečně vysvětlen. Jedno věrohodné vysvětlení je, že přirozené počítačové problémy bývají univerzální ve smyslu Turingova univerzálního stroje. Univerzální problém v určité třídě složitosti může simulovat jakýkoli jiný problém v této třídě. Důvod, proč je třída NP tak dobře prozkoumaná, spočívá v tom, že celá řada důležitých praktických problémů je úplná, včetně součtu podskupin. Není známo, že žádný z těchto problémů nemá algoritmus, který je rychlejší než exponenciální čas, ačkoli některé problémy s dokončením NP připouštějí proveditelná aproximace jejich řešení.

O výpočetní složitosti zůstává mnoho otevřených. Víme, že přísně více konkrétního výpočetního zdroje nám umožňuje řešit přísně obtížnější problémy, např. TIME [n] je přísně obsaženo v TIME [n ^1.01] a podobně pro SPACE a další opatření. Kompromisy mezi různými výpočetními zdroji však stále nejsou dostatečně srozumitelné. Je zřejmé, že P je obsažen v NP. Dále je NP obsažen v PSPACE, protože v PSPACE můžeme systematicky zkoušet každou jednotlivou větev výpočtu NP, znovu použít prostor pro následné větve a přijímat, pokud některá z těchto větví vede k přijetí. PSPACE je obsažen v EXPTIME, protože pokud stroj PSPACE zabere více než exponenciální čas, pak přesně opakoval nějakou konfiguraci, takže musí být v nekonečné smyčce. Níže jsou uvedeny známé vztahy mezi výše uvedenými třídami:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

I když se zdá jasné, že P je přísně obsažen v NP, že NP je přísně obsažen v PSPACE a že PSPACE je přísně obsažen v EXPTIME, žádná z těchto nerovností nebyla prokázána. Ve skutečnosti není ani známo, že P se liší od PSPACE, ani že NP se liší od EXPTIME. Jediné známé správné zahrnutí z výše uvedeného je, že P je přísně obsažen v EXPTIME. Zbývající otázky týkající se relativní síly různých výpočetních zdrojů jsou základní nevyřešené problémy v teorii výpočtu.

Bibliografie

• Church, Alonzo, 1933, "Soubor postulátů pro založení logiky (Druhý dokument)", Annals of Mathematics, druhá řada, 33, Princeton, 839-864.
• Church, Alonzo, 1936, „Neřešitelný problém teorie elementárních čísel“, American Journal of Mathematics, 58, Baltimore, 345-363.
• Church, Alonzo, 1936, „Poznámka k Entscheidungsproblemovi“, Journal of Symbolic Logic, 1, 40-41; korekce 1, Menasha, Wis., 101-102.
• Böerger, Egon, Erich Grädel a Yuri Gurevich, 1997, The Classical Decision Problem, Springer, Heidelberg.
• Cobham, Alan, 1964, „Vnitřní výpočetní obtížnost funkcí“, sborník z kongresu z roku 1964 pro logiku, matematiku a filozofii vědy, North-Holland, Amsterdam, 24-30.
• Cook, Stephen, 1971, „Složitost postupů při určování věty“, řízení třetího ročního sympozia ACM STOC, Shaker Heights, Ohio, 151–158.
• Davis, Martin, 2000, Univerzální počítač: Cesta z Leibnizu do Turingu, WW Norton & Company, New York.
• Edmonds, Jack, 1965, "Paths, Trees and Trees", Canadian Journal of Mathematics, 17, Toronto, 449-467.
• Enderton, Herbert B., 1972, Matematický úvod do logiky, Academic Press, New York.
• Garey, Michael a David S. Johnson, 1979, Computers and Intractability, Freeman, New York.
• Gödel, Kurt 1930, "Úplnost axiomů funkčního počtu", (van Heijenoort, 1967), 582-591.
• Gödel, Kurt 1931, „O formálně nerozhodnutelných návrzích Principia Mathematica a souvisejících systémů I“, (van Heijenoort, 1967), 592-617.
• Hartmanis, Juris, 1989, "Přehled teorie výpočetní komplexnosti" v J. Hartmanis, ed., Teorie výpočetní komplexnosti, Americká matematická společnost, Providence, 1-17.
• Hilbert a Ackermann, 1928/1938, Grundzüge der theoretischen Logik, Springer. Anglický překlad 2. vydání: Principles of Mathematical Logic, 1950, Chelsea Publishing Company, New York.
• Hodges, Andrew, 1992, Alan Turing: Enigma, Random House, Londýn.
• Hofstadter, Douglas, 1979, Gödel, Escher, Bach: Věčný zlatý cop, Základní knihy, New York.
• Hopcroft, John E., 1984, "Turing Machines", Scientific American, 250 (5), New York, 70-80.
• Karp, Richard, „Reducibilita mezi kombinatorickými problémy“, v složitosti výpočtů, RE Miller a JW Thatcher, eds. (1972), Plenum Press, New York, 85-104.
• Kleene, Stephen C., 1935, „Teorie pozitivních celých čísel ve formální logice,“American Journal of Mathematics, 57, Baltimore, 153-173, 219-244.
• Kleene, Stephen C., 1950, Úvod do metamatematiky, Van Nostrand, Princeton.
• Levin, Leonid, 1973, „Problémy univerzálního vyhledávání“, Problemy Peredachi Informatsii, 9 (3), 265-266; částečný anglický překlad v: BATrakhtenbrot, 1984, „Přehled ruských přístupů k Perebor (Brute-force Search) Algoritmy,“IEEE Annals of the History of Computing, 6 (4), Los Alamitos, CA, 384-400.
• Markov, AA, 1960, „Theory of Algorithms“, The American Mathematical Society Translations, series 2, 15, Providence, 1-14.
• Meyer, Albert a Dennis Ritchie, 1967, „Složitost smyčkových programů“. Proc. 22. národní konference ACM, Washington, DC, 465-470.
• Papadimitriou, Christos H., 1994, Computational Complexity, Addison-Wesley, Reading, Mass.
• Péter, Rózsa. 1967, Rekurzivní funkce, přeložil István Földes, Academic Press, New York.
• Post, Emil, 1936, „Konečné kombinované procesy - formulace I“, Journal of Symbolic Logic, 1, Menasha, Wis., 103-105.
• Rogers, Hartley Jr., Teorie rekurzivních funkcí a efektivní kompatibility, 1967, McGraw-Hill, New York.
• Turing, AM, 1936-7, „O kompatibilních číslech, s aplikací u Entscheidungsproblem“, Sborník London Mathematical Society, 2 (42), London, 230-265 [Předtisk je k dispozici online].
• van Heijenoort, Jean, ed., 1967, From Frege To Gödel: Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge, Mass.
• Whitehead, Alfred North a Bertrand Russell, 1910, Principia Mathematica, Cambridge University Press, Cambridge.

Další internetové zdroje

• Deskriptivní složitost: webová stránka popisující výzkum deskriptivní složitosti, což je výpočetní složitost z logického hlediska (s diagramem znázorňujícím svět vypočítatelnosti a složitosti). Spravuje Neil Immerman, University of Massachusetts, Amherst.
• Hmota, velikost a hustota vesmíru z National Solar Observatory / Sacramento Peak.