Church – Turingova práce - Church–Turing thesis

"Church's thesis" přeadresuje tady. Axiom CT v konstruktivní matematice viz Churchova teze (konstruktivní matematika) .

V teorii vyčíslitelnosti je Church-Turingova teze (také známý jako vypočitatelnosti práce je Turing-Church práce je Church-Turingova domněnka , církevní práce , církevní dohad , a Turing práce ) je hypotéza o povaze vyčíslitelných funkcí . Uvádí, že funkci na přirozených číslech lze vypočítat efektivní metodou právě tehdy, je -li vypočitatelná pomocí Turingova stroje . Práce je pojmenována po americkém matematikovi Alonzo Churchovi a britském matematikovi Alanu Turingovi . Před přesnou definicí vypočítatelné funkce matematici často používali neformální termín, který lze efektivně vypočítat, k popisu funkcí, které lze vypočítat metodami typu papír a tužka. V roce 1930 bylo provedeno několik nezávislých pokusů formalizovat pojem vyčíslitelnosti :

  • V roce 1933 Kurt Gödel s Jacquesem Herbrandem formalizovali definici třídy obecných rekurzivních funkcí : nejmenší třída funkcí (s libovolně mnoha argumenty), která je uzavřena pod složením , rekurzí a minimalizací a zahrnuje nulu , nástupce a všechny projekce .
  • V roce 1936 vytvořil Alonzo Church metodu pro definování funkcí nazývanou λ-počet . V rámci λ-kalkulu definoval kódování přirozených čísel nazývaných církevní číslice . Funkce na přirozených číslech se nazývá λ-vyčíslitelná, pokud lze odpovídající funkci na církevních číslicích reprezentovat termínem λ-počtu.
  • Také v roce 1936, před učením se o církevní práci, Alan Turing vytvořil teoretický model pro stroje, nyní nazývané Turingovy stroje, které by mohly provádět výpočty ze vstupů manipulací se symboly na pásce. Vzhledem k vhodnému kódování přirozených čísel jako posloupností symbolů se funkce na přirozených číslech nazývá Turingova vypočítatelná, pokud některý Turingův stroj vypočítá odpovídající funkci na zakódovaných přirozených číslech.

Church, Kleene a Turing dokázali, že tyto tři formálně definované třídy přepočitatelných funkcí se shodují: funkce je λ-vyčíslitelná tehdy a jen tehdy, je-li Turing vypočítatelná, a pokud a pouze pokud je obecná rekurzivní . To vedlo matematiky a počítačové vědce k přesvědčení, že koncepce vyčíslitelnosti je přesně charakterizována těmito třemi ekvivalentními procesy. Další formální pokusy charakterizovat vyčíslitelnost 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 vyčíslitelných funkcí se shodují s neformálním pojmem efektivně vypočítatelné funkce. Ačkoli je práce téměř univerzálně přijatelná, nelze ji formálně prokázat, protože koncept efektivně vypočítatelné je definován pouze neformálně.

Od jejího vzniku vznikaly variace na původní tezi, včetně prohlášení o tom, co lze fyzicky realizovat počítačem v našem vesmíru ( fyzická Church-Turingova práce ) a co lze efektivně vypočítat ( Church – Turingova práce (teorie složitosti) ). Tyto variace nejsou způsobeny Churchem nebo Turingem, ale vyplývají z pozdější práce v teorii složitosti a digitální fyzice . Práce má také důsledky pro filozofii mysli (viz níže ).

Prohlášení v Churchových a Turingových slovech

Viz také: Efektivní metoda

JB Rosser  ( 1939 ) řeší pojem „efektivní vyčíslitelnosti“ takto: „Existence CC a RC (Churchovy a Rosserovy důkazy) zjevně předpokládá přesnou definici„ efektivní “.„ Efektivní metoda “je zde použita v poměrně zvláštním smysl metody, jejíž každý krok je přesně předurčen a který je jistý, že poskytne odpověď v konečném počtu kroků “. Příslovce-přídavné jméno „efektivní“ se tedy používá ve smyslu „1a: vytváření rozhodného, ​​rozhodného nebo požadovaného účinku“ a „schopné dosáhnout výsledku“.

V následujícím textu budou slova „efektivně vypočítatelné“ znamenat „vyrobené jakýmkoli intuitivně„ efektivním “znamená cokoli“ a „efektivně spočí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. Práce se systémy logiky založené na řadové pod dohledem církve, jsou prakticky stejné:

