Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej.

Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego problemu.

W książce dowód wygląda następująco: „załóżmy, że $M_H$ rozwiązuje problem zatrzymania na wejściu $M;x$ , to znaczy decyduje, czy maszyna Turinga zatrzymuje się na wejściu . Zbuduj maszynę Turinga która przyjmuje maszynę Turinga jako input, uruchamia i odwraca wyjście. " Następnie pokazuje, że nie może wytworzyć zadowalającej mocy wyjściowej.x D M M H ( M ; M ) D ( D $M$$x$$D$$M$$M_H(M;M)$$D(D)$

To pozornie arbitralna konstrukcja , szczególnie idea karmienia samym sobą, a następnie sobie samym, dla której chciałbym mieć intuicję. Co przede wszystkim skłoniło ludzi do zdefiniowania tych konstrukcji i kroków?M $D$$M$$D$

Czy ktoś ma wyjaśnienie, w jaki sposób ktoś uzasadniłby swoją drogę do argumentu diagonalizacji (lub innego dowodu), gdyby nie znał tego rodzaju argumentu na początek?

Dodatek do pierwszej rundy odpowiedzi:

Pierwsze odpowiedzi wskazują więc, że udowodnienie nierozstrzygalności problemu zatrzymania było czymś opartym na wcześniejszych pracach Cantora i Russella oraz rozwoju problemu diagonalizacji, i że rozpoczęcie „od zera” oznaczałoby po prostu konieczność ponownego odkrycia tego argumentu.

Słusznie. Jednak nawet jeśli zaakceptujemy argument diagonalizacji jako dobrze zrozumiały, nadal uważam, że istnieje „luka intuicji” w stosunku do problemu zatrzymania. Dowód Cantora na niepoliczalność liczb rzeczywistych wydaje mi się dość intuicyjny; Paradoks Russella tym bardziej.

Co ja nadal nie rozumiem, co mogłoby skłonić kogoś do zdefiniowania na podstawie „S«samodzielnego stosowania» , a następnie ponownie zastosować do siebie. Wydaje się, że jest to mniej związane z diagonalizacją (w tym sensie, że argument Cantora nie miał czegoś takiego), chociaż oczywiście dobrze działa z diagonalizacją po ich zdefiniowaniu.M M ; M $D(M)$$M$$M;M$$D$

PS

@babou podsumował to, co niepokoiło mnie bardziej niż siebie: „Problemem wielu wersji dowodu jest to, że konstrukcje wydają się być wyciągane z magicznego kapelusza”.

W swojej edycji piszesz:

Nadal nie widzę, co zmotywowałoby kogoś do zdefiniowania oparciu o M „samozastosowania” M ; M , a następnie ponownie zastosuj D do siebie. Wydaje się, że jest to mniej związane z diagonalizacją (w tym sensie, że argument Cantora nie miał czegoś takiego), chociaż oczywiście dobrze działa z diagonalizacją po ich zdefiniowaniu.$D(M)$$M$$M;M$$D$

Powszechne „popularne” podsumowanie dowodu Turinga wygląda mniej więcej tak:

„Gdybyśmy mieli maszynę , które mogą zdecydować, czy kolejne Turinga postojów maszyn czy nie, możemy to wykorzystać do skonstruowania innego urządzenia D , które, biorąc pod uwagę to maszyna Turinga M , by powstrzymać wtedy i tylko wtedy, gdy M zrobił nie zatrzymał. Ale potem może przekazać D jako dane wejściowe do siebie, a tym samym uzyskać paradoks: ta maszyna zatrzyma się wtedy i tylko wtedy, gdy się nie zatrzyma! ”$M_H$$D$$M$$M$$D$

Teraz łatwo zauważyć, że powyższe podsumowanie połyskuje nad ważnym szczegółem - zatrzymanie maszyny Turinga zależy również od jej wkładu, którego nie wymieniliśmy! Ale ten problem może być ustalona dość łatwo: po prostu trzeba mieć D odebrać niektóre odpowiednie wejście x M dla każdego urządzenia wejściowego M , przed przekazaniem ich zarówno do M H .$M$$D$$x_M$$M$$M_H$

Jaki jest odpowiedni wybór dla , biorąc pod uwagę, że ostatecznie chcemy wyciągnąć sprzeczność? Cóż, naturalny wybór sugeruje bezpośrednio powyższy dowód „handwavy”, w którym ostatecznie uzyskujemy sprzeczność, uruchamiając maszynę D na sobie.$x_M$$D$

