Historia Kościoła – teza Turinga

Historia tezy Churcha-Turinga ( „tezy”) obejmuje historię rozwoju badań nad naturą funkcji, których wartości są efektywnie obliczalne; lub, mówiąc bardziej nowocześnie, funkcje, których wartości są obliczalne algorytmicznie. Jest to ważny temat we współczesnej teorii matematycznej i informatyce, szczególnie związany z pracami Alonzo Churcha i Alana Turinga .

Debata i odkrycie znaczenia „obliczeń” i „rekurencji” były długie i kontrowersyjne. Ten artykuł zawiera szczegóły tej debaty i odkrycia z aksjomatów Peano w 1889 roku poprzez niedawną dyskusję na temat znaczenia „ aksjomatu ”.

Dziewięć aksjomatów arytmetyki Peano

W 1889 roku Giuseppe Peano przedstawił swoje Zasady arytmetyki, przedstawione nową metodą , opartą na pracy Dedekinda . Soare sugeruje, że powstanie „prymitywnej rekurencji” zaczęło się formalnie od aksjomatów Peano, chociaż

„Na długo przed dziewiętnastym wiekiem matematycy stosowali zasadę definiowania funkcji przez indukcję. Dedekind 1888 udowodnił, używając przyjętych aksjomatów, że taka definicja definiuje funkcję jednoznaczną, i zastosował ją do definicji funkcji m+n, mxn, i m n . Opierając się na tej pracy Dedekinda, Peano 1889 i 1891 napisał znane pięć [sic] aksjomatów dla dodatnich liczb całkowitych. Jako dodatek do swojego piątego [sic] aksjomatu, indukcji matematycznej, Peano użył definicji przez indukcję, która ma nazywano pierwotną rekurencją (od Pétera 1934 i Kleene 1936)… ”.

Zauważ, że w rzeczywistości aksjomatów Peano jest 9 , a aksjomat 9 jest aksjomatem rekurencji/indukcji.

„Następnie 9 zostało zredukowanych do 5, ponieważ„ Aksjomaty 2, 3, 4 i 5, które dotyczą tożsamości, należą do podstawowej logiki. Pozostaje pięć aksjomatów, które stały się powszechnie znane jako „aksjomaty Peano… Peano przyznaje (1891b, s. 93), że jego aksjomaty pochodzą od Dedekinda…”.

Hilbert i problem Entscheidungs

Na Międzynarodowym Kongresie Matematyków (ICM) w 1900 roku w Paryżu słynny matematyk David Hilbert postawił zestaw problemów – obecnie znanych jako problemy Hilberta – jego latarnia oświetlająca drogę matematykom XX wieku. Problemy 2. i 10. Hilberta wprowadziły problem Entscheidungs ​​(„problem decyzyjny”). W swoim drugim problemie poprosił o dowód, że „arytmetyka” jest „ spójna ”. Kurta Godela udowodniłby w 1931 r., że w ramach tego, co nazwał „P” (obecnie nazywanego arytmetyką Peano ), „istnieją zdania [zdania] nierozstrzygalne”. Z tego powodu „spójność P jest nie do udowodnienia w P, pod warunkiem, że P jest niesprzeczne”. Chociaż dowód Gödla pokazałby narzędzia niezbędne Alonzo Churchowi i Alanowi Turingowi do rozwiązania problemu Entscheidungs, on sam nie odpowiedziałby na nie.

Pytanie o „Entscheidungsproblem” faktycznie pojawia się w ramach 10. problemu Hilberta . Istotą sprawy było następujące pytanie: „Co mamy na myśli, kiedy mówimy, że funkcja jest„ efektywnie obliczalna ””? Odpowiedź brzmiałaby mniej więcej w ten sposób: „Kiedy funkcja jest obliczana za pomocą mechanicznej procedury (procesu, metody)”. Chociaż w dzisiejszych czasach łatwo je sformułować, pytanie (i odpowiedź) krążyło wokół przez prawie 30 lat, zanim zostało precyzyjnie sformułowane.

Oryginalny opis problemu 10 przez Hilberta zaczyna się następująco:

" 10. Wyznaczanie rozwiązywalności równania diofantycznego . Mając równanie diofantyczne z dowolną liczbą nieznanych wielkości i wymiernymi współczynnikami całkowymi : Wymyślić proces , zgodnie z którym w skończonej liczbie operacji można określić , czy równanie jest rozwiązywalne w liczbach wymiernych”.

Do 1922 r. Konkretne pytanie o „Entscheidungsproblem” zastosowane do równań diofantycznych rozwinęło się w bardziej ogólne pytanie o „metodę decyzyjną” dla dowolnego wzoru matematycznego . Martin Davis wyjaśnia to w ten sposób: Załóżmy, że mamy do czynienia z „procedurą obliczeniową”, która składa się z (1) zestawu aksjomatów i (2) logicznego wniosku zapisanego w logice pierwszego rzędu , to znaczy — zapisanego w tym, co Davis nazywa „metodą Fregego” . reguły dedukcji” (lub współczesny odpowiednik logiki boolowskiej ). Rozprawa doktorska Gödla dowiodła, że ​​​​reguły Fregego są kompletne „… w tym sensie, że każda ważna formuła jest możliwa do udowodnienia”. Biorąc pod uwagę ten zachęcający fakt, czy mogłaby istnieć uogólniona „procedura obliczeniowa”, która powiedziałaby nam, czy wniosek można wyciągnąć z jej przesłanek? Davis nazywa takie procedury obliczeniowe „ algorytmami ”. Entscheidungsproblem byłby również algorytmem. „W zasadzie algorytm [the] Entscheidungsproblem zredukowałby całe ludzkie rozumowanie dedukcyjne do brutalnej kalkulacji”.

Innymi słowy: czy istnieje „algorytm”, który może nam powiedzieć, czy jakakolwiek formuła jest „prawdziwa” (tj. algorytm, który zawsze poprawnie daje ocenę „prawda” lub „fałsz”?)

„… Hilbertowi wydawało się jasne, że dzięki rozwiązaniu tego problemu, Entscheidungsproblem, powinno być w zasadzie możliwe rozwiązanie wszystkich problemów matematycznych w sposób czysto mechaniczny. Stąd biorąc pod uwagę w ogóle nierozwiązywalne problemy, jeśli Hilbert miał rację , to sam problem Entscheidungs ​​powinien być nierozwiązywalny”.

Rzeczywiście: co z samym algorytmem Entscheidungsproblem? Czy potrafi określić, w skończonej liczbie kroków, czy sam jest „udany” i „prawdziwy” (to znaczy, czy nie wpada w niekończące się „koło” lub „pętlę” i poprawnie zwraca osądzanie „prawdy” lub „fałszu” na temat własnego zachowania i skutków)?

Trzy problemy z drugiego i dziesiątego problemu Hilberta

Na kongresie w 1928 r. [w Bolonii we Włoszech ] Hilbert bardzo dokładnie uszczegóławia pytanie, dzieląc je na trzy części. Poniżej znajduje się podsumowanie Stephena Hawkinga :

  • „1. Udowodnić, że można udowodnić wszystkie prawdziwe twierdzenia matematyczne, czyli kompletność matematyki .
  • „2. Aby udowodnić, że można udowodnić tylko prawdziwe twierdzenia matematyczne, to znaczy spójność matematyki,
  • „3. Aby udowodnić rozstrzygalność matematyki, to znaczy istnienie procedury decyzyjnej rozstrzygającej prawdziwość lub fałszywość dowolnego zdania matematycznego”.