† Použijeme výraz „vyčíslitelná funkce“ ve smyslu funkce spočítatelné strojem a necháme „efektivně vypočítat“ odkazovat na intuitivní myšlenku bez konkrétní identifikace s jakoukoli z těchto definic.

Téze může být vyjádřena jako: Každá efektivně vypočítatelná funkce je vypočítatelná funkce . Church také uvedl, že „Žádný výpočetní postup nebude považován za algoritmus, pokud jej nelze reprezentovat jako Turingův stroj“. Turing to vyjádřil takto:

Bylo uvedeno ... že „funkce je efektivně vypočítatelná, pokud její hodnoty lze zjistit nějakým čistě mechanickým procesem“. Můžeme to brát doslovně s tím, že čistě mechanickým procesem, který by mohl provádět stroj. Vývoj ... vede k ... identifikaci vyčíslitelnosti † s efektivní vypočítatelností. [ † je poznámka pod čarou citovaná výše.]

Dějiny

Hlavní článek: Dějiny církve - Turingova práce

Jedním z důležitých problémů logiky v roce 1930 byl Entscheidungsproblem of David Hilbert a Wilhelm Ackermann , který požádal, jestli tam byl mechanický postup pro oddělení matematické pravdy z matematických lži. Tento úkol vyžadoval, aby byl pojem „algoritmus“ nebo „efektivní vypočítatelnost“ upřesněn, alespoň natolik, aby úkol mohl začít. Ale od samého počátku pokusy Alonzo Church začaly debatou, která pokračuje dodnes. Byl pojem „efektivní vypočítatelnosti“ (i) „axiomem nebo axiomy“ v axiomatickém systému, (ii) pouze definicí, která „identifikovala“ dvě nebo více tvrzení, (iii) empirickou hypotézu, kterou je třeba ověřit pozorováním přírodních událostí, nebo (iv) jen návrh pro argumentaci (tj. „teze“).

Kolem 1930–1952

V průběhu studia problému Church a jeho student Stephen Kleene zavedli pojem definovatelných funkcí λ 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 λ. Debata začala, když Church navrhl Gödelovi, aby „efektivně vyčíslitelné“ funkce definoval jako funkce definovatelné λ. Gödel však nepřesvědčil a návrh označil za „zcela neuspokojivý“. V korespondenci s Churchem (asi 1934–35) Gödel spíše navrhoval axiomatizaci pojmu „efektivní vypočítatelnosti“; v dopise z roku 1935 adresovaném Kleene Church skutečně uvedl, že:

Jeho [Gödelova] 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 základě toho něco udělat .

Ale Gödel nenabídl žádné další vedení. Nakonec navrhl jeho rekurzi, upravenou Herbrandovým návrhem, který Gödel podrobně popsal ve svých přednáškách z roku 1934 v Princetonu v New Jersey (Kleene a Rosser přepsaly poznámky). Nemyslel si však, že tyto dvě myšlenky lze uspokojivě identifikovat „kromě heuristicky“.

Dále bylo nutné identifikovat a prokázat ekvivalenci dvou pojmů efektivní vypočítatelnosti. Vybaven kalkulem λ a „obecnou“ rekurzí vytvořil Stephen Kleene s pomocí Church a J. Barkley Rossera důkazy (1933, 1935), které měly ukázat, že tyto dvě kameny jsou ekvivalentní. Church následně upravil své metody tak, aby zahrnovaly použití rekurze Herbrand – Gödel, a poté dokázal (1936), že problém Entscheidungs je neřešitelný: neexistuje žádný algoritmus, který by určoval, zda dobře formulovaný vzorec má „normální formu“.

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

Hypotéza vedoucí k přirozenému zákonu? : Na konci roku 1936 byl papír Alana Turinga (rovněž prokazující, že problém Entscheidungs je neřešitelný) doručen ústně, ale dosud se v tisku neobjevil. Na druhé straně se objevil papír Emila Posta z roku 1936, který byl certifikován nezávisle na Turingově práci. Post silně nesouhlasil s církevní „identifikací“ efektivní vypočítatelnosti pomocí λ-kalkulu a rekurze, přičemž uvedl:

Ve skutečnosti práce již odvedená církví a dalšími nese tuto identifikaci značně mimo fázi pracovní hypotézy. Ale maskovat tuto identifikaci pod definicí ... nás zaslepuje potřebou jejího neustálého ověřování.

Spíše považoval pojem „efektivní vypočítatelnosti“ za pouhou „pracovní hypotézu“, která by mohla vést spíše induktivním uvažováním k „ přirozenému zákonu “ než „definicí nebo axiomem“. Tuto myšlenku církev „ostře“ kritizovala.

Post tedy ve svém příspěvku z roku 1936 také diskontoval návrh Kurta Gödela na církev v letech 1934–35, že by teze mohla být vyjádřena jako axiom nebo soubor axiomů.

Turing přidává další definici, Rosser rovná všechny tři : Během krátké doby se objevil Turingův dokument 1936–37 „O počitatelných číslech s aplikací na problém Entscheidungsproblem“. V něm uvedl další pojem „efektivní vypočítatelnosti“ se zavedením svých a-strojů (nyní známých jako abstraktní výpočetní model Turingova stroje ). A v náčrtu, který byl přidán jako „dodatek“ k jeho papíru z let 1936–37, Turing ukázal, že třídy funkcí definovaných λ-kalkulem a Turingovými stroji se shodují. Church rychle poznal, jak přesvědčivá byla Turingova analýza. Ve svém přezkoumání Turingova dokumentu objasnil, že Turingův pojem učinil „identifikaci s účinností v běžném (ne výslovně definovaném) smyslu evidentní okamžitě“.

Za několik let (1939) Turing navrhl, stejně jako Church a Kleene před ním, aby jeho formální definice mechanického výpočetního prostředku byla správná. Do roku 1939 tedy Church (1934) i Turing (1939) individuálně navrhli, aby jejich „formální systémy“ byly definicemi „efektivní vypočítatelnosti“; ani neformuloval svá prohlášení jako teze .

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

Všechny tři definice jsou ekvivalentní, takže nezáleží na tom, která je použita.

Kleene navrhuje tezi I : Toto ponechalo zjevné vyjádření „práce“ Kleene. V roce 1943 Kleene navrhl svou „PRÁCI I“:

Tato heuristická skutečnost [obecné rekurzivní funkce lze efektivně vypočítat] ... vedla církev k vyslovení následující teze. Stejná teze implikuje Turingův popis výpočetních strojů.

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

Protože byla požadována přesná matematická definice pojmu efektivně vypočítatelná (efektivně rozhodnutelná), můžeme tuto tezi pojmout ... jako její definici ...

... práce má charakter hypotézy - bod zdůrazněný Postem a církví. Pokud považujeme tezi a její opak za definici, pak hypotéza je hypotéza o aplikaci matematické teorie vyvinuté z definice. Pro přijetí hypotézy existují, jak jsme naznačili, docela přesvědčivé důvody.

Církevně -Turingova teze : Stephen Kleene v úvodu do metamatematiky konečně pokračuje ve formálním pojmenování „Církevní teze“ a „Turingova teze“ pomocí své teorie rekurzivní realizovatelnosti. Kleene přešel od prezentace své práce v terminologii definice Church-Kleene lambda k rekurzivitě Gödel-Kleene (částečné rekurzivní funkce). V tomto přechodu Kleene upravil Gödelovy obecné rekurzivní funkce, aby umožnil důkazy o neřešitelnosti problémů v intuiciismu EJ Brouwera. V jeho absolventské učebnici logiky je představena „Churchova teze“ a základní matematické výsledky jsou prokázány jako nerealizovatelné. Dále Kleene pokračuje v prezentaci „Turingovy práce“, kde se ukazuje, že výsledky jsou nesporné, pomocí svého zjednodušeného odvození Turingova stroje na základě práce Emila Posta. Obě práce jsou prokázány jako ekvivalentní pomocí "Věty XXX".

Teze I. Každá efektivně vypočítatelná funkce (efektivně rozhodnutelný predikát) je obecná rekurzivní .

Věta XXX: Následující třídy dílčích funkcí jsou stejné, tj. Mají stejné členy: (a) částečné rekurzivní funkce, (b) vyčíslitelné funkce ...

Turingova teze: Turingova teze, že každá funkce, která by byla přirozeně považována za vyčíslitelnou, je podle jeho definice, tj. Pomocí jednoho z jeho strojů, vypočítatelná, je ekvivalentní Churchově teorii Věty XXX.

