Církev – Turingova teze - Church–Turing thesis - Wikipedia

v teorie vypočítatelnosti, Církev – Turingova teze (také známý jako vyčíslitelnost práce,^[1] the Turing – církevní práce,^[2] the Církev – Turingova domněnka, Církevní teze, Církevní domněnka, a Turingova práce) je hypotéza o povaze vypočítatelné funkce. Uvádí, že a funkce na přirozená čísla lze vypočítat pomocí efektivní metoda právě když je vypočítatelný a Turingův stroj. Tato práce je pojmenována po americkém matematikovi Alonzo Church a britský matematik Alan Turing. Před přesnou definicí vypočítatelné funkce matematici často používali neformální výraz efektivně vypočítatelné popsat funkce, které lze vypočítat metodami papír a tužka. Ve 30. letech bylo učiněno několik nezávislých pokusů formalizovat pojem vypočítatelnost:

• V roce 1933 Kurt Gödel, s Jacques Herbrand vytvořil formální definici třídy s názvem obecné rekurzivní funkce. Třída obecných rekurzivních funkcí je nejmenší třída funkcí (možná s více než jedním argumentem), která zahrnuje všechny konstantní funkce, projekce, nástupnická funkce, a která je uzavřena pod složení funkce, rekurze, a minimalizace.
• V roce 1936 Alonzo Church vytvořil metodu pro definování funkcí zvanou λ-kalkul. V rámci λ-kalkulu definoval kódování přirozených čísel zvaných Církevní číslice. Funkce na přirozených číslech se nazývá λ-vypočítatelné jestliže odpovídající funkce na církevních číslech může být reprezentována členem λ-kalkulu.
• Také v roce 1936, předtím, než se dozvěděl o práci církve,^{[Citace je zapotřebí ]} Alan Turing vytvořil teoretický model pro stroje, nyní nazývané Turingovy stroje, které mohly provádět výpočty ze vstupů manipulací se symboly na pásku. Při vhodném kódování přirozených čísel jako sekvencí symbolů se volá funkce na přirozených číslech Turing vypočítatelný pokud nějaký Turingův stroj vypočítá odpovídající funkci na zakódovaných přirozených číslech.

Kostel^[3] a Turing^[4][6] dokázal, že tyto tři formálně definované třídy vypočítatelných funkcí se shodují: funkce je λ-vypočítatelná právě tehdy, když je Turingova spočitatelná, a právě tehdy, když je obecně rekurzivní. To vedlo matematiky a počítačové vědce k přesvědčení, že koncept vypočítatelnosti je přesně charakterizován těmito třemi ekvivalentními procesy. Další formální pokusy charakterizovat vypočítatelnost následně tuto víru posílily (viz níže ).

Na druhou stranu teze Church-Turing uvádí, že výše uvedené tři formálně definované třídy vypočítatelných funkcí se shodují s neformální pojem efektivně vypočítatelné funkce. Protože koncept neformální kalkulace jako neformální pojem nemá formální definici, nelze tuto práci formálně dokázat, i když má téměř univerzální přijetí.

Od jejího vzniku se objevily variace původní práce, včetně výroků o tom, co lze fyzicky realizovat počítačem v našem vesmíru (fyzická turingova turingova práce ) a co lze efektivně vypočítat (Církev – Turingova teze (teorie složitosti) ). Tyto variace nejsou způsobeny Churchem nebo Turingem, ale vyplývají z pozdější práce v teorie složitosti a digitální fyzika. Práce má také důsledky pro filozofie mysli (vidět níže ).

Prohlášení církevními a Turingovými slovy

J. B. Rosser  (1939 ) se zabývá pojmem „efektivní vypočítatelnost“ následovně: „Je zřejmé, že existence CC a RC (Church's and Rosser's proofs) předpokládá přesnou definici„ efektivní “. každý krok je přesně předurčen a je jisté, že vyprodukuje odpověď v konečném počtu kroků “.^[7] Adverbní adjektivum „efektivní“ se tedy používá ve smyslu „1a: vytváření rozhodného, ​​rozhodujícího nebo požadovaného efektu“ a „schopné dosáhnout výsledku“.^[8][9]