Proste funkcje arytmetyczne nieredukowalne do rekurencji pierwotnej

Gabriel Sudan (1927) i Wilhelm Ackermann (1928) wyświetlają funkcje rekurencyjne , które nie są prymitywnie rekurencyjne:

„Czy istnieją rekursje , których nie da się zredukować do pierwotnej , aw szczególności czy rekurencja może być użyta do zdefiniowania funkcji, która nie jest prymitywnie
rekurencji rekurencyjna ? : istnieją rekursje, które nie są prymitywnie rekurencyjne] autorstwa Ackermanna 1928”.

W kolejnych latach Kleene zauważa, że ​​Rózsa Péter (1935) uprościła przykład Ackermanna („por. też Hilbert- Bernays 1934”) i Raphaela Robinsona (1948). Péter przedstawił inny przykład (1935), w którym wykorzystano argument Cantora dotyczący przekątnej . Péter (1950) i Ackermann (1940) również przedstawili „ rekursje pozaskończone ”, co skłoniło Kleene do zastanowienia się:

„… czy możemy w jakikolwiek dokładny sposób scharakteryzować pojęcie jakiejkolwiek„ rekurencji ”lub klasę wszystkich„ funkcji rekurencyjnych ”.

Kleene konkluduje, że wszystkie „rekursje” obejmują (i) analizę formalną, którą przedstawia w swoim §54 Obliczenia formalne prymitywnych funkcji rekurencyjnych oraz (ii) zastosowanie indukcji matematycznej . Od razu stwierdza, że ​​rzeczywiście definicja Gödla-Herbranda rzeczywiście „charakteryzuje wszystkie funkcje rekurencyjne” - patrz cytat z 1934 r. Poniżej .

Dowód Gödla

W 1930 roku matematycy zebrali się na spotkaniu matematycznym i uroczystości przejścia na emeryturę Hilberta . Oby los chciał,

„na tym samym spotkaniu młody czeski matematyk Kurt Gödel ogłosił wyniki, które zadały mu [opinia Hilberta, że ​​wszystkie trzy odpowiedzi były TAK] poważnym ciosem”.

Ogłosił, że odpowiedź na pierwsze dwa z trzech pytań Hilberta z 1928 roku brzmi NIE.

Następnie w 1931 roku Gödel opublikował swoją słynną pracę O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemów pokrewnych I. We wstępie do tej pracy Martin Davis ostrzega:

„Czytelnika należy ostrzec, że [w tym konkretnym artykule] to, co Gödel nazywa funkcjami rekurencyjnymi , nazywa się teraz prymitywnymi funkcjami rekurencyjnymi . (Poprawiona terminologia została wprowadzona przez Kleene ).”

Rozszerzenie Gödla „efektywnej kalkulacji”

Cytując Kleene (1952): „Charakterystyka wszystkich„ funkcji rekurencyjnych ”dokonała się w definicji„ ogólnej funkcji rekurencyjnej ”Gödla 1934 , który oparł się na sugestii Herbranda ” (Kleene 1952: 274). Gödel wygłosił serię wykładów w Institute for Advanced Study (IAS), Princeton, NJ. We wstępie napisanym przez Martina Davisa Davis zauważa to

„Dr Gödel stwierdził w liście, że w czasie tych wykładów wcale nie był przekonany, że jego koncepcja rekurencji obejmuje wszystkie możliwe rekurencje…”

Dawson twierdzi, że wykłady te miały na celu wyjaśnienie obaw, że „twierdzenia o niezupełności były w jakiś sposób zależne od specyfiki formalizacji”:

„Gödel wspomniał przykład Ackermanna w końcowej części swojego artykułu z 1934 r., jako sposób motywowania koncepcji „ogólnej funkcji rekurencyjnej”, którą tam zdefiniował; ale wcześniej w przypisie 3 już przypuszczał (jako „zasada heurystyczna”) że wszystkie finitywnie obliczalne funkcje można uzyskać za pomocą rekurencji takiego bardziej ogólnego rodzaju.
„Przypuszczenie to wywołało od tego czasu wiele komentarzy. W szczególności, kiedy Martin Davis podjął się opublikowania wykładów Gödla z 1934 r. [w Davis 1965: 41ff], uznał to za wariant Tezy Kościoła ; ale w liście do Davisa… Gödel stwierdził dobitnie, że to „nieprawda”, ponieważ w czasie tych wykładów „wcale nie był przekonany”, że jego koncepcja rekurencji obejmuje „wszystkie możliwe rekurencje”. Powiedział raczej: „Podane tam przypuszczenie odnosi się tylko do równoważności„ procedury skończonej (obliczeniowej) ”i„ procedury rekurencyjnej ”. Aby wyjaśnić tę kwestię, Gödel dodał postscriptum do wykładów, w którym wskazał, że to, co ostatecznie przekonał go, że intuicyjnie obliczalne funkcje pokrywają się z tymi, które są ogólnie rekurencyjne, była praca Alana Turinga ( Turinga 1937 ).
„Niechęć Gödla do uznania ogólnej rekurencyjności lub λ-definiowalności za odpowiednią charakterystykę nieformalnego pojęcia efektywnej obliczalności została szczegółowo zbadana przez kilku autorów [Przypis 248: „Patrz zwłaszcza Davis 1982; Gandy'ego 1980 i 1988; Sieg 1994"]. Panuje zgoda co do tego, że w rzeczywistości ani Gödel, ani Church's formalizmy były tak jasne lub wewnętrznie przekonujące, jak analiza Alana Turinga, a Wilfried Sieg argumentował, że dowody na rzecz Tezy Churcha dostarczane przez „zbieżność różnych pojęć” (fakt, że systemy zaproponowane przez Churcha, Gödla, Posta i Alana Turinga okazało się, że wszystkie mają to samo rozszerzenie) jest mniej przekonujące, niż się powszechnie uważa. Tak więc, niezależnie od wrodzonej ostrożności Gödla, istniały dobre powody jego sceptycyzmu. Ale co w takim razie chciał osiągnąć poprzez swoje pojęcie ogólnej rekurencyjności? ...
„Raczej Gödel uzyskał swoją definicję [klasy ogólnych funkcji rekurencyjnych] poprzez modyfikację idei Herbranda…; a Wilfried Sieg argumentował, że jego prawdziwym celem w końcowej części artykułu z 1934 r. [notatek z wykładu] było „ oddzielić funkcje rekurencyjne od epistemologicznie ograniczonego pojęcia dowodu [Herbranda] poprzez określenie „ mechanicznych reguł wyprowadzania równań”. Co było bardziej ogólne Sieg sugeruje, że pojęcie „ogólnej” rekursywności Gödla polegało na tym, że Herbrand zamierzał scharakteryzować tylko te funkcje, których rekurencyjność można było udowodnić za pomocą środków skończonych [250]”.

Wykłady Gödla w Princeton

Kleene i Rosser dokonali transkrypcji wykładów Gödla z 1934 r. W Princeton. W swoim artykule Ogólne funkcje rekurencyjne liczb naturalnych Kleene stwierdza:

„Definicja ogólnej funkcji rekurencyjnej liczb naturalnych została zaproponowana przez Herbranda Gödelowi i została użyta przez Gödla z ważną modyfikacją w serii wykładów w Princeton w 1934 r.…
” Funkcja rekurencyjna (relacja) w sensie Gödla ... będziemy teraz nazywać pierwotną funkcją rekurencyjną (relacją).

Kościelna definicja „efektywnie obliczalnego”

Artykuł Churcha An Unsolvable Problem of Elementary Number Theory (1936) dowiódł, że problem Entscheidungs ​​był nierozstrzygalny w ramach rachunku λ i ogólnej rekurencji Gödla-Herbranda; ponadto Church przytacza dwa twierdzenia Kleene'a , które dowiodły, że funkcje zdefiniowane w rachunku λ są identyczne z funkcjami określonymi przez rekurencję ogólną:

„Twierdzenie XVI. Każda funkcja rekurencyjna liczb całkowitych dodatnich jest λ-definiowalna. 16
„Twierdzenie XVII. Każda definiowalna przez λ funkcja dodatnich liczb całkowitych jest rekurencyjna. 17
" 16 .... W tej formie został on po raz pierwszy uzyskany przez Kleene....
" 17 Wynik ten został uzyskany niezależnie przez obecnego autora i SC Kleene mniej więcej w tym samym czasie.

Artykuł rozpoczyna się bardzo długim przypisem 3. Interesujący jest również inny przypis 9. Martin Davis stwierdza, że ​​„Ten artykuł jest przede wszystkim ważny ze względu na wyraźne stwierdzenie (znane odtąd jako teza Churcha ), że funkcje, które można obliczyć za pomocą skończonego algorytmu, są właśnie funkcjami rekurencyjnymi, a w konsekwencji można podać wyraźny nierozwiązywalny problem ":

Jak się okaże, tę definicję efektywnej obliczalności można przedstawić w jednej z dwóch równoważnych postaci: (1)… λ-definiowalnej… 2)… rekurencyjnej…. Pojęcie λ-definiowalności jest wspólnie z obecnym autorem i SC Kleene, kolejne kroki w tym kierunku zostały podjęte przez obecnego autora w Annals of Mathematics , t. 34 (1933), s. 863, oraz Kleene w American Journal of Mathematics , t. 57 (1935), s. 219. Pojęcie rekurencyjności w rozumieniu §4 poniżej zawdzięczamy wspólnie Jacquesowi Herbrandowi i Kurtowi Gödelowi , jak tam wyjaśniono. A dowód równoważności tych dwóch pojęć pochodzi głównie od Kleene, ale częściowo także od obecnego autora i JB Rossera… . Propozycja utożsamienia tych pojęć z intuicyjnym pojęciem efektywnej obliczalności jest po raz pierwszy podjęta w niniejszym artykule (ale patrz pierwszy przypis do §7 poniżej).
„Za pomocą metod Kleene ( American Journal of Mathematics , 1935), rozważania niniejszej pracy mogłyby, ze stosunkowo niewielką modyfikacją, zostać przeprowadzone całkowicie w kategoriach λ-definiowalności, bez użycia pojęcia rekurencyjności. Z drugiej strony, od czasu uzyskania wyników niniejszej pracy, Kleene wykazał (patrz jego mający się wkrótce ukazać artykuł „Ogólne funkcje rekurencyjne liczb naturalnych”), że analogiczne wyniki można uzyskać całkowicie w kategoriach rekurencyjności, bez robienia użycie λ-definiowalności. Fakt jednak, że dwie tak skrajnie różne i (zdaniem autora) równie naturalne definicje efektywnej obliczalności okazują się równoważne, wzmacnia siłę przytoczonych poniżej racji, by sądzić, że stanowią one jako ogólną charakterystykę tej pojęcie, które jest zgodne ze zwykłym intuicyjnym jego rozumieniem”.

