Church-Turingova diplomová práce

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ě“).

Doporučujeme:  Postvirový únavový syndrom

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é“.

Doporučujeme:  NREM spánek

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é.

Doporučujeme:  Zkoušky státní komise

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.