Tak więc, aby zachowanie było naprawdę paradoksalne w tym przypadku, tj. Gdy jest wywoływane jako D ( D ) , chcemy, aby zatrzymanie D ( M ) zależało od zachowania M, gdy jest wywoływane jako M ( M ) . W ten sposób, to otrzymujemy sprzeczność chcemy poprzez ustawienie M = D .$D$$D(D)$$D(M)$$M$ $M(M)$$M = D$

Pamiętaj, że to nie jedyny wybór; moglibyśmy również wyprowadzić tę samą sprzeczność, powiedzmy, konstruując maszynę taki sposób, że D ' ( M ) zatrzymuje się wtedy i tylko wtedy, gdy M ( D ' ) (a nie M ( M ) ) się nie zatrzymuje. Ale, podczas gdy jest oczywiste, że maszyna D można łatwo powielić swoje wejście przed przekazaniem go do M H , to nie jest aż tak oczywiste jak skonstruować maszynę D ' , które powoływania M H z własnym kodem jako wejścia. Zatem używając tego$D'$$D'(M)$$M(D')$$M(M)$$D$$M_H$$D'$$M_H$ zamiast D niepotrzebnie komplikuje dowód i czyni go mniej intuicyjnym.$D'$$D$

Może być po prostu błędem myśleć, że ktoś przemówiłby do tego argumentu, nie czyniąc podobnego argumentu w pewnym momencie wcześniej, w „prostszym” kontekście.

Pamiętaj, że Turing znał przekątny dowód Cantora na niepoliczalność reali. Co więcej, jego praca jest częścią historii matematyki, która obejmuje paradoks Russella (który wykorzystuje argument diagonalizacji) i pierwsze twierdzenie Gödela o niepełności (które wykorzystuje argument diagonalizacji). W rzeczywistości wynik Gödela jest głęboko powiązany z dowodem nierozstrzygalności problemu zatrzymania (i stąd negatywną odpowiedzią na Entscheidungsproblem Hilberta).

Dlatego uważam, że twoje pytanie jest w pewnym sensie źle uzasadnione i że nie możesz dotrzeć do problemu zatrzymania, nie przechodząc wcześniej przez resztę (lub coś niezwykle podobnego). Podczas gdy pokazujemy te rzeczy studentom bez przeglądania historii, jeśli jesteś pracującym matematykiem, wydaje się mało prawdopodobne, aby przejść od niczego do Turing Machines bez niczego pośredniego - ich celem było sformalizowanie obliczeń, problem wielu ludzi miał pracowałem nad tym przez dziesięciolecia.

Cantor nawet nie zastosował diagonalizacji w swoim pierwszym dowodzie niepoliczalności reali, jeśli weźmiemy daty publikacji jako przybliżenie, kiedy pomyślał o pomyśle (nie zawsze wiarygodna rzecz), zajęło mu około 17 lat od poznania że reale były niepoliczalne, aby wypracować argument diagonalizacji.

W odniesieniu do „samozastosowania” w dowodzie, o którym wspominasz, jest to również integralna część paradoksu Russella (który całkowicie zależy od autoreferencji), a pierwsze twierdzenie Gödela jest jak mocna wersja paradoksu Russella . Dowód na nierozstrzygalność problemu zatrzymania jest tak mocno poinformowany przez pracę Gödela, że ​​trudno sobie wyobrazić dotarcie tam bez niego, dlatego pomysł „samozastosowania” jest już częścią podstawowej wiedzy, której potrzebujesz, aby dostać się do problemu zatrzymania . Podobnie dzieło Gödela jest przerobieniem paradoksu Russella, więc nie można się tam dostać bez drugiego (zauważ, że Russell nie był pierwszym, który zaobserwował taki paradoks, więc prototypy argumentu diagonalizacji pojawiły się w formalnej logice od około 600 pne). Zarówno prace Turinga, jak i Gödela (fragmenty, o których tu mówimy) mogą być postrzegane jako coraz skuteczniejsze pokazy problemów z odniesieniem do samego siebie i tego, jak są one osadzone w matematyce. Ponownie więc bardzo trudno jest zasugerować, że pojawiły się te pomysły na poziomie, na którym Turing się zajmowała priori były one kulminacją prac tysiącleci w dziedzinie filozofii, matematyki i logiki.