V následujícím textu budou slova „účinně vypočítatelný“ znamenat „vyrobený jakýmkoli intuitivně„ účinným “znamená vůbec“ a „skutečně vypočítatelný“ bude znamenat „vyroben Turingovým strojem nebo ekvivalentním mechanickým zařízením“. Turingovy „definice“ uvedené v poznámce pod čarou v jeho Ph.D. Ph.D. z roku 1938 teze Logické systémy založené na ordinálech, pod dohledem církve, jsou prakticky stejné:

^† Výraz „vypočítatelná funkce“ budeme používat k označení funkce vypočítatelné strojem a necháme „efektivně vypočítatelnou“ odkazovat na intuitivní myšlenku bez konkrétní identifikace s některou z těchto definic.^[10]

Práce lze konstatovat jako: Každá efektivně vypočítatelná funkce je vypočítatelná funkce.^[11]Církev také uvedla, že „Žádný výpočetní postup nebude považován za algoritmus, pokud jej nelze reprezentovat jako Turingův stroj“.^{[Citace je zapotřebí ]}Turing to uvedl takto:

Bylo konstatováno ... že „funkci lze skutečně vypočítat, pokud její hodnoty lze zjistit nějakým čistě mechanickým procesem“. Můžeme to brát doslovně, chápeme-li to čistě mechanickým procesem, který by mohl provádět stroj. Vývoj ... vede k ... identifikaci vypočítatelnosti^† s efektivní vypočítatelností. [^† je poznámka pod čarou uvedená výše.]^[10]

Dějiny

Jedním z důležitých problémů logiků ve třicátých letech byl Entscheidungsproblem z David Hilbert a Wilhelm Ackermann,^[12] který se ptal, zda existuje mechanický postup pro oddělení matematických pravd od matematických lží. Tento úkol vyžadoval upřesnění pojmu „algoritmus“ nebo „efektivní kalkulovatelnost“, alespoň natolik, aby mohl úkol začít.^[13] Ale od samého začátku Alonzo Church Pokusy začaly debatou, která trvá dodnes.^[14] Byl^{[vyjasnit ]} pojem „efektivní vypočítatelnost“ jako (i) „axiom nebo axiomy“ v axiomatickém systému, (ii) pouze definice že „identifikoval“ dva nebo více návrhů, (iii) an empirická hypotéza být ověřen pozorováním přírodních jevů, nebo (iv) spravedlivý návrh z důvodu argumentace (tj. „teze“).

Kolem 1930–1952

V průběhu studia problému Church a jeho student Stephen Kleene představil pojem λ-definovatelné funkce a dokázali dokázat, že několik velkých tříd funkcí, s nimiž se v teorii čísel často setkáváme, bylo definovatelných λ.^[15] Debata začala, když církev navrhla Gödelovi, že je třeba definovat „efektivně vypočítatelné“ funkce jako funkce definovatelné λ. Gödel však nebyl přesvědčen a návrh označil za „naprosto neuspokojivý“.^[16] Spíše v korespondenci s církví (kolem 1934–1935) navrhl Gödel axiomatizující pojem „efektivní vypočítatelnost“; ve skutečnosti v dopise Kleene z roku 1935 Church uvedl, že:

Jeho [Gödelova] jediná myšlenka v té době byla, že by bylo možné, pokud jde o efektivní vypočítatelnost jako nedefinovaný pojem, uvést soubor axiomů, které by ztělesňovaly obecně přijímané vlastnosti tohoto pojmu, a na tomto základě něco udělat .^[17]