Kleene konečně poprvé používá termín „teze o Church-Turingově“ v části, ve které pomáhá objasnit pojmy v příspěvku Alana Turinga „Problém slova v polovičních skupinách se zrušením“, jak požaduje kritika od Williama Booneho.

Pozdější vývoj

Pokus porozumět pojmu „efektivní vyčíslitelnosti“ lépe 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ů (včetně Conwayovy hry na život ), paralelismus a krystalické automaty ho vedly k tomu, aby navrhl čtyři „principy (nebo omezení) ... o kterých se tvrdí, že každý stroj musí splňovat“. 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í 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í - vytváří větu, že „to, co lze vypočítat zařízením splňujícím zásady I – IV, je vypočítatelné“.

Na konci devadesátých let Wilfried Sieg analyzoval Turingovo a Gandyho pojetí „efektivní vypočítatelnosti“ se záměrem „zostřit neformální představu, formulovat její obecné rysy axiomaticky a zkoumat axiomatický rámec“. V jeho 1997 a 2002, práce Sieg představuje řadu omezení na chování computor - „agenta lidský výpočet, který postupuje mechanicky“. Tato omezení se sníží na:

  • "(B.1) (Ohraničenost) Počet symbolických konfigurací, které může počítač okamžitě rozpoznat, má pevnou hranici."
  • "(B.2) (Ohraničenost) Existuje počet pevných stavů, ve kterých může být počítač pevně stanoven.
  • "(L.1) (Lokalita) Počítač může měnit pouze prvky pozorované symbolické konfigurace.
  • "(L.2) (Lokalita) Počítač může přesunout pozornost z jedné symbolické konfigurace na jinou, ale nové pozorované konfigurace musí být v ohraničené vzdálenosti od bezprostředně dříve pozorované konfigurace.
  • "(D) (Determinacy) Okamžitě rozpoznatelná (pod) konfigurace jednoznačně určuje další výpočetní krok (a id [okamžitý popis])"; uvedl jiným způsobem: „Interní stav počítače spolu s pozorovanou konfigurací jednoznačně opravuje další krok výpočtu a další vnitřní stav.“

Záležitost zůstává v aktivní diskusi v rámci akademické obce.

Diplomová práce jako definice

Na práci nelze pohlížet jako na nic jiného než na běžnou matematickou definici. Komentáře Gödla k tomuto tématu naznačují tento názor, např. „Správnou definici mechanické počitatelnosti stanovil nade vší pochybnost Turing“. Robert I. Soare výslovně uvádí, že tezi nelze považovat za nic jiného než za definici , kde je také argumentováno, že Turingova definice vyčíslitelnosti není o nic méně pravděpodobná jako správná než definice spojité funkce epsilon-delta .

Úspěch práce

