V teorii vyčíslitelnosti je Church-Turingova teze (také známá jako Church’s thesis, Church’s conjecture and Turingova teze) kombinovaná hypotéza o povaze efektivně vyčíslitelných (vyčíslitelných) funkcí rekurzí (Church’s Thesis), mechanickým zařízením ekvivalentním Turingovu stroji (Turingova teze) nebo použitím Churchova λ-kalkulu:
Tři výpočetní procesy (rekurze, λ-kalkul a Turingův stroj) byly prokázány jako ekvivalentní Alonzo Churchem, Stephenem Kleenem a J.B. Rosserem (1934-6) a Alanem Turingem (1936-7). Přestože Stephen Kleene prokázal, že obě teze jsou ekvivalentní, základní předpoklad tezí – pojem „efektivně vyčíslitelný“ nebo „efektivně vypočitatelný“ – je „neurčitý intuitivní“, který je založen na i) „heuristickém [pozorovacím, zážitkovém] důkazu“, ii) „rovnocennosti „různorodých formulací“ (např. tři výpočetní procesy) a iii) na observační analýze člověka s tužkou a papírem podle souboru pravidel (Turingova analýza) a „pracovníka“ v krabicích (analýza Emila Posta 1936). Tudíž, jak stojí, ani jedna z tezí nemůže být prokázána. Různé pojmy pro „efektivní vypočitatelnost/vyčíslitelnost“ – moucha v masti – byly navrženy jako „formální definice“ Churchem, Turingem a Rosserem, jako „pracovní hypotéza“ vedoucí induktivním uvažováním k „přirozenému zákonu“ Postem (nápad „ostře“ kritizovaný Churchem), nebo jako axiom nebo soubor axiomů (navržený Kurtem Gödelem Churchovi v letech 1934-5, ale zavržený v roce 1936).
Dnes má tato práce téměř univerzální přijetí.
Církev-Turingova teze uvádí, že pokud existuje algoritmus (procedura, která končí), pak existuje ekvivalentní Turingův stroj nebo použitelná λ-funkce pro tento algoritmus.
V následujícím textu budou slova „efektivně vypočitatelný“ znamenat „vyrobený jakýmkoliv intuitivně „efektivním“ prostředkem“ a „vypočitatelný“ budou znamenat „vyrobený Turingovým strojem nebo rovnocenným mechanickým zařízením“.
Turingovy 1939 „definice“ jsou prakticky stejné:
Práci lze konstatovat následovně:
Turingovy uvedl, že tímto způsobem:
Jedním z důležitých problémů pro logicians v 1930s byl David Hilbert Entscheidungsproblem, který se ptal, zda existuje mechanický postup pro oddělení matematických pravd od matematických lží.
V průběhu studia problému Alonzo Church a jeho student Stephen Kleene představili pojem λ-definovatelných funkcí a byli schopni dokázat, že několik velkých tříd funkcí, které se často vyskytují v teorii čísel, bylo λ-definovatelných. Church navrhl Kurtu Gödelovi, že by se měly definovat „efektivně vyčíslitelné“ funkce jako λ-definovatelné funkce. Kurt Gödel však nebyl přesvědčen a označil návrh za „naprosto neuspokojivý“. Jako protinávrh Gödel nabídl svou (primitivní) rekurzi, upravenou Herbrandovým návrhem, že on (Gödel) podrobně popsal ve svých přednáškách v roce 1934 v Princetonu NJ (Kleene a další student J. B. Rosser přepisovali poznámky.) Kleene, s pomocí Churche a Rossera, pak vypracoval důkazy, aby ukázal, že dva kalkuly jsou rovnocenné. Church upravil své metody, aby zahrnovaly použití Herbrand-Gödel rekurze a pak prokázal, že Entscheidungsproblem je neřešitelný: Neexistuje žádný zobecněný „efektivní výpočet“ (metoda, algoritmus), který může určit, zda vzorec v buď rekurzivní- nebo λ-kalkul je nebo není „platný“ (přesněji: že dobře tvarovaný vzorec je v „normální formě“).
Během jednoho roku, ve své 1936-37 papíru „O vypočitatelných čísel, s aplikací na Entscheidungsproblem“ Alan Turing prosadil svou představu o „efektivní vyčíslitelnost“ se zavedením jeho a-stroje (nyní známý jako Turingův stroj abstraktní výpočetní model). Navrhl, stejně jako Church a Kleene před ním, že jeho formální definice mechanické výpočetní agent byl ten správný.
V roce 1964 „Postscriptum“, které přidal do Davisovy antologie The Undecidable, Gödel dále vyjádřil svůj názor, že rekurze a λ-kalkul „jsou pro náš účel mnohem méně vhodné“ . Všimněte si, že do této „méně vhodné“ kategorie zahrnuje vlastní Herbrand-Gödelovu rekurzi.
Původ fráze „Church-Turingova teze“ :
Definice popisuje „význam“ slova, slovní skupiny nebo symbolu; má kolem sebe pojem dogmatického tvrzení: nezpochybnitelné, rozhodnuté. Teze je naopak tvrzení nebo návrh, který někdo tvrdí a pak obhajuje argumentem, nebo „hypotéza“, která má být dokázána (nebo možná jen uplatněna bez důkazu).
Jak Church, tak Turing individuálně navrhovali, aby jejich „formální systémy“ byly definicemi „efektivní kalkulovatelnosti“; ani jeden z nich nezarámoval svá tvrzení jako teze. Post 1936 dokonce nesouhlasil s Churchovým tvrzením o jeho „definici“ a trval na tom, že by to měla být „pracovní hypotéza“.) Rosser (1939) identifikoval (tedy tvrdil rovnocennost) tří pojmů-jako-definic: „Všechny tři definice jsou rovnocenné, takže nezáleží na tom, která z nich je použita.“
Otevřený výraz „teze“ – tedy „hypotéza“ – musel být přenechán Kleenovi. Ve své práci z roku 1943 Rekurzivní predikáty a kvantifikátory Kleene navrhl jeho „THESIS I“:
Kleene jde na vědomí, že:
O několik let později (1952) Kleene by otevřeně jméno, obhajovat, vyjádřit dvě „teze“, jak je citováno v úvodu-v odstavci, a pak „identifikovat“ je (ukázat rovnocennost) pomocí jeho Věta XXX.
Pozdější vývoj: Axiomatizace pojmu „efektivní výpočet/výpočet“
Gödel v korespondenci s kostelem (ca 1934-5) navrhl axiomatizing „efektivní kalkulovatelnost“ (Nakonec Gödel navrhl církvi použití Herbrand-Gödel rekurze jako jeho definice; po Turingova 1936-7 podpořil Turingovy definice):
Pokus o lepší pochopení tohoto pojmu vedl Robina Gandyho (Turingova studenta a přítele) v roce 1980 k analýze strojového počítání (na rozdíl od lidského počítání prováděného Turingovým strojem). Gandyho zvědavost a analýza „buněčných automatů“, „Conwayovy hry na život“, „paralelismu“ a „krystalických automatů“ ho vedla k navržení čtyř „principů (nebo omezení) … které, jak se tvrdí, musí splňovat každý stroj.“ 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.“ Z těchto principů a některých dalších omezení – (1a) dolní mez lineárních rozměrů kterékoli z částí, (1b) horní mez rychlosti šíření (rychlost světla), (2) diskrétní postup stroje a (3) deterministické chování – vytváří větu, že „Co lze vypočítat zařízením vyhovujícím principům I-IV, je vypočitatelné“.
Koncem 90. let Wilfried Sieg analyzoval Turingovy a Gandyho představy o „efektivní kalkulovatelnosti“ se záměrem „zostřit neformální představu, formulovat její obecné rysy axiomaticky a zkoumat axiomatický rámec“. Ve svém roce 2002 předkládá řadu omezení zredukovaných zhruba na: „(B) Boundedness … (L) Locality … (D) Determinancy“.
Jiné formalismy (kromě rekurze, lambda kalkulu a Turingova stroje) byly navrženy pro popis efektivní kalkulovatelnosti/vyčíslitelnosti . Stephen Kleene (1952) přidává na seznam funkce „ počitatelné v systému S1“ Kurta Gödela 1936 a Emila Posta (1943, 1946) „kanonické [také nazývané normální] systémy“. V 50. letech Hao Wang a Martin Davis značně zjednodušili model Turingova stroje s jedním páskem (viz Post-Turingův stroj). Marvin Minsky rozšířil model na dvě nebo více pásek a značně zjednodušil pásky na „nahoru-dolů čítače“, které Melzak a Lambek dále rozvinuli do toho, co je dnes známé jako model počítacího stroje. Na přelomu 60. a 70. let výzkumníci rozšířili model počítacího stroje do registračního stroje, blízkého příbuzného modernímu pojetí počítače. Jiné modely zahrnují kombinační logiku a Markovovy algoritmy. Gurevič přidává model ukazovátka Kolmogorova a Uspenského (1953, 1958): „…chtěli jen … přesvědčit sami sebe, že neexistuje způsob, jak rozšířit pojem výpočetní funkce.“
Všechny tyto příspěvky zahrnují důkazy, že modely jsou výpočetně ekvivalentní Turingovu stroji; takové modely jsou prý Turingovy kompletní. Protože všechny tyto různé pokusy o formalizaci konceptu „efektivní kalkulovatelnosti/vyčíslitelnosti“ přinesly ekvivalentní výsledky, obecně se nyní předpokládá, že Church-Turingova teze je správná. Ve skutečnosti Gödel (1936) navrhl něco silnějšího než toto; poznamenal, že na konceptu „zúčtovatelné v S1“ bylo něco „absolutního“:
Další variací je Strong Church-Turingova práce (SCTT), která není dílem Churche nebo Turinga, ale byla realizována postupně ve vývoji teorie složitosti. Uvádí (srov. Bernstein, Vazirani 1997):
Slovo ‚efektivně‘ zde znamená až redukce polynomiálního času. Strongova Churchova–Turingova teze pak předpokládá, že všechny ‚rozumné‘ modely výpočtu přinášejí stejnou třídu problémů, které lze vypočítat v polynomiálním čase. Za předpokladu, že pravděpodobnostní polynomiální čas (BPP) se rovná deterministickému polynomiálnímu času (P), je slovo ‚pravděpodobnostní‘ ve Strongově–Turingově tezi nepovinné.
Pokud jsou kvantové počítače fyzicky možné, mohly by zneplatnit Strongovu-Turingovu tezi, protože se také předpokládá, že kvantový polynomiální čas (BQP) je větší než BPP. Jinými slovy, existují efektivní kvantové algoritmy, které provádějí úlohy, o kterých není známo, že by měly efektivní pravděpodobnostní algoritmy; například faktoringová celá čísla. Neplatí však původní nebo fyzikální Church-Turingova teze, protože kvantový počítač může být vždy simulován Turingovým strojem.
Filosofické důsledky
Church-Turingova diplomová práce má údajně některé hluboké důsledky pro filozofii mysli. Existují také některé důležité otevřené otázky, které se týkají vztahu mezi Church-Turingovou diplomovou prací a fyzikou a možnosti hypervýpočtů. Při použití ve fyzice má diplomová práce několik možných významů:
Existuje mnoho dalších technických možností, které spadají mimo tyto tři kategorie nebo mezi ně, ale ty slouží k ilustraci rozsahu konceptu.
Lze formálně definovat funkce, které nejsou vypočitatelné. Známým příkladem takové funkce je funkce zaneprázdněného bobra. Tato funkce bere vstupní n a vrací největší počet kroků, které Turingův stroj s n stavy může provést před zastavením, když běží bez vstupu. Pomocí konkrétních modelů Turingových strojů vědci vypočítali hodnotu této funkce pro malé hodnoty n: 0 až 4. Simulace Turingových strojů s 5 a 6 stavy byly provedeny, ale bez přesvědčivých výsledků. Pro vyšší hodnoty byly uvedeny pouze dolní meze. Nalezení horní hranice na funkci zaneprázdněného bobra je ekvivalentní řešení problému zastavení, problému, o kterém je známo, že je neřešitelný Turingovými stroji. Vzhledem k tomu, že funkce zaneprázdněného bobra nemůže být vypočtena Turingovými stroji, Church-Turingova teze tvrdí, že tato funkce nemůže být efektivně vypočtena žádnou metodou.
Mark Burgin, Eugene Eberbach, Peter Kugel a další výzkumníci tvrdí, že superrekurzivní algoritmy, jako jsou induktivní Turingovy stroje, vyvracejí Church-Turingovu tezi. Jejich argument se opírá o definici algoritmu, která je širší než ta obyčejná, takže nevypočítatelné funkce získané z některých induktivních Turingových strojů se nazývají vyčíslitelné. Tato interpretace Church-Turingovy teze se liší od interpretace běžně přijímané v teorii vyčíslitelnosti, diskutované výše. Argument, že superrekurzivní algoritmy jsou skutečně algoritmy ve smyslu Church-Turingovy teze, nenašel široké přijetí v komunitě výzkumníků vyčíslitelnosti.