Przypis 9 znajduje się w sekcji §4 Funkcje rekurencyjne :

9 Ta definicja [„rekurencyjnego”] jest ściśle związana z definicją funkcji rekurencyjnych, którą zaproponował Kurt Gödel podczas wykładów w Princeton, NJ, 1934, i którą przypisał częściowo niepublikowanemu sugestia Jacques'a Herbranda. Główne cechy, w których obecna definicja rekurencyjności różni się od definicji Gödla, wynikają z SC Kleene.
" W nadchodzącym artykule Kleene, zatytułowanym "General recursive functions of natural numbers", ... następuje ... że każda funkcja rekurencyjna w obecnym sensie jest również rekurencyjna w sensie Gödla (1934) i odwrotnie”.

Jakiś czas przed artykułem Churcha An Unsolvable Problem of Elementary Number Theory (1936) doszło do dialogu między Gödelem a Churchem na temat tego, czy definiowalność λ jest wystarczająca do zdefiniowania pojęcia „algorytmu” i „efektywnej obliczalności”.

W Church (1936) widzimy, pod rozdziałem §7 Pojęcie efektywnej obliczalności , przypis 18, który stwierdza, co następuje:

18 Kwestię związku między efektywną obliczalnością a rekurencyjnością (na którą tutaj proponuje się odpowiedzieć, identyfikując te dwa pojęcia) podniósł Gödel w rozmowie z autorem. Odpowiednie pytanie o związek między efektywną obliczalnością a λ-definiowalnością zostało wcześniej zaproponowane przez autora niezależnie.”

Przez „identyfikowanie” Kościoła rozumie się – nie „ustalanie tożsamości” – ale raczej „sprawianie, że jest lub staje się identyczny”, „pojmowanie jako zjednoczone” (jak w duchu, światopoglądzie lub zasadzie) (vt forma) i (vi formie) jako „być lub stać się tym samym”.

Post i „efektywna obliczalność” jako „prawo naturalne”

Posta co do tego, czy rekurencja była adekwatną definicją „efektywnej obliczalności”, a także opublikowanie artykułu Churcha , zachęciły go jesienią 1936 roku do zaproponowania „sformułowania” z „psychologiczną wiernością”: sekwencja spacji lub pól” wykonujących maszynowe „prymitywne czynności” na kartce papieru w każdym pudełku. Pracownik jest wyposażony w „stały niezmienny zestaw kierunków”. Każda instrukcja składa się z trzech lub czterech symboli: (1) etykieta/numer identyfikacyjny, (2) operacja, (3) następna instrukcja j i ; jednakże, jeśli instrukcja jest typu (e) i określenie brzmi „tak”, TO instrukcja j i ' ELSE, jeśli jest to instrukcja „nie” j i . „Pierwotne czyny” są tylko 1 z 5 rodzajów: (a) zaznaczenie papieru w pudełku, w którym się znajduje (lub zakreślenie znaku, który już tam jest), (b) wymazanie znaku (lub wymazanie), (c ) przesuń się o jedno pomieszczenie w prawo, (d) przesuń się o jedno pomieszczenie w lewo, (e) określ, czy kartka jest zaznaczona, czy pusta. Robotnik zaczyna od kroku 1 w pokoju startowym i robi to, co nakazują mu instrukcje. (Zobacz więcej na maszynie post-Turinga ).

Ta sprawa, wspomniana we wstępie o „intuicyjnych teoriach”, spowodowała, że ​​Post ostro zaatakował Churcha:

„Autor spodziewa się, że niniejsze sformułowanie okaże się logicznie równoważne z rekurencyjnością w sensie rozwoju Gödel-Kościoła. 7 Jego celem jest jednak nie tylko przedstawienie systemu o pewnej logicznej mocy, ale także, w jego ograniczonym w dziedzinie wierności psychologicznej. W tym drugim sensie rozważa się coraz szersze sformułowania. Z drugiej strony naszym celem będzie wykazanie, że wszystkie takie dają się logicznie zredukować do sformułowania 1. Przedstawiamy ten wniosek w chwili obecnej jako hipotezę roboczą I naszym zdaniem takie jest utożsamianie przez Churcha efektywnej obliczalności z rekurencyjnością. 8 " (kursywa w oryginale)
7 [szkicuje podejście do dowodu]
8 "Por. Kościół, zamek. cit., s. 346, 356-358. W rzeczywistości praca wykonana już przez Churcha i innych przenosi tę identyfikację znacznie poza etap roboczej hipotezy. Ale ukrywanie tej identyfikacji pod definicją ukrywa fakt, że dokonano fundamentalnego odkrycia w ograniczeniach matematycznej mocy Homo Sapiens i zaślepia nas na potrzebę jego ciągłej weryfikacji .