Gödel však nenabídl žádné další pokyny. Nakonec navrhne jeho rekurzi, upravenou Herbrandovým návrhem, kterou Gödel podrobně popsal na svých přednáškách v roce 1934 v Princetonu NJ (Kleene Rosser přepsal poznámky). Ale nemyslel si, že tyto dvě myšlenky lze uspokojivě identifikovat „kromě heuristicky“.^[18]

Dále bylo nutné identifikovat a dokázat rovnocennost dvou pojmů efektivní kalkulovatelnosti. Vybaveno λ-kalkulem a „obecnou“ rekurzí, Stephen Kleene s pomocí církve a J. Barkley Rosser předložil důkazy (1933, 1935), aby ukázal, že oba kameny jsou ekvivalentní. Church následně upravil své metody tak, aby zahrnovaly použití rekurze Herbrand – Gödel, a poté (1936) dokázal, že Entscheidungsproblem je neřešitelný: neexistuje žádný algoritmus, který by určoval, zda a dobře formulovaný vzorec má „normální formu“.^{[vyjasnit ][19]}

O mnoho let později v dopise Davisovi (kolem r. 1965) Gödel uvedl, že „nebyl v době těchto přednášek [1934] vůbec přesvědčen o tom, že jeho koncept rekurze zahrnuje všechny možné rekurze“.^[20] V letech 1963–64 by se Gödel distancoval od rekurze Herbrand – Gödel a kalkulu λ ve prospěch Turingova stroje jako definice „algoritmu“ nebo „mechanického postupu“ nebo „formálního systému“.^[21]

Hypotéza vedoucí k přirozenému zákonu?: Na konci roku 1936 Alan Turing papír (také dokazující, že Entscheidungsproblem je neřešitelný) byl doručen ústně, ale dosud se neobjevil v tisku.^[22] Na druhou stranu, Emil Post Objevil se papír z roku 1936, který byl certifikován nezávisle na Turingově práci.^[23] Příspěvek rozhodně nesouhlasil s „identifikací“ církve efektivní vypočítatelnosti pomocí λ-kalkulu a rekurze, přičemž uvedl:

Práce, kterou již provedla Církev a další, tuto identifikaci ve skutečnosti nese podstatně mimo fázi pracovní hypotézy. Ale zamaskovat tuto identifikaci definicí… nás oslepuje nad nutností jejího nepřetržitého ověřování.^[24]

Pojem „efektivní vypočítatelnost“ spíše považoval za pouhou „pracovní hypotézu“, která by mohla vést induktivní uvažování na „přírodní zákon „spíše než„ definicí nebo axiomem “.^[25] Církev tuto myšlenku „ostře“ kritizovala.^[26]

Post tedy ve svém příspěvku z roku 1936 také slevoval Kurt Gödel Návrh církve v letech 1934–1935, že práce může být vyjádřena jako axiom nebo soubor axiomů.^[17]

Turing přidává další definici, Rosser rovná se všechny tři: Během krátké doby Turingův dokument z let 1936–1937 „Na vypočítatelných číslech s aplikací na problém Entscheidungs“^[22] objevil se. V něm uvedl další pojem „efektivní vypočítatelnosti“ zavedením svých strojů typu „a“ (nyní známých jako „a“) Turingův stroj abstraktní výpočetní model). A v náčrtu přidaném jako „dodatek“ k jeho dokumentu z let 1936–37 Turing ukázal, že třídy funkcí definované pomocí λ-kalkulu a Turingových strojů se shodovaly.^[27] Church rychle poznal, jak přesvědčivá byla Turingova analýza. Ve své recenzi Turingova článku objasnil, že Turingova představa učinila „identifikaci s účinností v běžném (ne explicitně definovaném) smyslu evidentní okamžitě“.^[28]

Za několik let (1939) by Turing navrhl, stejně jako Church a Kleene před ním, to jeho formální definice mechanického výpočetního agenta byla správná.^[29] Do roku 1939 tedy Church (1934) i Turing (1939) individuálně navrhli, aby jejich „formální systémy“ byly definice „efektivní kalkulovatelnosti“;^[30] ani nezarámovali svá prohlášení jako práce.