To samo-odniesienie jest również częścią argumentu Cantora, po prostu nie jest przedstawione w tak nienaturalnym języku, jak bardziej fundamentalna logiczna praca Turinga. Diagonalizację Cantora można przeformułować jako wybór elementów z zestawu mocy zestawu (zasadniczo część twierdzenia Cantora). Jeśli weźmiemy pod uwagę zbiór (dodatnich) liczb rzeczywistych jako podzbiory naturali (pamiętaj, że tak naprawdę nie potrzebujemy cyfr, aby to działało, to po prostu ułatwia prezentację) i twierdzimy, że istnieje przypuszczenie, że naturals ma rzeczywistości, możemy wytworzyć element zestawu mocy (tj. rzeczywistego), który nie jest obrazem przypuszczenia (i stąd wywodzi sprzeczność), przyjmując ten element za zbiór naturali, którzy nie są sobą obraz pod zastrzeżeniem. Gdy sformułujemy to w ten sposób, „

Własna aplikacja nie jest niezbędnym składnikiem dowodu

W skrócie

Jeśli istnieje maszyna Turinga która rozwiązuje problem zatrzymania, to z tej maszyny możemy zbudować inną maszynę Turinga L o zachowaniu zatrzymania (funkcja charakterystyczna zatrzymania), która nie może być zachowaniem zatrzymania żadnej maszyny Turinga.$H$$L$

Paradoks zbudowany na samodzielnie stosowanej funkcji (zwanej w tej odpowiedzi L - przepraszam za niespójności notacji) nie jest niezbędnym składnikiem dowodu, ale urządzeniem używanym z konstrukcją jednej specyficznej sprzeczności, ukrywającej coś, co wydaje się być „prawdziwym” cel ”konstrukcji. Prawdopodobnie dlatego nie jest intuicyjny.$D$$L$

Bardziej bezpośrednie wydaje się wykazanie, że istnieje tylko znaczna liczba zachowań zatrzymania (nie więcej niż maszyny Turinga), które można zdefiniować jako charakterystyczne funkcje zatrzymania związane z każdą maszyną Turinga. Konstrukcyjnie można zdefiniować charakterystyczną funkcję zatrzymania, której nie ma na liście, i zbudować z niej oraz z maszyny która rozwiązuje problem zatrzymania, maszyny L, która ma tę nową charakterystyczną funkcję zatrzymania. Ponieważ jednak z konstrukcyjnego punktu widzenia nie jest to charakterystyczna funkcja zatrzymywania maszyny Turinga, L nie może być jednym. Ponieważ L jest zbudowany z H przy użyciu technik budowy maszyn Turinga, H nie może być maszyną Turinga.$H$$L$$L$$L$$H$$H$

Samo zastosowanie do siebie, użyte w wielu dowodach, jest sposobem na pokazanie sprzeczności. Działa to jednak tylko wtedy, gdy niemożliwa funkcja zatrzymania charakterystycznego jest zbudowana z przekątnej listy dozwolonych funkcji zatrzymania charakterystycznego Turinga, poprzez odwrócenie tej przekątnej (zamiana 0 i 1 ). Ale istnieje nieskończenie wiele innych sposobów budowania nowej charakterystycznej funkcji zatrzymania. Wtedy nie można już udowodnić braku Turinga paradoksem kłamców (przynajmniej nie tylko). Konstrukcja do samodzielnego zastosowania nie jest intuicyjna, ponieważ nie jest niezbędna, ale wygląda na płynną po wyciągnięciu z magicznego kapelusza.$L$$0$$1$

Zasadniczo nie jest maszyną Turinga, ponieważ od samego początku jest zaprojektowany tak, aby zachowywał się tak, jak maszyna Turinga, i którą można pokazać bardziej bezpośrednio, a zatem bardziej intuicyjnie.$L$

Uwaga : może się zdarzyć, że przy każdym konstruktywnym wyborze niemożliwej charakterystycznej funkcji zatrzymania istnieje obliczalna zmiana kolejności wyliczenia maszyny Turinga w taki sposób, że staje się przekątna (nie wiem). Ale, imho, nie zmienia to faktu, że samodzielna aplikacja jest techniką pośredniego dowodu, która ukrywa bardziej intuicyjny i interesujący fakt.