Innymi słowy, Post mówi: „Tylko dlatego, że tak to zdefiniowałeś , nie czyni tego naprawdę; twoja definicja opiera się wyłącznie na intuicji”. Post szukał czegoś więcej niż definicji: „Powodzenie powyższego programu zmieniłoby dla nas tę hipotezę nie tyle w definicję czy aksjomat, ale w prawo naturalne. Tylko tak, jak się wydaje autorowi , można Twierdzenie Gödla … i wyniki Churcha… zostaną przekształcone we wnioski dotyczące wszystkich logik symbolicznych i wszystkich metod rozwiązywania”.

Ta kontrowersyjna postawa znalazła zrzędliwy wyraz w Alanie Turingu 1939 i pojawi się ponownie w przypadku Gödla, Gandy'ego i Siega.

Turing i obliczalność

Artykuł AM Turinga On Computable Numbers, With an Application to the Entscheidungsproblem został dostarczony Londyńskiemu Towarzystwu Matematycznemu w listopadzie 1936 roku. Ponownie czytelnik musi pamiętać o przestrodze: użyte przez Turinga słowo „komputer” odnosi się do istoty ludzkiej i działanie „komputera”, które nazywa „komputerem”; na przykład stwierdza: „Obliczenia są zwykle wykonywane przez pisanie pewnych symboli na papierze” (s. 135). Ale używa słowa „obliczenia” w kontekście swojej definicji maszyny, a jego definicja liczb „obliczalnych” jest następująca:

„Liczby„ obliczalne ”można krótko opisać jako liczby rzeczywiste, których wyrażenia w postaci ułamków dziesiętnych można obliczyć za pomocą skończonych środków… Zgodnie z moją definicją liczba jest obliczalna, jeśli jej ułamek dziesiętny może zostać zapisany przez maszynę.

Jaka jest definicja jego „maszyny” według Turinga? Turing podaje dwie definicje, pierwszą podsumowującą w §1 Maszyny obliczeniowe , a drugą bardzo podobną w §9. Wyprowadziłem się z jego bardziej szczegółowej analizy działań ludzkiego „komputera”. W odniesieniu do swojej definicji §1 mówi, że „uzasadnienie leży w fakcie, że ludzka pamięć jest z konieczności ograniczona”, a §1 kończy śmiałym stwierdzeniem o proponowanej przez siebie maszynie, używając słowa „wszystko”

„Twierdzę, że te operacje [napisanie symbolu na kwadratowej taśmie, wymazanie symbolu, przesunięcie o jedno pole w lewo, przesunięcie o jedno pole w prawo, wyszukanie symbolu w kwadracie i zmiana konfiguracji maszyny w wyniku zeskanowania jednego symbolu] obejmują wszystkie te, które są używane do obliczania liczby”.

Podkreślenie słowa jeden w powyższym nawiasie jest celowe. W odniesieniu do §9.I zezwala maszynie na zbadanie większej liczby kwadratów; jest to bardziej kwadratowy rodzaj zachowania, który, jak twierdzi, charakteryzuje działania komputera (osoby):

„Maszyna skanuje pola B odpowiadające kwadratom B obserwowanym przez komputer. W dowolnym ruchu maszyna może zmienić symbol na zeskanowanym kwadracie lub może zmienić dowolne ze zeskanowanych pól na inne pole odległe nie więcej niż o L pól od jednego z inne zeskanowane kwadraty ... Opisane właśnie maszyny nie różnią się zasadniczo od maszyn liczących, jak zdefiniowano w §2 [sic], a odpowiadając dowolnej maszynie tego typu, można skonstruować maszynę liczącą do obliczania tej samej sekwencji, to znaczy powiedzieć sekwencję obliczoną przez komputer”.

Turing dalej definiuje „maszynę liczącą” w §2 to (i) „a-maszyna” („maszyna automatyczna”) zgodnie z definicją w §1 z dodatkowym ograniczeniem (ii): (ii) drukuje dwa rodzaje symboli – cyfry 0 i 1 – oraz inne symbole. Liczby 0 i 1 będą reprezentować „sekwencję obliczoną przez maszynę”.

Ponadto, aby określić, czy liczba ma być uważana za „obliczalną”, maszyna musi wydrukować nieskończoną liczbę zer i jedynek; jeśli nie, jest uważany za „okrągły”; w przeciwnym razie uważa się, że jest „bez okręgów”:

„Liczba jest obliczalna, jeśli różni się o liczbę całkowitą od liczby obliczonej przez maszynę bez okręgów”.

Chociaż nie nazywa tego swoją „tezą”, Turing proponuje dowód, że jego „obliczalność” jest równoważna „efektywnej obliczalności” Churcha :

„W niedawnym artykule Alonzo Church przedstawił ideę„ efektywnej obliczalności ”, która jest równoważna mojej„ obliczalności ”, ale jest bardzo różnie zdefiniowana… Dowód równoważności między„ obliczalnością ”a„ efektywną obliczalnością ”jest przedstawiony w załącznik do niniejszej pracy”.

Dodatek : Obliczalność i efektywna obliczalność zaczyna się w następujący sposób; zauważ, że nie wspomina tutaj o rekurencji , aw rzeczywistości jego szkic dowodowy ma jego maszynę przeżuwającą ciągi symboli w rachunku λ i rachunku różniczkowym przeżuwającym „kompletne konfiguracje” jego maszyny, i nigdzie nie wspomina się o rekurencji. Dowód równoważności obliczalności maszynowej i rekurencji musi czekać na Kleene 1943 i 1952:

„Twierdzenie, że wszystkie efektywnie obliczalne (definiowalne przez λ) sekwencje są obliczalne, a jego odwrotność została udowodniona poniżej w zarysie”.

Gandy (1960) zdaje się mylić ten śmiały szkic dowodowy z Tezą Churcha ; patrz 1960 i 1995 poniżej. Co więcej, uważna lektura definicji Turinga prowadzi czytelnika do zauważenia, że ​​Turing twierdził, że „operacje” proponowanej przez niego maszyny w §1 są wystarczające do obliczenia dowolnej obliczalnej liczby, a maszyna imitująca działanie ludzkiego „komputera” jako przedstawiony w §9.I jest odmianą tej proponowanej maszyny. Ten punkt zostanie powtórzony przez Turinga w 1939 roku.

Turing identyfikuje efektywną obliczalność z obliczeniami maszynowymi

Ogromna praca doktorska Alana Turinga w Princeton (pod kierunkiem Alonzo Churcha ) pojawia się jako Systems of Logic Based on Ordinals . W nim podsumowuje poszukiwanie definicji „efektywnie obliczalnego”. Proponuje definicję pokazaną pogrubioną czcionką, która konkretnie identyfikuje (ujednolica) pojęcia „obliczenia maszynowe” i „efektywnie obliczalne”.