Rosser (1939) formálně identifikoval tři pojmy jako definice:

Všichni tři definice jsou ekvivalentní, takže nezáleží na tom, který z nich je použit.^[31]

Navrhuje Kleene Církevní práce: Toto ponechalo Kleene zjevné vyjádření „teze“. Ve svém příspěvku z roku 1943 Rekurzivní predikáty a kvantifikátory Kleene navrhl své „PRÁCE I“:

Tento heuristický fakt [obecné rekurzivní funkce lze účinně vypočítat] ... vedl církev ke stanovení následující teze (²²). Stejná práce je implicitní v Turingově popisu výpočetních strojů (²³).

PRÁCE I. Každá efektivně vypočítatelná funkce (skutečně rozhodnutelný predikát) je obecná^[32] rekurzivní [Kleeneova kurzíva]

Vzhledem k tomu, že je zapotřebí přesná matematická definice pojmu skutečně vypočítatelný (účinně rozhodnutelný), můžeme tuto práci vzít ... jako jeho definici ...^[33]

(²²) odkazy Church 1936;^{[není dostatečně konkrétní k ověření ]} (²³) reference Turing 1936–7 Kleene dále poznamenává, že:

práce má charakter hypotézy - bod zdůrazněný Postem a Churchem (²⁴). Pokud považujeme práci a její obrácení za definici, pak je hypotézou hypotéza o aplikaci matematické teorie vyvinuté z definice. Pro přijetí hypotézy existují, jak jsme navrhli, docela přesvědčivé důvody.^[33]

(24) reference Post 1936 of Post and Church's Formální definice v teorii řadových čísel, Fond. Matematika. svazek 28 (1936) str. 11–21 (viz odkaz č. 2, Davis 1965:286).

Kleeneova církev - Turingova teze: O několik let později (1952) Kleene, který přešel od prezentace své práce v matematické terminologii lambda kalkulu svého doktorského poradce Alonzo Church k teorii obecných rekurzivních funkcí svého dalšího učitele Kurta Gödela, by otevřeně pojmenoval Church– Turingova teze ve své opravě Turingova příspěvku „Slovní problém v poloskupinách se zrušením“,^[34] bránit a vyjádřit dvě „teze“ a poté je „identifikovat“ (ukázat rovnocennost) pomocí své Věty XXX:

Heuristické důkazy a další úvahy vedly církev v roce 1936 k navržení následující teze.

Práce I. Každá efektivně vypočítatelná funkce (efektivně rozhodnutelný predikát) je obecně rekurzivní.^[35]

Věta XXX: Následující třídy dílčích funkcí jsou koextenzivní, tj. Mají stejné členy: (a) částečné rekurzivní funkce, (b) vypočítatelné funkce ...^[36]

Turingova teze: Turingova teze, že každá funkce, která by přirozeně byla považována za vypočítatelnou, je vypočítatelná podle jeho definice, tj. Pomocí jednoho z jeho strojů, je ekvivalentní s Churchovou tezí od Věty XXX.^[36]

Pozdější vývoj

Pokus porozumět pojmu „efektivní vypočítatelnost“ vedl lépe Robin Gandy (Turingův student a přítel) v roce 1980 analyzovat stroj výpočet (na rozdíl od výpočtu člověka prováděného Turingovým strojem). Gandyho zvědavost a analýza mobilní automaty (počítaje v to Conwayova hra o život ), paralelismus a krystalické automaty, ho vedly k tomu, aby navrhl čtyři „principy (nebo omezení) ... které musí každý stroj splňovat“.^[37] Jeho nejdůležitější čtvrtý, „princip kauzality“, je založen na „konečné rychlosti šíření efektů a signálů; současná fyzika odmítá možnost okamžitého působení na dálku“.^[38] Z těchto principů a některých dalších omezení - (1a) spodní hranice lineárních rozměrů kterékoli z částí, (1b) horní hranice rychlosti šíření (rychlost světla), (2) diskrétní postup stroje, a (3) deterministické chování - vytvoří větu, že „Co lze vypočítat zařízením splňujícím zásady I – IV, je vypočítatelné.“^[39]