Szczegółowa analiza dowodów

Nie zamierzam być historią (ale dzięki tym, którzy to lubią), ale staram się działać tylko intuicyjnie.

Wydaje mi się, że prezentacja podana przez @vzn , z którą zetknąłem się dawno temu (zapomniałem), jest w rzeczywistości raczej intuicyjna, a nawet wyjaśnia nazwę przekątnej. Powtarzam to szczegółowo, ponieważ uważam, że @vzn nie podkreślił wystarczająco swojej prostoty.

Moim celem jest mieć intuicyjny sposób na odzyskanie dowodu, wiedząc, że Cantor. Problemem wielu wersji dowodu jest to, że konstrukcje wydają się być wyciągane z magicznego kapelusza.

Dowód, który przedstawiam, nie jest dokładnie taki sam jak w pytaniu, ale jest poprawny, o ile widzę. Jeśli nie popełniłem błędu, jest on wystarczająco intuicyjny, ponieważ mógłbym go odzyskać po latach, które liczę, i pracować nad bardzo różnymi zagadnieniami.

Przypadek podzbiorów (Cantor)$\mathbb N$

Dowód Cantor zakłada (jest tylko hipoteza), że nie jest to wyliczenie podzbiorów liczb całkowitych, tak, aby wszystkie podzbiorze można przedstawić jego funkcja charakterystyczna C j ( I ) , który jest 1 , jeżeli i ∈ S j w przeciwnym razie wynosi 0 .$S_j$$C_j(i)$$1$$i\in S_j$$0$