„Mówi się, że funkcja jest„ efektywnie obliczalna ”, jeśli jej wartości można znaleźć za pomocą jakiegoś czysto mechanicznego procesu. Chociaż dość łatwo jest intuicyjnie zrozumieć tę ideę, niemniej jednak pożądane jest posiadanie bardziej określonej, wyrażonej matematycznie definicji Taką definicję po raz pierwszy podał Gödel w Princeton w 1934 roku... Funkcje te są opisane przez Gödla jako „ogólne rekurencyjne”… . Inną definicję efektywnej obliczalności podał Church…, który utożsamia ją z definiowalnością λ. Autor ostatnio zaproponował definicję bardziej odpowiadającą idei intuicyjnej (Turing [1], patrz także post [1]). Stwierdzono powyżej, że „funkcja jest skutecznie obliczalna, jeśli jej wartości można znaleźć za pomocą jakiegoś czysto mechanicznego procesu”. Możemy potraktować to stwierdzenie dosłownie, rozumiejąc przez proces czysto mechaniczny taki, który mógłby być przeprowadzony przez maszynę . Możliwe jest podanie matematycznego opisu, w pewnej postaci normalnej, struktur tych maszyn. Rozwój tych idei prowadzi do autorskiego zdefiniowania funkcji obliczalnej i utożsamienia obliczalności † z efektywną obliczalnością . Udowodnienie, że te trzy definicje są równoważne, nie jest trudne, choć nieco pracochłonne.
„† Będziemy używać wyrażenia „funkcja obliczalna” na oznaczenie funkcji obliczalnej przez maszynę i pozwolimy, aby „efektywnie obliczalna” odnosiła się do intuicyjnej idei bez szczególnego utożsamiania się z którąkolwiek z tych definicji. Nie ograniczamy wartości przyjmowanych przez obliczalną funkcją będą liczby naturalne; możemy na przykład mieć obliczalne funkcje zdaniowe .

To jest potężne wyrażenie. ponieważ „identyczność” jest w rzeczywistości jednoznacznym stwierdzeniem warunków koniecznych i wystarczających, innymi słowy, nie ma innych przypadkowości identyfikacji „z wyjątkiem tego, jaką interpretację nadano słowom „funkcja”, „maszyna”, „obliczalny” i „efektywnie wymierny":

Dla wszystkich funkcji: JEŚLI „ta funkcja jest obliczana przez maszynę” TO „ta funkcja jest efektywnie obliczana” ORAZ JEŚLI „ta funkcja jest efektywnie obliczana” TO „ta funkcja jest obliczana przez maszynę”.

Rosser: rekurencja, rachunek λ i tożsamość obliczeniowa maszyny Turinga

Artykuł JB Rossera An Nieformal Exposition of Proofs of Gödel's Theorem and Church's Theorem stwierdza, co następuje:

„Skuteczna metoda” jest tutaj użyta w dość szczególnym znaczeniu metody, której każdy krok jest dokładnie z góry określony i która z pewnością da odpowiedź w skończonej liczbie kroków. W tym szczególnym znaczeniu podano trzy różne dokładne definicje dotychczas 5. Najprostszy z nich do stwierdzenia (za sprawą Posta i Turinga ) mówi zasadniczo, że skuteczna metoda rozwiązania pewnego zestawu problemów istnieje, jeśli można zbudować maszynę, która następnie rozwiąże dowolny problem ze zbioru bez interwencji człowieka poza wstawieniem pytania i (później) odczytaniem odpowiedzi. Wszystkie trzy definicje są równoważne, więc nie ma znaczenia, która z nich jest używana. Co więcej, fakt, że wszystkie trzy są równoważne, jest bardzo mocnym argumentem przemawiającym za poprawnością któregokolwiek z nich.
5 Jedną z definicji podaje Church in I [tj. Church 1936 An Unsolvable Problem of Elementary Number teorii ]. Inna definicja pochodzi od Jacquesa Herbranda i Kurta Gödela . Jest to stwierdzone w I, przypis 3, s. 346. Trzecia definicja została podana niezależnie w dwóch nieco różnych formach przez EL Post… i AM Turing…. Pierwsze dwie definicje są równoważne w I. Trzecia jest równoważna z pierwszymi dwoma przez AM Turinga, Computability and λ-definability [ Journal of Symbolic Logic , tom. 2 (1937), s. 153-163]”.

Kleene i Teza I

Kleene definiuje „ogólne funkcje rekurencyjne” i „częściowe funkcje rekurencyjne” w swoim artykule Recursive Predicates and Quantifiers . Pojawiają się funkcje reprezentujące, operator mu itp. Kontynuuje w §12 Teorie algorytmów , aby przedstawić swoją słynną Tezę I, którą nazwał Tezą Kościoła w 1952 roku:

„Ten heurystyczny fakt, jak również pewne refleksje na temat natury symbolicznych procesów algorytmicznych, skłoniły Churcha do postawienia następującej tezy 22. Ta sama teza jest implicite zawarta w opisie maszyn liczących Turinga 23 .
” Teza I. Każda efektywnie obliczalna funkcja (efektywnie rozstrzygalny predykat) jest ogólnie rekurencyjny.
„Ponieważ brakowało dokładnej matematycznej definicji terminu efektywnie obliczalnego (efektywnie rozstrzygalnego), możemy przyjąć tę tezę wraz z już przyjętą zasadą, z którą jest ona odwrotna, jako jej definicję… teza ma charakter hipotezy – punkt podkreślany przez Posta i Churcha 24. 22
( Church [1] [ An Unsolvable Problem of Elementary Number Theory ]
23 Turing [1] [ O liczbach obliczalnych, z zastosowaniem do Entscheidungsproblem 1936)]
24 Post [1, s. 105] i Kościół [2]

Kleene's Church, Turing i Church-Turing tezy

W swoim rozdziale §60 Kleene definiuje „ tezę Kościoła ” w następujący sposób:

„… dowody heurystyczne i inne względy skłoniły Churcha 1936 do wysunięcia następującej tezy.
Teza I. Każda efektywnie obliczalna funkcja (predykat efektywnie rozstrzygalny) jest ogólnie rekurencyjna.
„Teza ta jest również zawarta w koncepcji maszyny obliczeniowej sformułowanej przez Turinga 1936-7 i Post 1936”.

Na stronie 317 wyraźnie nazywa powyższą tezę „tezą Kościoła”:

„§ 62. Teza Kościoła . Jednym z głównych celów tego i następnego rozdziału jest przedstawienie dowodów na rzecz tezy Kościoła (Teza I §60).”

O „sformułowaniu” Turinga Kleene mówi:

„Sformułowanie Turinga stanowi zatem niezależne stwierdzenie tezy Churcha (w równoważnych słowach). Post 1936 dał podobne sformułowanie”.

Kleene proponuje to, co pokazał Turing: „Obliczalne funkcje Turinga (1936-1937) to takie, które mogą być obliczone przez maszynę zaprojektowaną, zgodnie z jego analizą, do odtwarzania wszelkiego rodzaju operacji, które ludzki komputer mógłby wykonać , pracując zgodnie z wcześniej przypisanymi instrukcjami”.

Kleene definiuje tezę Turinga w następujący sposób:

„§ 70. Teza Turinga . Teza Turinga, że ​​każda funkcja, którą w sposób naturalny można by uznać za obliczalną w ramach jego definicji, tj. przez jedną z jego maszyn, jest równoważna tezie Churcha z Twierdzenia XXX”.

Rzeczywiście, bezpośrednio przed tym stwierdzeniem Kleene stwierdza Twierdzenie XXX:

„Twierdzenie XXX (= Twierdzenia XXVIII + XXIX). Następujące klasy funkcji cząstkowych są współobszerne, tj. mają tych samych członków: (a) cząstkowe funkcje rekurencyjne, (b) funkcje obliczalne, (c) funkcje obliczalne 1/1 . Podobnie z l [mała litera L] całkowicie zdefiniowane przyjęte funkcje Ψ."

Gödel, maszyny Turinga i efektywna obliczalność

Do swojego artykułu z 1931 r. O twierdzeniach formalnie nierozstrzygalnych Gödel dodał notatkę dodaną 28 sierpnia 1963 r. , Która wyjaśnia jego opinię na temat alternatywnych form / wyrazów „systemu formalnego ”. Jeszcze wyraźniej powtarza swoje opinie w 1964 r. (patrz poniżej):

Notatka dodana 28 sierpnia 1963. W wyniku późniejszych postępów, a zwłaszcza faktu, że dzięki pracy AM Turinga 69 można obecnie podać precyzyjną i bezsprzecznie adekwatną definicję ogólnego pojęcia systemu formalnego 70 , całkowicie ogólna wersja twierdzeń VI i XI są teraz możliwe. Oznacza to, że można rygorystycznie udowodnić, że w każdym niesprzecznym systemie formalnym, który zawiera pewną ilość skończonej teorii liczb, istnieją nierozstrzygalne zdania arytmetyczne, a ponadto nie można udowodnić spójności takiego systemu w system.
pojęciem 69 Zob. Turing 1937 , s. 249.
70 . W wykładzie w Princeton (wspomnianym w Princeton University 1946 , s. 11 [zob. Davis 1965, s. 84-88 [tj. Davis s. 84-88]]) zasugerowałem pewne pozaskończone uogólnienia formalizmów, ale są one czymś radykalnie różnią się od systemów formalnych we właściwym tego słowa znaczeniu, których cechą charakterystyczną jest to, że rozumowanie w nich można w zasadzie całkowicie zastąpić urządzeniami mechanicznymi”.
Moim zdaniem termin „system formalny” lub „formalizm” nie powinien być nigdy używany do niczego poza tym

Gödel 1964 - W Postscriptum Gödla do notatek z wykładu z 1934 r. W IAS w Princeton , powtarza, ale jeszcze bardziej odważnie, swoją niezbyt entuzjastyczną opinię na temat skuteczności obliczalności określonej przez Church's λ-definiowalność i rekurencja (musimy wywnioskować, że oba są oczerniane z powodu użycia przez niego „definicji” w liczbie mnogiej w dalszej części). To było w liście do Martina Davisa (prawdopodobnie kiedy montował The Undecidable ). Uderzająca jest powtarzalność niektórych sformułowań:

„W konsekwencji późniejszych postępów, w szczególności faktu, że dzięki pracom AM Turinga można obecnie podać precyzyjną i bezsprzecznie adekwatną definicję ogólnego pojęcia systemu formalnego, istnienie nierozstrzygalnych zdań arytmetycznych i niemożliwość wykazania spójności systemu w tym samym systemie można teraz rygorystycznie udowodnić dla każdego spójnego systemu formalnego zawierającego pewną ilość skończonej teorii liczb.
„Praca Turinga zawiera analizę pojęcia „procedury mechanicznej” (inaczej „algorytmu”, „procedury obliczeniowej” lub „skończonej procedury kombinatorycznej”). Koncepcja ta jest pokazana jako równoważna koncepcji „maszyny Turinga ” . system formalny można po prostu zdefiniować jako dowolną mechaniczną procedurę tworzenia formuł, zwaną formułami dowodliwymi… pojęcie systemu formalnego, którego istotą jest to, że rozumowanie jest całkowicie zastąpione mechanicznymi operacjami na formułach. (Zauważ, że pytanie, czy istnieje istnieją skończone niemechaniczne procedury… nie są równoważne z żadnym algorytmem, nie mają nic wspólnego z adekwatnością definicji „systemu formalnego” i „procedury mechanicznej”.…
jeśli „procedura skończona” jest rozumiana jako „procedura mechaniczna”, na pytanie postawione w przypisie 3 można odpowiedzieć twierdząco na rekurencyjność zdefiniowaną w §9, która jest równoważna z ogólną rekursywnością zdefiniowaną dzisiaj (patrz SC Kleene (1936)
... ) " równoczesny papier przez EL Post (1936) ... . Jeśli chodzi o poprzednie równoważne definicje obliczalności, które jednak są znacznie mniej odpowiednie dla naszych celów, patrz A. Church 1936…”

Przypis 3 znajduje się w treści notatek z wykładów z 1934 r.:

3 Odwrotność wydaje się być prawdziwa, jeśli oprócz rekurencji zgodnie ze schematem (2) dopuszcza się rekursje innych postaci (np. względem dwóch zmiennych jednocześnie). Nie można tego udowodnić, ponieważ pojęcie obliczeń skończonych nie jest zdefiniowane , ale służy jako zasada heurystyczna”.

Davis zauważa, że ​​„w rzeczywistości równoważność między jego definicją [rekurencji] [Gödla] a definicją Kleene'a [1936] nie jest całkiem trywialna. Tak więc, wbrew pozorom, przypis 3 do tych wykładów nie jest stwierdzeniem tezy Churcha . "

Gandy: „obliczenia maszynowe”, dyskretne, deterministyczne i ograniczone do „lokalnej przyczyny” przez prędkość światła

Wpływowy artykuł Robina Gandy'ego zatytułowany Church's Thesis and Principles for Mechanisms pojawia się w Barwise et al. Gandy zaczyna od nieprawdopodobnego wyrażenia Tezy Churcha , sformułowanej w następujący sposób:

"1. Wprowadzenie
"W całym artykule będziemy używać terminu "obliczalny" w odniesieniu do jakiegoś intuicyjnie danego pojęcia, a "obliczalny" w znaczeniu "obliczalny przez maszynę Turinga "; oczywiście dostępnych jest obecnie wiele równoważnych definicji słowa „obliczalny”.
„ Teza Churcha. To, co jest skutecznie obliczalne, jest obliczalne.
”… Zarówno Church, jak i Turing mieli na myśli obliczenia dokonywane przez abstrakcyjną istotę ludzką przy użyciu pewnych mechanicznych pomocy (takich jak papier i ołówek)”

Robert Soare (1995, patrz poniżej) miał problemy z tym sformułowaniem, biorąc pod uwagę artykuł Churcha (1936) opublikowany przed „Dowodem wyrostka robaczkowego” Turinga (1937).

Gandy próbuje „przeanalizować procesy mechaniczne i w ten sposób przedstawić argumenty przemawiające za:

„Teza M. To, co może obliczyć maszyna, jest obliczalne”.

Gandy „wyklucza z rozważań urządzenia, które są zasadniczo maszynami analogowymi… Jedynymi fizycznymi założeniami dotyczącymi urządzeń mechanicznych (por. Zasada IV poniżej) są takie, że istnieje dolna granica wymiarów liniowych każdej atomowej części urządzenia i że istnieje górna granica (prędkość światła) prędkości propagacji zmian”. Ale potem jeszcze bardziej ogranicza swoje maszyny:

„(2) Po drugie, zakładamy, że postęp obliczeń urządzenia mechanicznego można opisać w kategoriach dyskretnych, tak że rozważane urządzenia są w luźnym sensie komputerami cyfrowymi”. (3) Na koniec przypuszczamy, że urządzenie jest
deterministyczne : to znaczy, dalsze zachowanie urządzenia jest jednoznacznie określone po podaniu pełnego opisu jego stanu początkowego.

W rzeczywistości argumentuje na rzecz tej „Tezy M”, którą nazywa swoim „Twierdzeniem”, której najważniejszą „Zasadą” jest „Zasada IV: Zasada przyczynowości lokalnej”:

„Teraz dochodzimy do najważniejszej z naszych zasad. W analizie Turinga wymóg, aby działanie zależało tylko od ograniczonej części zapisu, opierał się na ludzkim ograniczeniu. Zastępujemy to fizycznym ograniczeniem, które nazywamy zasadą lokalnej przyczynowość. Jej uzasadnienie leży w skończonej prędkości rozchodzenia się efektów i sygnałów: współczesna fizyka odrzuca możliwość natychmiastowego działania na odległość”.

W 1985 roku „Teza M” została dostosowana do maszyny Quantum Turinga , w wyniku czego powstała zasada Church-Turing-Deutsch . [ potrzebne źródło ]

Szybować

dokładne badanie obliczalności i rekurencji Soare'a . Cytuje Gödla z 1964 r. (Powyżej) w odniesieniu do „znacznie mniej odpowiedniej” definicji obliczalności i dodaje:

Kleene napisał [1981b, s. 49]: „ Obliczalność Turinga jest wewnętrznie przekonująca”, ale „λ-definiowalność nie jest wewnętrznie przekonująca”, a „ogólna rekurencyjność z trudem taka (jej autor Gödel nie był wówczas wcale przekonany ) … . Większość ludzi akceptuje dziś Tezę Turinga”

Przypis 7 Soare'a (1995) również wychwytuje „zamieszanie” Gandy'ego , ale najwyraźniej trwa ono również w Gandy'm (1988). To zamieszanie stanowi poważny błąd w badaniach i/lub myślach i pozostaje chmurą unoszącą się nad całym jego programem:

7 Gandy rzeczywiście napisał „tezę Churcha”, a nie „tezę Turinga”, jak napisano tutaj, ale z pewnością Gandy miał na myśli tę drugą, przynajmniej w zamyśle, ponieważ Turing nie udowodnił niczego w 1936 roku ani nigdzie indziej na temat ogólnych funkcji rekurencyjnych .

Breger i problem milczących aksjomatów

Breger zwraca uwagę na problem, gdy podchodzi się do pojęcia „aksjomatycznie”, to znaczy, że „system aksjomatyczny” może być w nim osadzony jeden lub więcej milczących aksjomatów, które są niewypowiedziane, gdy prezentowany jest zestaw aksjomatów.

Na przykład podmiot aktywny z wiedzą (i zdolnościami) może być (potencjalnym) fundamentalnym aksjomatem w dowolnym systemie aksjomatycznym: „know-how istoty ludzkiej jest konieczne – know-how, które nie jest sformalizowane w aksjomatach. ¶ ... Matematyka jako czysto formalny system symboli bez człowieka posiadającego wiedzę na temat symboli jest niemożliwa ... "

Cytuje Hilberta :

„W wykładzie uniwersyteckim wygłoszonym w 1905 r. Hilbert uznał za„ absolutnie konieczne ” posiadanie „aksjomatu myśli” lub „aksjomatu istnienia inteligencji” przed sformułowaniem aksjomatów w logice. Na marginesie scenariusza Hilbert dodał później: „a priori filozofów". Sformułował ten aksjomat w następujący sposób: „Potrafię myśleć o przedmiotach i oznaczać je za pomocą prostych symboli, takich jak a, b,..., x, y ,..., aby można je było jednoznacznie rozpoznać. Moja myśl operuje tymi przedmiotami w pewien sposób według pewnych reguł, a moje myślenie jest w stanie wykryć te reguły poprzez obserwację siebie i całkowicie opisać te reguły” [(Hilbert 1905, 219); zob. 62f i 227)]”.

Breger dalej wspiera swój argument przykładami z Giuseppe Veronese (1891) i Hermanna Weyla (1930-1). Następnie omawia problem ówczesnego wyrażania zbioru aksjomatów w określonym języku, tj. języku znanym agentowi, np. niemieckim.

Zobacz więcej na ten temat w Charakterystykach algorytmów , w szczególności opinia Searle'a, że ​​poza wszelkimi obliczeniami musi istnieć obserwator, który nadaje znaczenie użytym symbolom .

Definicje Siega i aksjomatyczne

Na „Feferfest” - 70. urodzinach Solomona Fefermana - Wilfried Sieg po raz pierwszy przedstawia artykuł napisany dwa lata wcześniej zatytułowany „Obliczenia człowieka i maszyny: analiza pojęciowa”, przedrukowany w (Sieg i in. 2002: 390–409). Wcześniej Sieg opublikował „Mechanical Procedures and Mathematical Experience” (w: George 1994, s. 71ff), przedstawiając historię „obliczalności”, poczynając od Richarda Dedekinda , a kończąc w latach pięćdziesiątych na późniejszych artykułach Alana Turinga i Stephena Cole Kleene . Artykuł Feferfest destyluje wcześniejszy artykuł do jego głównych punktów i skupia się głównie na Robina Gandy'ego z 1980 roku. Sieg rozszerza „obliczalność przez maszynę strunową” (ludzki „komputer”) Turinga jako zredukowaną do mechanizmu „obliczalność przez maszynę literową” na równoległe maszyny Gandy'ego.

Sieg cytuje nowsze prace, w tym „prace Kołmogorowa i Uspienskiego nad algorytmami” oraz (De Pisapia 2000), w szczególności model maszyny ze wskaźnikiem KU ) oraz sztuczne sieci neuronowe i twierdzi:

„Rozdzielenie nieformalnej analizy pojęciowej i matematycznego dowodu równoważności jest niezbędne do uznania, że ​​poprawność Tezy Turinga (biorąc ogólnie) spoczywa na dwóch filarach; mianowicie o poprawności warunków ograniczoności i lokalności dla komputerów oraz o poprawności właściwej tezy centralnej. Ten ostatni wyraźnie stwierdza, że ​​obliczenia komputera mogą być bezpośrednio naśladowane przez określony rodzaj maszyny. Niezależnie od tego, jak satysfakcjonująca może być ta linia argumentacji analitycznej, istnieją dwa słabe punkty: luźność warunków ograniczających (Czym są konfiguracje symboliczne? Jakie zmiany mogą wywołać operacje mechaniczne?) i odpowiadająca jej niejasność głównej tezy. Jesteśmy, bez względu na to, jak się obrócimy, w pozycji metodologicznie wciąż niezadowalającej… ”.

Twierdzi, że „krok w kierunku bardziej satysfakcjonującego stanowiska… [poprzez] dalsze odchodzenie od określonych typów konfiguracji i operacji…”

„Często twierdzono, że Turing analizował obliczenia maszyn. Jest to historycznie i systematycznie niedokładne, co powinno być całkiem jasne w mojej prezentacji. Dopiero w 1980 roku uczeń Turinga, Robin Gandy, scharakteryzował obliczenia maszynowe”.

To, czy powyższe stwierdzenie jest prawdziwe, pozostawiamy czytelnikowi do rozważenia. Sieg dalej opisuje analizę Gandy'ego (patrz powyżej 1980). Robiąc to, próbuje sformalizować to, co nazywa „maszynami Gandy'ego” (ze szczegółową analizą w dodatku). O maszynach Gandy:

„… definicja maszyny Gandy'ego jest „abstrakcyjną” definicją matematyczną, która ucieleśnia… właściwości obliczeń równoległych… Po drugie, maszyny Gandy'ego dzielą z grupami i przestrzeniami topologicznymi ogólną cechę abstrakcyjnych definicji aksjomatycznych , a mianowicie to dopuszczają szeroką gamę różnych interpretacji . Po trzecie, ... obliczenia dowolnej maszyny Gandy'ego mogą być symulowane przez maszynę listową, [i] najlepiej rozumieć ją jako twierdzenie o reprezentacji dla pojęcia aksjomatycznego. [pogrubiona czcionka dodana]
„Podejście aksjomatyczne oddaje istotę procesów obliczeniowych w sposób abstrakcyjny. Różnica między dwoma opisanymi przeze mnie typami kalkulatorów sprowadza się do tego, że komputery Turinga modyfikują jedną ograniczoną część stanu, podczas gdy maszyny Gandy'ego działają równolegle na dowolnie wielu ograniczonych częściach. Twierdzenia o reprezentacji gwarantują, że modele aksjomatów są obliczeniowo równoważne maszynom Turinga w ich odmianie literowej.

Notatki

  •   Barwise, Jon , HJ Keisler i K. Kunen , redaktorzy, 1980, The Kleene Symposium , 426 stron, North-Holland Publishing Company, Amsterdam, ISBN 0-444-85345-6
  • Church, A. , 1936a, w (Davis 1965: 88ff), „Nierozwiązywalny problem elementarnej teorii liczb”
  • Church, A., 1936b, w (Davis 1965: 108ff), „Notatka o problemie Entscheidungs”
  • Church, A., 1938, Konstruktywna druga klasa liczbowa , Bull. Amer. Matematyka soc. tom. 44, nr 4, 1938, s. 224–232]
  •   Davis, redaktor Martin , 1965, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions , Raven Press, Nowy Jork, ISBN 0-911216-01-4 . Wszystkie oryginalne prace są tutaj, w tym Gödel, Church, Turing , Rosser, Kleene i Post wymienione w tym artykule. Cenny komentarz Davisa poprzedza większość artykułów.
  •   Davis, Martin, 2001, Silniki logiki: matematycy i pochodzenie komputera , WW Norton & Company, Nowy Jork, ISBN 0-393-04785-7 pbk.
  •   Dawson, John William, Jr., 1997, Dylematy logiczne: życie i twórczość Kurta Gödla , 361 stron, AK Peters, Wellesley, MA, ISBN 1-56881-025-3 , QA29.058D39.
  •   Dawson, John William i John William Dawson, Jr., 2005, Dylematy logiczne: życie i twórczość Kurta Gödla , 362 strony, AK Peters, Wellesley, MA, ISBN 978-1-56881-025-6
  • De Pisapia, N., 2000, Gandy Machines: abstrakcyjny model obliczeń równoległych dla maszyn Turinga, gry w życie i sztucznych sieci neuronowych , praca magisterska, Carnegie Mellon University, Pittsburgh.
  • Dershowitz, Nachum i Gurevich, Yuri , 2007, Naturalna aksjomatyzacja tezy Kościoła , http://research.microsoft.com/~gurevich/Opera/188.pdf
  • Gandy, Robin , 1978, Church's Thesis and the Principles for Mechanisms , w (Barwise i in. 1980:123-148)
  •   George, Alexander (+ red.), 1994, Mathematics and Mind , 216 stron, Nowy Jork, Oxford University Press, ISBN 0-19-507929-9
  • Gödel, K. , 1930, w (van Heijenoort 1967: 592ff), Niektóre wyniki metamatematyczne dotyczące kompletności i spójności
  • Gödel, K., 1931a, w (Davis 1965: 4-38), O formalnie nierozstrzygalnych twierdzeniach Principia Mathematica i systemów pokrewnych. I.
  • Gödel, K., 1931b, w (van Heijenoort 1976: 616ff) O kompletności i spójności
  • Gödel, K., 1934, w (Davis 1965: 39-74), O nierozstrzygalnych twierdzeniach formalnych systemów matematycznych
  • Gödel, K., 1936, w (Davis 1965: 82ff), On The Length of Proofs , „Przetłumaczone przez redaktora z oryginalnego artykułu w Ergenbnisse eines mathematishen Kolloquiums , Heft 7 (1936) s. 23-24”. Cytowane przez Kleene (1952) jako „Über die Lāange von Beweisen”, w Ergebnisse eines math. Koll itp.
  • Gödel, K., 1964, w (Davis 1965: 71ff), Postscriptum
  •   Groshoz, Emily and Breger, Herbert, 2000, The Growth of Mathematical Knowledge , 416 stron, Kluwer Academic Publishers, Dordrect, Holandia, ISBN 0-7923-6151-2 .
  •   Hawking, Stephen , 2005, Bóg stworzył liczby całkowite: przełomy matematyczne, które zmieniły historię , zredagowane, z komentarzem Stephena Hawkinga , Running Press, Filadelfia, ISBN 0-7624-1922-9
  •   Hodges, Andrew , 1983 , Alan Turing: The Enigma , wydanie 1, Simon and Schuster, Nowy Jork, ISBN 0-671-52809-2
  • Kleene, SC , 1935, w (Davis 1965: 236ff) Ogólne funkcje rekurencyjne liczb naturalnych
  •   Kleene, SC, 1971, 1952 (10 wydanie 1991) Wprowadzenie do metamatematyki , 550 stron, North-Holland Publishing Company (Wolters-Noordhoff Publishing) ISBN 0-7204-2103-9
  •   Merriam-Webster Inc., 1983, Ninth New Collegiate Dictionary Webstera , 1563 strony, Merriam-Webster Inc., Springfield, MA, ISBN 0-87779-509-6
  • Post, EL , 1936, w (Davis 1965:288ff), Finite Combinatory Processes - Formulation 1 or The Journal of Symbolic Logic, tom. 1, nr 3 (wrzesień 1936), s. 103–105.
  • Rossera. JB , 1939, Nieformalna ekspozycja dowodów twierdzenia Gödla i twierdzenia Churcha , The Journal of Symbolic Logic. Tom. 4. (1939), s. 53–60 i przedruk w (Davis 1967: 223-230).
  •   Sieg, Wilfried, Richard Sommer i Carolyn Talcott (red.), 2002, Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman, Lecture Notes in Logic 15 , 444 strony, AK Peters, Ltd., ISBN 1-56881 -169-1
  • Soare, Robert , 1996, Computability and Recursion , „Biuletyn logiki symbolicznej 2”, tom 2, numer 3, wrzesień 1996, s. 284–321.
  • Turing, AM (1937) [dostarczone Towarzystwu 1936], „O liczbach obliczeniowych, z zastosowaniem do Entscheidungsproblem” (PDF) , Proceedings of the London Mathematical Society , 2, tom. 42, s. 230–65, doi : 10.1112/plms/s2-42.1.230 i Turing, AM (1938). „O liczbach obliczeniowych, z zastosowaniem do problemu Entscheidungs: poprawka”. Proceedings of London Mathematical Society . 2. Cz. 43 (wyd. 1937). s. 544–6. doi : 10.1112/plms/s2-43.6.544 . (Zobacz też: Davis 1965:115ff)
  • Turing, A., 1939, w (Davis 1965: 154ff), Systemy logiki oparte na liczbach porządkowych
  •   van Heijenoort, Jean , 1976, From Frege To Gödel: A Source Book in Mathematical Logic , 116 stron, 1879–1931, druk 3, druk oryginalny 1967, Harvard University Press, Cambridge Massachusetts, ISBN 0-674-31844-7 (pbk .).

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=History_of_the_Church–Turing_thesis&oldid=1101731183 ”