Na konci 90. let Wilfried Sieg analyzoval Turingovy a Gandyho pojmy „efektivní vypočítatelnosti“ se záměrem „zostřit neformální představu, formovat její obecné rysy axiomaticky a prozkoumat axiomatický rámec“.^[40] Ve své práci z let 1997 a 2002 Sieg představuje řadu omezení chování a počítač- "lidský výpočetní agent, který postupuje mechanicky". Tato omezení se snižují na:

• "(B.1) (Omezenost) Počet symbolických konfigurací, které může počítač okamžitě rozpoznat, je pevně vázán."
• "(B.2) (Omezenost) Existuje pevná hranice počtu interních stavů, ve kterých může být počítač.
• "(L.1) (Lokalita) Počítač může měnit pouze prvky pozorované symbolické konfigurace.
• „(L.2) (Lokalita) Počítač může přesouvat pozornost z jedné symbolické konfigurace na jinou, ale nové pozorované konfigurace musí být v ohraničené vzdálenosti od okamžitě dříve pozorované konfigurace.
• "(D) (Determinacy) Okamžitě rozpoznatelná (sub-) konfigurace jednoznačně určuje další krok výpočtu (a id [okamžitý popis])"; uvedl jiný způsob: „Interní stav počítače společně s pozorovanou konfigurací jednoznačně opravuje další krok výpočtu a další interní stav.“^[41]

Záležitost zůstává v aktivní diskusi v rámci akademické komunity.^[42][43]

Práce jako definice

Na tuto práci nelze pohlížet jako na běžnou matematickou definici. Tento názor naznačují komentáře Gödela k tématu, např. „správná definice mechanické vypočítatelnosti byla nepochybně stanovena Turingem“.^[44] Důvody pro nahlížení na práci jako na nic jiného než definici výslovně stanoví Robert I. Soare,^[45] kde se také tvrdí, že Turingova definice vypočítatelnosti není o nic méně pravděpodobné, že bude správná než definice epsilon-delta spojitá funkce.

Úspěch práce

Další formalizmy (kromě rekurze λ-kalkul a Turingův stroj ) byly navrženy pro popis efektivní vypočítatelnosti / vypočítatelnosti. Stephen Kleene (1952) přidává do seznamu funkce "počítatelný v systému S₁„z Kurt Gödel 1936 a Emil Post (1943, 1946) "kanonický [také zvaný normální] systémy".^[46] V padesátých letech Hao Wang a Martin Davis výrazně zjednodušil model Turingova stroje s jednou páskou (viz Post-Turingův stroj ). Marvin Minsky rozšířil model na dvě nebo více pásek a výrazně zjednodušil pásky na „čítače nahoru-dolů“, které Melzak a Lambek dále se vyvinul do toho, co je nyní známé jako pultový stroj Modelka. Na konci šedesátých a začátku sedmdesátých let rozšířili vědci model počítadlového stroje na zaregistrovat stroj, blízký bratranec moderní představy o počítač. Mezi další modely patří kombinační logika a Markovovy algoritmy. Gurevič přidává ukazatel stroj model Kolmogorova a Uspenského (1953, 1958): „... chtěli jen ... přesvědčit sebe, že neexistuje způsob, jak rozšířit představu o vypočítatelné funkci.“^[47]

Všechny tyto příspěvky zahrnují důkazy, že modely jsou výpočetně ekvivalentní s Turingovým strojem; o takových modelech se říká, že jsou Turing dokončen. Protože všechny tyto různé pokusy o formalizaci pojmu „efektivní vypočítatelnost / vypočítatelnost“ přinesly ekvivalentní výsledky, nyní se obecně předpokládá, že teze Church-Turing je správná. Ve skutečnosti Gödel (1936) navrhl něco silnějšího než toto; poznamenal, že v pojmu „lze počítat v S je něco„ absolutního “₁":