Może to być postrzegane jako tabela , tak że T [ i , j ] = C j ( i $T$$T[i,j]=C_j(i)$

Następnie, biorąc pod uwagę przekątną, budujemy charakterystyczną funkcję taką, że D ( i ) = ¯ T [ i , i ] , tj. Jest identyczna z przekątną stołu z każdym bitem odwracanym do drugiej wartości.$D$$D(i)=\overline{T[i,i]}$

W przekątnej nie ma nic specjalnego, poza tym, że jest to łatwy sposób na uzyskanie charakterystycznej funkcji która różni się od wszystkich innych i to wszystko, czego potrzebujemy.$D$

Dlatego podzbiór charakteryzowany przez nie może być w wyliczeniu. Ponieważ byłoby to prawdą jakiegokolwiek wyliczenia, nie może być wyliczenie, które wylicza wszystkie podzbiory N .$D$$\mathbb N$

Jest to wprawdzie, zgodnie z początkowym pytaniem, dość intuicyjne. Czy możemy uczynić dowód problemu zatrzymania za intuicyjny?

Przypadek problemu zatrzymania (Turing)

Zakładamy, że mamy wyliczenie maszyn Turinga (które, jak wiemy, są możliwe). Zahamowanie zachowanie Turingowi urządzenie można przedstawić charakterystycznej funkcji zatrzymania H j ( I ) , który jest 1 , gdy M j postojów na wejścia I i 0 inaczej.$M_j$$H_j(i)$$1$$M_j$$i$$0$

Można to postrzegać jako tabelę , taką że T [ i , j ] = H j ( i $T$$T[i,j]=H_j(i)$

Następnie, biorąc pod uwagę przekątną, budujemy charakterystyczną funkcję zatrzymania taką, że D ( i ) = ¯ T [ i , i ] , tj. Jest identyczna z przekątną stołu z każdym bitem odwracanym do drugiej wartości.$D$$D(i)=\overline{T[i,i]}$

W przekątnej nie ma nic specjalnego, poza tym, że jest to łatwy sposób na uzyskanie charakterystycznej funkcji zatrzymania która różni się od wszystkich innych i to wszystko, czego potrzebujemy (patrz uwaga na dole).$D$

Zatem zachowanie zatrzymania charakteryzowane przez nie może być w wyliczeniu maszyną Turinga. Ponieważ wymieniliśmy je wszystkie, dochodzimy do wniosku, że nie ma maszyny Turinga o takim zachowaniu.$D$

Nie zatrzymując oracle tak daleko, a nie hipoteza Obliczalność : Nie wiemy nic o obliczalności wiedzieć i funkcji H j .$T$$H_j$

Załóżmy teraz, że mamy maszyny Turinga , które mogą rozwiązać problemu stopu, tak że H ( i , j ) zawsze postojów z H j ( í ) jako wynik.$H$$H(i,j)$$H_j(i)$

Chcemy udowodnić, że dana , możemy zbudować maszynę L , który ma charakterystyczny powstrzymując funkcyjny D . Maszyna L jest prawie identyczna z H , więc L ( i ) naśladuje H ( i , i ) , z tym wyjątkiem, że gdy H ( i , i ) kończy się z wartością 1 , L ( i ) przechodzi w nieskończoną pętlę i nie kończy się.$H$$L$$D$$L$$H$$L(i)$$H(i,i)$$H(i,i)$$1$$L(i)$

Jest całkiem jasne, że możemy zbudować taką maszynę jeśli istnieje H. Dlatego ta maszyna powinna być w naszym początkowym wyliczeniu wszystkich maszyn (które, jak wiemy, są możliwe). Ale nie może tak być, ponieważ jego zachowanie zatrzymania D nie odpowiada żadnej z wymienionych maszyn. Maszyna L nie może istnieć, co oznacza, że H nie może istnieć.$L$$H$$D$$L$$H$

_{Celowo naśladowałem pierwszy dowód i wdałem się w drobne szczegóły}

Mam wrażenie, że kroki następują naturalnie w ten sposób, szczególnie gdy ktoś uważa dowód Cantora za dość intuicyjny.

Najpierw wymienia się konstrukty sporne. Następnie bierze się i modyfikuje przekątną jako wygodny sposób na dotknięcie ich wszystkich, aby uzyskać nieuwzględnione zachowanie, a następnie uzyskać sprzeczność, pokazując obiekt, którego zachowanie nie zostało uwzględnione ... jeśli pewna hipoteza miałaby być prawdziwa: istnienie wyliczenie dla Cantora i istnienie obliczalnej wyroczni zatrzymującej dla Turinga.

Uwaga: Aby zdefiniować funkcję , możemy zastąpić odwróconą przekątną dowolną inną charakterystyczną funkcją zatrzymania, inną niż wszystkie wymienione w T , która jest obliczalna (od tych wymienionych na przykład w T ), pod warunkiem, że dostępna jest wyrocznia zatrzymująca . Wtedy maszyna L musiałaby być odpowiednio skonstruowana, aby mieć D jako charakterystyczną funkcję zatrzymania, a L ( i ) korzystałby z maszyny H , ale nie naśladowałby tak bezpośrednio H ( i , i ) . Wybór przekątnej znacznie ułatwia.$D$$T$$T$$L$$D$$L(i)$$H$$H(i,i)$

Porównanie z dowodem „innym”

Zdefiniowana tutaj funkcja jest najwyraźniej analogiem funkcji D w dowodzie opisanym w pytaniu.$L$$D$

Budujemy go tylko w taki sposób, że ma charakterystyczną funkcję zatrzymania, która nie odpowiada żadnej maszynie Turinga, i uzyskujemy z tego bezpośrednią sprzeczność. Daje nam to swobodę nieużywania przekątnej (za ile jest ona warta).

Idea „zwykłego” dowodu wydaje się próbować zabić to, co uważam za martwą rybę. Mówi: załóżmy, że jest jedną z wymienionych maszyn (tj. Wszystkie z nich). Następnie musi ona indeksem j L w tej liczby: L = M J L . Zatem jeśli L ( j L ) zatrzyma się, mamy T [ j L , j L ] = H ( j L , j L ) = 1 , więc L ( j L$L$$j_L$$L=M_{j_L}$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=1$$L(j_L)$zapętli się według konstrukcji. I odwrotnie, jeśli czy nie, a następnie zatrzymania T [ j L , J l ] = H ( j L , J l ) = 0 tak, że L ( j L ) zatrzyma się konstrukcyjnie. Mamy zatem sprzeczność. Ale sprzeczność wynika ze sposobu, w jaki skonstruowano charakterystyczną funkcję zatrzymującą L , i wydaje się o wiele prostsze powiedzieć, że $L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=0$$L(j_L)$$L$$L$ nie może być maszyną Turinga, ponieważ jest skonstruowana tak, aby miała charakterystyczną funkcję zatrzymywania, która nie jest funkcją maszyny Turinga.

Z drugiej strony ten zwykły dowód byłby o wiele bardziej bolesny, gdybyśmy nie wybrali przekątnej, podczas gdy bezpośrednie podejście zastosowane powyżej nie ma z tym problemu. Czy to może być przydatne, nie wiem.

Jest też dowód na to, że używa innego paradoksu, paradoksu Berry'ego, który słyszałem od Ran Raz.

$B(n)$$n$$S(n)$$n$$B(n)$$S(n)$

Rozważ następujący program:

1. $n$

2. $L$

3. $L$

Jest to program do obliczania . Jak duży jest ten program? Kodowanie n wymaga znaków O ( log n ) , a reszta programu nie zależy od $B(n)$$n$$O(\log n)$$n$$O(\log n)$$C\log n$$N$$C\log N \leq N$$N$$B(N)$$B(N)$

Ten sam pomysł można wykorzystać do udowodnienia twierdzeń o niekompletności Gödela, jak pokazali Kritchman i Raz .

W grę wchodzi bardziej ogólna idea zwana „twierdzeniem o rekurencji”, która może być bardziej intuicyjna: maszyny Turinga mogą korzystać z własnego opisu (a zatem same się uruchamiać). Dokładniej, istnieje twierdzenie:

Dla każdej maszyny Turinga Tistnieje maszyna Turinga, Rktóra oblicza R(x) = T(R;x).

Gdybyśmy mieli maszynę Turinga, która mogłaby rozwiązać problem zatrzymania, to korzystając z pomysłu opisanego powyżej, moglibyśmy z łatwością skonstruować wiele „kłamliwych” maszyn Turinga: np. W notacji podobnej do pytona,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

Bardziej skomplikowany argument polega na próbie zrobienia tego bezpośrednio, bez odwoływania się do twierdzenia o rekurencji. Oznacza to, że powtarza przepis na konstruowanie funkcji „autoreferencyjnych”. np. biorąc pod uwagę maszynę Turinga T, oto jeden taki przepis na zbudowanie Rsatysfakcjonującego

R(x) = T(R; x)

Najpierw zdefiniuj

S(M; x) = T(M(M; -); x)

przy M(M; -)czym tak naprawdę mam na myśli to, że obliczamy (używając opisu M) i podłączamy opis maszyny Turinga, który na wejściu yocenia M(M; y).

Teraz obserwujemy, że jeśli podłączymy się Sdo siebie

S(S; x) = T(S(S; -); x)

otrzymujemy kopię, której chcemy. Więc jeśli ustawimy

R = S(S; -)

Następnie mamy

R(x) = T(R; x)

zgodnie z życzeniem.

dowód Turinga jest dość podobny do dowodu Kantorów, że liczebność reali („niepoliczalna”) jest większa niż liczebność racjonalności („policzalna”), ponieważ nie można ich umieścić w korespondencji 1-1, ale nie jest to odnotowane / podkreślone w bardzo wiele referencji (czy ktoś je zna?). (iirc) CS profesor kiedyś pokazał to lata temu w klasie (nie jestem pewny, skąd go wziął). w dowodzie Kantorów można sobie wyobrazić siatkę o wymiarze poziomym n- ^tej cyfry liczby, a wymiarze pionowym n- ^tej liczby zbioru.

Konstrukcja odporna na zatrzymanie Turinga jest dość podobna, z tym wyjątkiem, że zamiast tego zawartość tabeli to Halt / Nonhalt dla 1/0, a oś pozioma jest n- ^tym wejściem, a oś pionowa jest n- ^tym programem komputerowym. innymi słowy, kombinacja programów komputerowych i danych wejściowych jest policzalna, ale nieskończona tabela / tablica jest niepoliczalna w oparciu o uniwersalną konstrukcję symulatora maszyny, która może „przerzucić” zatrzymanie do przypadkowego zatrzymania, zakładając, że istnieje wykrywacz zatrzymania (stąd reductio ad absurdam ) .

niektóre dowody na to, że Turing miał na myśli konstrukcję Kantorów częściowo, to, że jego ten sam artykuł z dowodem zatrzymania mówi o liczbach obliczalnych jako (wzdłuż linii) liczb rzeczywistych z cyframi obliczalnymi.

W tym miejscu warto zwrócić uwagę na dzieło Emila Posta, któremu (słusznie) przypisuje się, że jest współodkrywcą podstawowych wyników obliczeń, choć niestety opublikowano go zbyt późno, aby uznać go za współodkrywcę rozwiązania Entscheidungsproblem . Z pewnością brał udział w opracowaniu tak zwanej tezy Kościoła-Turinga .

Post był motywowany względami bardzo filozoficznymi, a mianowicie teoretycznymi ograniczeniami ludzkiej zdolności do obliczania, a nawet uzyskiwania precyzyjnych odpowiedzi w spójny sposób sposób. Opracował system, zwany teraz post kanonicznymi systemami , których szczegóły są nieistotne, które, jak twierdził, mogłyby zostać wykorzystane do rozwiązania każdego problemu, który można rozwiązać w sposób tak manipulacyjny przy pomocy symboli . Co ciekawe, wyraźnie stwierdził, że stany mentalne są częścią „pamięci”, więc jest prawdopodobne, że przynajmniej uważał swój model obliczeniowy za model ludzkiej myśli w całości.

Entscheidungsproblem rozważa możliwość zastosowania takiego środka obliczeniowego, aby powiedzieć, określić twierdzenie dowolnej twierdzenia wyrażanego w systemie Principia Mathematica . Ale PM był systemem wyraźnie zaprojektowanym tak, aby był w stanie reprezentować całe rozumowanie matematyczne, a co za tym idzie (przynajmniej w czasie, gdy logika była jeszcze w modzie) całe ludzkie rozumowanie!

Nie jest zatem zaskakujące, aby zwrócić uwagę takiego systemu na same systemy post kanoniczne, podobnie jak ludzki umysł, poprzez dzieła Frege'a, Russela i logików z przełomu wieków, zwrócił uwagę na wydział rozumowania samego ludzkiego umysłu.

W tym momencie jasne jest, że odniesienie do siebie lub zdolność systemów do opisywania siebie były dość naturalnym tematem na początku lat 30. XX wieku. W rzeczywistości David Hilbert miał nadzieję na „bootstrap” rozumowania matematycznego, przedstawiając formalny opis całej ludzkiej matematyki, który następnie mógłby zostać matematycznie udowodniony jako spójny!

Po uzyskaniu kroku użycia formalnego systemu do uzasadnienia samego siebie jest to przeskok i odejście od typowych paradoksów autoreferencyjnych (które mają dość starą historię ).

Ponieważ zakłada się, że wszystkie stwierdzenia w Principia są „prawdziwe” w pewnym sensie metafizycznym, a Principia może wyrazić

program pzwraca wynik truena wejściun

jeśli istnieje program, który decyduje o wszystkich twierdzeniach w tym systemie, bardzo łatwo jest bezpośrednio wyrazić paradoks kłamcy:

ten program zawsze kłamie.

można wyrazić przez

Program pzawsze zwraca przeciwieństwo tego, co według zasad matematyki ppowróci.

Trudność polega na budowaniu programu p. Ale w tym momencie bardziej naturalne jest rozważenie bardziej ogólnego zdania

Program pzawsze zwraca przeciwieństwo tego, co powie szef PM q.

dla niektórych arbitralnych q. Ale łatwo jest zbudować p(q)na dowolny q! Wystarczy obliczyć, co PM przewiduje, że wyświetli, i odwrócić odpowiedź. Nie możemy zastąpić qprzez pw tym momencie chociaż, ponieważ ptrwa qna wejściu, a qnie (to nie bierze wejście). Zmieńmy zdanie, aby p pobierało dane wejściowe:

Program pzwraca przeciwieństwo tego, co mówi PM q(r)wróci.

Arg! Ale teraz pwymaga 2 danych wejściowych: qi r, chociaż qtylko 1. Ale poczekaj: i tak chcemy pw obu miejscach, więc rnie jest to nowa informacja, ale tylko ta sama część danych, mianowicie q! To jest krytyczna obserwacja.

W końcu rozumiemy

Program pzwraca przeciwieństwo tego, co mówi PM q(q)wróci.

Zapomnijmy o tym głupim biznesie „PM mówi”, a my rozumiemy

Program p(q)zwraca przeciwieństwo tego, co q(q)powróci.

Jest to legalny program, pod warunkiem, że mamy program, który zawsze mówi nam, co q(q)zwraca . Ale teraz, że mamy naszego programu p(q), możemy zastąpić qprzez pi dostać paradoks naszego kłamcy.