Byly navrženy další formalismy (kromě rekurze, λ-kalkulu a Turingova stroje ) pro popis efektivní vypočítatelnosti/vyčíslitelnosti. Stephen Kleene (1952) přidává do seznamu funkce „ započitatelné v systému S 1 “ Kurta Gödela 1936 a Emil Posta (1943, 1946) „ kanonické [také nazývané normální ] systémy “. V roce 1950 Hao Wang a Martin Davis výrazně zjednodušili model páskového Turingova stroje s jednou páskou (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 „čítače nahoru-dolů“, z nichž Melzak a Lambek dále vyvinuli to, co je nyní známé jako model pultového stroje . Na konci šedesátých a na začátku sedmdesátých let vědci rozšířili model pultového stroje na registrační stroj , blízký bratranec moderního pojetí počítače . Jiné modely zahrnují kombinační logiku a Markovovy algoritmy . Gurevich dodává model ukazatele stroje Kolmogorova a Uspenského (1953, 1958): „... jen chtěli ... přesvědčit sami sebe, že neexistuje způsob, jak rozšířit pojem vyčíslitelné funkce.“

Všechny tyto příspěvky zahrnují důkazy o tom, že modely jsou výpočetně ekvivalentní Turingovu stroji; o takových modelech se říká, že jsou Turingovy kompletní . Protože všechny tyto různé pokusy o formalizaci pojmu „efektivní vypočítatelnosti/vypočítatelnosti“ 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 na pojmu „započítatelné v S 1 “ je něco „absolutního “:

Může být také ukázáno, že funkce, která je spočítatelná ['započítatelná'] v jednom ze systémů Si , nebo dokonce v systému transfinitního typu, je již vypočítatelná [započítatelná] v S 1 . Pojem „vyčíslitelný“ [„započítatelný“] je tedy v určitém určitém smyslu „absolutní“, zatímco prakticky všechny ostatní známé metamathematické pojmy (např. Prokazatelné, definovatelné atd.) Závisí v podstatě na systému, pro který jsou definovány. .

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

Důkazy v teorii vyčíslitelnosti často vyvolávají teorii Církev -Turinga neformálním způsobem, aby byla stanovena vypočítatelnost funkcí, přičemž se vyhýbáme (často velmi dlouhým) detailům, které by byly součástí přísného, ​​formálního důkazu. Aby se zjistilo, že je funkce vypočítatelná pomocí Turingova stroje, je obvykle považováno za dostatečné poskytnout neformální anglický popis toho, jak lze funkci efektivně vypočítat, a poté dojít k závěru „tezí Church – Turing“, že funkce je Turingova vypočítatelná (ekvivalentně , částečně rekurzivní).

Dirk van Dalen uvádí pro ilustraci tohoto neformálního použití teze Church -Turing následující příklad:

PŘÍKLAD: Každá nekonečná RE sada obsahuje nekonečnou rekurzivní množinu .

Důkaz: Nechť A je nekonečné RE. Seznamujeme prvky A efektivně, n 0 , n 1 , n 2 , n 3 , ...

Z tohoto seznamu extrahujeme rostoucí sublist: vložte m 0 = n 0 , po konečném počtu kroků najdeme n k takové, že n k > m 0 , dáme m 1 = n k . Tento postup opakujeme, abychom našli m 2 > m 1 atd. Toto poskytne efektivní výpis podmnožiny B = {m 0 , m 1 , m 2 , ...} A, s vlastností m i <m i+ 1 .

Nárok . B je rozhodnutelné. Abychom mohli testovat k v B, musíme zkontrolovat, zda k = m i pro nějaké i. Protože se sekvence m i zvyšuje, musíme vyprodukovat nejvýše k+1 prvků seznamu a porovnat je s k. Pokud se žádný z nich nerovná k, pak k není v B. Protože je tento test účinný, je B rozhodnutelné a podle Churchovy teze rekurzivní.

Aby byl výše uvedený příklad zcela rigorózní, bylo by nutné pečlivě sestrojit Turingův stroj nebo funkci λ, nebo pečlivě vyvolat rekurzivní axiomy, nebo v nejlepším případě 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 efektivní postup je popsán v angličtině při rozhodování o sadě B, teoretik vypočítatelnosti to přijímá jako důkaz, že sada je skutečně rekurzivní.

Variace

Úspěch disertační práce Church – Turing přiměl navrhnout variace této práce. Například fyzikální Church-Turingova teze uvádí: „Všechny fyzicky vyčíslitelné funkce jsou Turing-vypočitatelný.“

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

Variace teze Church – Turing řeší, zda lze efektivně simulovat libovolný, ale „rozumný“ model výpočtu. Říká se tomu teze proveditelnosti , známá také jako ( klasická ) teoretika složitosti-teoretická teze Church – Turing nebo rozšířená teze Church – Turing , která není dána Churchem nebo Turingem, ale byla spíše realizována postupně ve vývoji teorie složitosti . Uvádí: „ Pravděpodobnostní Turingův stroj může účinně simulovat jakýkoli realistický model výpočtu.“ Slovo „efektivně“ zde znamená až polynomiální redukce . Tato práce byla původně nazýván výpočetní složitost-teoretické Church-Turing teze Ethan Bernstein a Umesh Vazirani (1997). Teorie složitosti-teoretická církev-Turingova teze tedy 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 se domněnka, že pravděpodobnostní polynomiální čas ( BPP ) rovná deterministickému polynomiálnímu času ( P ), slovo „pravděpodobnostní“ je v teorii složitosti-teoretické Churchově-Turingově volitelné. Podobnou tezi, zvanou invarianční 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 konstantního faktoru v prostoru.“ Tato práce se původně objevila v příspěvku na STOC '84, což byl první dokument, který ukázal, že pro simulaci stroje s náhodným přístupem na Turingově stroji lze simultánně dosáhnout režie polynomiálního času a režie konstantního prostoru .

Pokud by se ukázalo, že BQP je přísnou nadmnožinou BPP , zneplatnilo by to teorii složitosti a teoretičnosti Church-Turing. Jinými slovy, existovaly by efektivní kvantové algoritmy, které provádějí úkoly, které nemají efektivní pravděpodobnostní algoritmy . To by však nezrušilo původní tezi Church-Turing, protože kvantový počítač může být vždy simulován Turingovým strojem, ale z důvodu efektivity by to zneplatnilo klasickou teorii složitosti-teoretické Church-Turingovy práce. V důsledku toho teze o teorii kvantové složitosti-Church – Turingova teorie uvádí: „ Kvantový Turingův stroj může účinně 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í: „Ačkoli [...] Turingovy stroje vyjadřují chování algoritmů, širší tvrzení, že algoritmy přesně zachycují to, co lze vypočítat, je neplatné“. Tvrdí, že formy výpočtu, které práce nezachytila, jsou dnes relevantní, termíny, které nazývají super-Turingův výpočet .

Filozofické implikace

Filozofové interpretovali tezi Church -Turing, že má důsledky pro filozofii mysli . B. Jack Copeland uvádí, že je otevřenou empirickou otázkou, zda existují skutečné deterministické fyzikální procesy, které v dlouhodobém horizontu unikají simulaci pomocí Turingova stroje; dále uvádí, že je otevřenou empirickou otázkou, zda jsou takové procesy zapojeny do práce lidského mozku. Existuje také několik důležitých otevřených otázek, které pokrývají vztah mezi teorií Církve a Turinga a fyzikou a možnost hypercomputace . 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ích funkcí je fyzicky nemožný. Toto bylo nazýváno silnou teorií Church – Turing nebo Church – Turing – Deutsch a je základem digitální fyziky .
  2. Vesmír není rovnocenný s Turingovým strojem (tj. Fyzikální zákony nelze Turingově spočítat), ale nesporné fyzikální události nejsou „využitelné“ pro konstrukci hyperpočítače . Do této kategorie by například spadal vesmír, ve kterém fyzika zahrnuje náhodná reálná čísla , na rozdíl od vyčíslitelných skutečností.
  3. Vesmír je hyperpočítač a je možné stavět fyzická zařízení, která tuto vlastnost využijí a vypočítají nerekurzivní funkce. Je například otevřenou otázkou, zda jsou všechny kvantově mechanické události spočítatelné Turingem, i když je známo, že rigorózní modely, jako jsou kvantové Turingovy stroje, jsou ekvivalentní deterministickým Turingovým strojům. (Nejsou nutně účinně ekvivalentní; viz výše.) John Lucas a Roger Penrose navrhli, že lidská mysl může být výsledkem nějakého druhu kvantově mechanicky vylepšeného „nealgoritmického“ výpočtu.

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

Filozofické aspekty práce, týkající se fyzických i biologických počítačů, jsou také diskutovány v Odifreddiho učebnici z roku 1989 o teorii rekurze.

Nepočitatelné funkce

Lze formálně definovat funkce, které nelze spočítat. Známým příkladem takové funkce je funkce Busy Beaver . Tato funkce přebírá vstup n a vrací největší počet symbolů, které může Turingův stroj s n stavy vytisknout před zastavením, když je spuštěn bez vstupu. Nalezení horní hranice funkce zaneprázdněného bobra je ekvivalentní řešení problému se zastavením, problému , o kterém je známo, že je Turingovými stroji neřešitelný. Protože funkci Těžký bobr nelze vypočítat pomocí Turingových strojů, teze Church – Turing uvádí, že tuto funkci nelze efektivně vypočítat žádnou metodou.

Několik výpočetních modelů umožňuje výpočet (Church-Turingových) nepočitatelných funkcí. Jsou známé jako hyperpočítače . Mark Burgin tvrdí, že super rekurzivní algoritmy, jako jsou indukční Turingovy stroje, vyvracejí tezi Church-Turing. Jeho argument se opírá o definici algoritmu, která je širší než obyčejná, takže nevyčíslitelné 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 vyčíslitelnosti, o níž byla řeč výše. Argument, že super-rekurzivní algoritmy jsou skutečně algoritmy ve smyslu teze Church-Turing, nenašel široké přijetí v komunitě výzkumných pracovníků.

Viz také

Poznámky pod čarou

Reference

externí odkazy