Může se také ukázat, že funkce, která je vypočítatelná [„vyčíslitelná“] v jednom ze systémů S_i, nebo dokonce v systému transfinitního typu, je již vypočítatelný [vyčíslitelný] v S₁. Pojem „vypočítatelný“ [„počítatelný“] je tedy v určitém definitivním smyslu „absolutní“, zatímco prakticky všechny ostatní známé metamatematické pojmy (např. Prokazatelné, definovatelné atd.) Závisí zcela zásadně na systému, kterému jsou definovány. .^[48]

Neformální použití v důkazech

Důkazy v teorii vyčíslitelnosti se často odvolávají na tezi Church-Turing neformálním způsobem, aby stanovily vyčíslitelnost funkcí a zároveň se vyhnuly (často velmi dlouhým) detailům, které by byly zahrnuty do přísného, ​​formálního důkazu.^[49] Abychom zjistili, že funkce je vypočítatelná Turingovým strojem, je obvykle považováno za dostatečné poskytnout neformální anglický popis toho, jak lze funkci efektivně vypočítat, a poté uzavřít „tezí Church-Turing“, že funkce je Turingova vypočítatelná (ekvivalentně , částečná rekurzivní).

Dirk van Dalen uvádí následující příklad pro ilustraci tohoto neformálního využití práce Church-Turing:^[50]

PŘÍKLAD: Každý nekonečný RE sada obsahuje nekonečno rekurzivní množina.

Důkaz: Nechť A je nekonečný RE. Seznamujeme prvky A efektivně, n₀, n₁, n₂, n₃, ...

Z tohoto seznamu extrahujeme rostoucí sublist: put m₀= n₀, po konečně mnoha krocích najdeme n_k takový, že n_k > m₀, dát m₁= n_k. Tento postup opakujeme, abychom našli m₂ > m₁atd., čímž se získá efektivní seznam podmnožiny B = {m₀, m₁, m₂, ...} z A, s vlastností m_i i + 1.

Nárok. B je rozhodnutelné. Abychom mohli otestovat k v B, musíme zkontrolovat, zda k = m_i pro některé i. Od posloupnosti m_iS přibývajícím množstvím musíme vyprodukovat maximálně k + 1 prvků seznamu a porovnat je s k. Pokud se žádný z nich nerovná k, pak k ne v B. Jelikož je tento test účinný, je B rozhodnutelné a, církevní tezírekurzivní.

Aby byl výše uvedený příklad zcela přísný, bylo by třeba pečlivě sestrojit Turingův stroj nebo funkci λ, nebo opatrně vyvolat rekurzní axiomy, nebo přinejlepším chytře vyvolat různé věty teorie vypočítatelnosti. Ale protože teoretik vypočítatelnosti věří, že Turingova vypočítatelnost správně zachycuje to, co lze efektivně vypočítat, a protože je v angličtině vysvětlen efektivní postup pro rozhodování o množině B, teoretik počítatelnosti to přijímá jako důkaz, že množina je skutečně rekurzivní.

Variace

Úspěch práce Church-Turing vedl k navržení variant této práce. Například fyzická církev – Turingova teze uvádí: "Všechny fyzicky vypočítatelné funkce jsou Turingově vypočítatelné."^[51]:101

Teze Church-Turing neříká nic o efektivitě, s jakou může jeden model výpočtu simulovat jiný. Bylo například prokázáno, že (vícepáska) univerzální Turingův stroj pouze trpí logaritmickým faktorem zpomalení při simulaci jakéhokoli Turingova stroje.^[52]

Variace teze Church-Turing se zabývá otázkou, zda lze účinně simulovat libovolný, ale „rozumný“ model výpočtu. Tomu se říká studie proveditelnosti,^[53] také známý jako (klasický) teoreticko-teoretická církev – Turingova teze nebo rozšířená Church – Turingova teze, což není způsobeno církví nebo Turingem, ale bylo spíše realizováno postupně ve vývoji teorie složitosti. Uvádí:^[54] "A pravděpodobnostní Turingův stroj umí efektivně simulovat jakýkoli realistický model výpočtu. “Slovo„ efektivně “zde znamená až polynomiální časové redukce. Tato práce se původně jmenovala výpočetní složitost - teoretická církev – Turingova práce od Ethana Bernsteina a Umesh Vazirani (1997). Teorie složitosti podle Církve – Turingovy práce tedy předpokládá, že všechny „rozumné“ modely výpočtu přinášejí stejnou třídu problémů, jaké lze vypočítat v polynomiálním čase. Za předpokladu domněnky, že pravděpodobnostní polynomiální čas (BPP ) rovná se deterministický polynomiální čas (P ), slovo „pravděpodobnostní“ je volitelné v teorii složitosti-Church-Turingova práce. Podobná teze, zvaná invariance práce, představili Cees F. Slot a Peter van Emde Boas. Uvádí: "„Rozumné“ stroje se mohou navzájem simulovat v polynomiálně ohraničené režii v čase a režii s konstantním faktorem v prostoru. “^[55] Práce se původně objevila v příspěvku na adrese STOC '84, což byl první dokument, který ukázal, že režie v polynomiálním čase a režii v konstantním prostoru mohou být zároveň dosažené pro simulaci a Stroj s náhodným přístupem na Turingově stroji.^[56]

Li BQP se ukazuje jako přísná nadmnožina BPP, to by zneplatnilo teorii Church-Turingovy teorie složitosti. Jinými slovy, bylo by to efektivní kvantové algoritmy které provádějí úkoly, které nemají efektivní výkon pravděpodobnostní algoritmy. To by však nevyvrátilo platnost původní Church-Turingovy teze, protože kvantový počítač lze vždy simulovat Turingovým strojem, ale zneplatnilo by to klasickou teoreticko-teoretickou teorii Church-Turing z důvodu efektivity. V důsledku toho kvantová složitost - teoretická církev – Turingova teze uvádí:^[54] "A kvantový Turingův stroj dokáže efektivně simulovat jakýkoli realistický model výpočtu. “

Eugene Eberbach a Peter Wegner tvrdí, že teze Church-Turing je někdy interpretována příliš široce a uvádí „širší tvrzení, že algoritmy přesně zachycují to, co lze vypočítat, je neplatné“.^{[57][stránka potřebná ]} Tvrdí, že formy výpočtu nezachycené v práci jsou dnes relevantní, termíny, které nazývají super-Turingův výpočet.

Filozofické důsledky

Filozofové interpretovali tezi Church-Turing jako důsledky pro filozofie mysli.^[58][59][60] B. Jack Copeland uvádí, že jde o otevřenou empirickou otázku, zda existují skutečné deterministické fyzikální procesy, které z dlouhodobého hlediska unikají simulaci pomocí Turingova stroje; dále uvádí, že jde o otevřenou empirickou otázku, zda jsou takové procesy zapojeny do fungování lidského mozku.^[61] Existuje také několik důležitých otevřených otázek, které se zabývají vztahem mezi církevně-turingovou tezí a fyzikou a možností hyperpočítání. Při aplikaci na fyziku má práce několik možných významů:

1. Vesmír je ekvivalentní Turingovu stroji; tedy výpočet nerekurzivní funkce je fyzicky nemožné. Toto bylo nazváno silnou tezí Církev – Turing, nebo Princip Church – Turing – Deutsch, a je základem digitální fyzika.
2. Vesmír není ekvivalentní s Turingovým strojem (tj. Zákony fyziky nejsou Turingově vypočítatelné), ale nepočitatelné fyzikální události nejsou „využitelné“ pro konstrukci hyperpočítač. Například vesmír, ve kterém fyzika zahrnuje náhodné reálná čísla, naproti tomu vypočítatelné reals, spadá do této kategorie.
3. Vesmír je hyperpočítač, a je možné sestavit fyzická zařízení k využití této vlastnosti a k ​​výpočtu nerekurzivních funkcí. Například jde o otevřenou otázku, zda všechny kvantově mechanické události jsou Turingovy vypočítatelné, i když je známo, že přísné modely jako např kvantové Turingovy stroje jsou ekvivalentní deterministickým Turingovým strojům. (Nejsou nutně efektivně ekvivalentní; viz výše.) John Lucas a Roger Penrose naznačují, že lidská mysl může být výsledkem nějakého druhu kvantově mechanicky vylepšeného „nealgoritmického“ výpočtu.^[62][63]

Existuje mnoho dalších technických možností, které spadají mimo nebo mezi tyto tři kategorie, ale slouží k ilustraci rozsahu konceptu.

Filozofické aspekty práce týkající se fyzických i biologických počítačů jsou rovněž diskutovány v Odifreddiho učebnici teorie rekurze z roku 1989.^{[64]:101–123}

Nepočítatelné funkce

Lze formálně definovat funkce, které nelze vypočítat. Známým příkladem takové funkce je Busy Bobr funkce. Tato funkce přijímá vstup n a vrátí největší počet symbolů, které a Turingův stroj s n státy mohou tisknout před zastavením, když jsou spuštěny bez vstupu. Nalezení horní hranice funkce zaneprázdněného bobra je ekvivalentní řešení zastavení problému, o kterém je známo, že je Turingovými stroji neřešitelný. Protože funkci zaneprázdněného bobra nemohou Turingovy stroje vypočítat, práce Church-Turing uvádí, že tuto funkci nelze efektivně vypočítat žádným způsobem.

Několik výpočetních modelů umožňuje výpočet (Church-Turing) nevypočitatelných funkcí. Tito jsou známí jakohyperpočítače Mark Burgin to tvrdí super-rekurzivní algoritmy jako jsou indukční Turingovy stroje vyvracejí tezi Church-Turing.^{[65][stránka potřebná ]} Jeho argument se opírá o definici algoritmu, který je širší než běžný, takže nevypočitatelné funkce získané z některých indukčních Turingových strojů se nazývají vypočítatelné. Tato interpretace teze Church-Turing se liší od interpretace běžně přijímané v teorii vypočítatelnosti, diskutované výše. Argument, že super-rekurzivní algoritmy jsou skutečně algoritmy ve smyslu teze Church-Turing, nenašel v komunitě pro výzkum vypočítatelnosti široké přijetí.^{[Citace je zapotřebí ]}

Viz také

• Abstraktní stroj
• Církevní práce v konstruktivní matematice
• Princip Church – Turing – Deutsch, který uvádí, že každý fyzický proces lze simulovat pomocí univerzálního výpočetního zařízení
• Logika vypočítatelnosti
• Teorie vypočítatelnosti
• Rozhodnutelnost
• Hyperpočítání
• Model výpočtu
• Oracle (počítačová věda)
• Super-rekurzivní algoritmus
• Turingova úplnost

Poznámky pod čarou

Reference

externí odkazy

• "The Church–Turing Thesis" vstup od B. Jack Copeland v Stanfordská encyklopedie filozofie.
• "Computation in Physical Systems" vstup od Gualtiero Piccinini v Stanfordská encyklopedie filozofie —a comprehensive philosophical treatment of relevant issues.
• Kaznatcheev, Artem (September 11, 2014). "Transcendental idealism and Post's variant of the Church-Turing thesis". Journal of Symbolic Logic. 1 (3): 103–105.
• A speciální problém (Vol.28, No.4, 1987) of the Deník Notre Dame formální logiky was devoted to the Church-Turing thesis.