Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?

30

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 MH 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 )MxDMMH(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 DDMD

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.D(M)MM;Mre

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

użytkownik118967
źródło
3
Rozważ możliwość, że jakikolwiek dowód na istnienie niepoliczalnych zbiorów będzie musiał być nieco sprzeczny z intuicją, nawet jeśli przyzwyczaimy się do tego, że są poprawne . Zastanów się również, czy to pytanie (jeśli zostało poprawnie sformułowane ) należy do strony math.stackexchange.com .
André Souza Lemos
4
Cantor znalazł argument diagonalizacji, a teraz nie możemy się go oduczyć: Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können .
Hendrik,
1
Po dalszych przemyśleniach muszę zapytać, dlaczego według ciebie jest to tak różne od paradoksu Russella. Paradoks Russella wygląda nawet tak samo, jeśli użyjemy notacji celu oznaczenia X S (tj. Pomyślimy, że zbiory są funkcjami, których wartości to lub ). Następnie paradoks Russella polega na zdefiniowaniu , a następnie rozważeniu . S(X)XStruefalseD(M) = not M(M)D(D)
1
Diagonalizacja jest standardową techniką . Pewnie był czas, kiedy nie było to znane, ale od dawna jest to standard, więc twój argument jest po prostu wynikiem twojej ignorancji (nie chcę być niegrzeczny, to fakt: nie wiedziałeś wszystkie inne dowody, które wykorzystują taką technikę i stąd dziwne są za pierwszym razem, gdy ją zobaczysz. Gdy zobaczysz ją 50 razy, prawdopodobnie będziesz w stanie zrozumieć, jak można ją zastosować w nowej sytuacji).
Bakuriu
1
Może przeczytałbyś moją wymianę komentarzy z Lukiem Mathiesonem (po jego odpowiedzi). Jego odpowiedź wyjaśnia historycznie, dlaczego Turing zastosował samozapylenie (jedna z rzeczy, o którą pytasz w swoim pytaniu). Wygląda na to, że matematycy postrzegali wówczas te problemy. Moja własna odpowiedź próbuje dać bardzo prosty dowód, który go nie używa (lub przynajmniej pokazuje, że nie jest to konieczne), o co jeszcze prosisz, zupełnie inaczej. Być może mógłbym uczynić to jeszcze prostszym niż w mojej odpowiedzi. Dlaczego nauczyciele nadal używają dowodu Turinga jest kwestią socjologiczną i pedagogiczną (?!). cc @HendrikJan
babou

Odpowiedzi:

18

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)MM;MD

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! ”MHDMMD

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

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

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 .DD(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 tegoDD(M)M(D)M(M)DMHDMH zamiast D niepotrzebnie komplikuje dowód i czyni go mniej intuicyjnym.DD

Ilmari Karonen
źródło
1
Wow, naprawdę zadrżałeś na moje pytanie! To jest dokładnie to rodzaj opowieści szukałem! Wciąż czytam wszystko, ale wygląda na to, że to byłaby zaakceptowana odpowiedź. Dzięki!
user118967
18

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, „

Luke Mathieson
źródło
2
Tak, wydaje się, że celem Turinga było odtworzenie okrągłości (z której pochodzi diagonalizacja) za pomocą maszyn, w celu wprowadzenia jakiegoś abstrakcyjnego pojęcia czasu , z którym można mówić o skończoności w nowy sposób.
André Souza Lemos
Może możesz mnie oświecić, ponieważ nie znam niektórych z tych dowodów. Rozumiem, że te dowody można zestawić za pomocą samodzielnych odniesień. Mogę nawet uwierzyć (choć może to wymagać dowodu), że zawsze istnieje pewne odniesienie do siebie, niezależnie od tego, jaką strukturę zbudowano w tym celu. Ale nie widzę potrzeby jawnego wykorzystywania go do przeprowadzenia dowodu jego zawarcia. W ten sposób możesz sformułować argument Cantora, ale nie musisz. I nie rozumiem, dlaczego musisz to robić dla problemu zatrzymania. Mogłem przegapić krok, ale który?
babou
Aby wyjaśnić moją poprzednią uwagę, pierwotne pytanie brzmi : „ Czy jest bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania ... ”. Pomijam koniec, ponieważ uważam, że OP narzeka głównie na brak intuicji. Uważam, że rzeczywiście istnieje bardziej intuicyjny dowód, nie wykorzystujący samodzielnego odniesienia. Może ci się wydawać, że użycie tego dowodu jest pedagogicznie nierozsądne (niezwiązane z twórczością Russella i Gödla), ale jeśli odpowie na zadane pytanie, jaki jest sens jego odrzucenia. Wydaje się, że raczej zaprzeczasz pytaniu niż odpowiadasz na nie.
babou
@babou Myślę, że problem polega na tym, że odpowiadamy na różne pytania. Myślę, że OP nie było dobrze sformułowane w tym względzie. Powtarzającym się pytaniem w treści OP wydaje mi się, że „jak ktoś kiedykolwiek pomyślał o argumentie diagonalizacji, aby udowodnić ...” (sparafrazowane oczywiście) i że „konstrukcje wydają się być wyciągnięte z magicznego kapelusza” .
Luke Mathieson
@babou, również, aby trochę rozwinąć, z odpowiednią klawiaturą, nie sądzę, że w ten czy inny sposób jest koniecznie przydatny pedagogicznie (zależałoby to w dużej mierze od kontekstu). W rzeczywistości, w przypadku większości współczesnych kursów CS, prawdopodobnie lepiej jest to zrobić bez argumentu diagonalizacji, większość studentów CS po prostu nie jest już wystarczająco matematycznie skłonna do poznania tła, które ułatwiłoby zrozumienie, ale zdecydowanie odpowiedziałem na pytanie, które zakończyło oryginalny tekst: ...
Luke Mathieson
9

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

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

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

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

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)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 .SjCj(i)1iSj0

Może to być postrzegane jako tabela , tak że T [ i , j ] = C j ( i )TT[i,j]=Cj(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.DD(i)=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 .DN

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.MjHj(i)1Mji0

Można to postrzegać jako tabelę , taką że T [ i , j ] = H j ( i )TT[i,j]=Hj(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.DD(i)=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 .THj

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.HH(i,j)Hj(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ę.HLDLHL(i)H(i,i)H(i,i)1L(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ć.LHDLH

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.DTTLDL(i)HH(i,i)

Porównanie z dowodem „innym”

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

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 )LjLL.=M.jotL.L.(jotL.)T.[jotL.,jotL.]=H.(jotL.,jotL.)=1L.(jotL.)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 LL.(jotL.)T.[jotL.,jotL.]=H.(jotL.,jotL.)=0L.(jotL.)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.

Babou
źródło
To miłe, dziękuję! Wygląda na to, że w jakiś sposób udało ci się ominąć samonakładające się konstrukcje, które uważałem za kłopotliwe. Teraz zastanawiam się, dlaczego ludzie uznali je za niezbędne.
user118967
@ user118967 Próbowałem podkreślić, że użycie przekątnej nie jest tak naprawdę ważne. Wszystko, czego chcesz, to zdefiniowanie charakterystycznej funkcji zatrzymania, która różni się od wszystkich wymienionych w tabeli i którą można obliczyć z tych wymienionych, pod warunkiem, że mamy wyrocznię zatrzymania. Istnieje nieskończenie wiele takich charakterystycznych funkcji zatrzymania. Teraz nie wydaje się to tak widoczne w zwykłym dowodzie i może się zdarzyć, że niektóre konstrukcje tego dowodu wydają się arbitralne tylko dlatego, że są, jak wybranie przekątnej w dowodzie powyżej. To jest tylko proste, nie konieczne.
babou
@ user118967 Dodałem i wprowadzenie podsumowujące analizę różnych dowodów. Uzupełnia porównanie między próbami (z samodzielnym zastosowaniem i bez), które podano na końcu. Nie wiem, czy zlikwidowałem diagonalizację, o co prosiłem :) (myślę, że byłoby to niesprawiedliwe), ale sugeruję, jak pozbyć się oczywistej przekątnej. Dowód nie wykorzystuje samozastosowania, co wydaje się niepotrzebne, ale zręcznie wyglądające, sztuczka ukrywa coś, co może wydawać się ważniejszą kwestią, zachowanie zatrzymania.
babou
@ user118967 Aby odpowiedzieć na twój pierwszy komentarz i po przeczytaniu najbardziej uprzywilejowanej odpowiedzi, wydaje się, że główną motywacją jest związek z twórczością Russella i Gödela. Teraz nie mam pojęcia, czy jest to naprawdę niezbędne do tego celu, a wariant konstrukcji samozastosujących się może z pewnością być badany w tym celu, ale nie widzę sensu narzucania go wszystkim. Co więcej, bardziej bezpośredni dowód wydaje się bardziej intuicyjny i daje narzędzie do dalszej analizy wersji samozastosującej się. Dlaczego więc?
babou
Tak, zgadzam się z tobą w tej sprawie.
user118967
8

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

b(n)nS.(n)nb(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 nb(n)nO(logn)nO(logn)dolognN.dologN.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 .

Yuval Filmus
źródło
Być może jest to w cytowanym przeze mnie artykule lub w klasycznej monografii Złożoność Kolmogorowa autorstwa Li i Vitányi.
Yuval Filmus
Nawiasem mówiąc, czy uważasz, że ta metoda zapewnia atak na problem NP vs CoNP?
Mohammad Al-Turkistany
Nie. Takie problemy są obecnie poza nami.
Yuval Filmus
n
nnn
6

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.


źródło
Pierwszy akapit nie pasuje do cytowanego przez ciebie twierdzenia, które znam pod nazwą twierdzenia smn.
Raphael
@Raphael: W moim podręczniku nazywa się to twierdzeniem o rekurencji. :( Moja krótka próba w Google nie znalazła żadnych alternatywnych nazw.
Bez obaw; może rozumiem cię źle lub istnieją różne nazwy dla tej samej rzeczy. To powiedziawszy, twoje zdanie „Maszyny Turinga mogą używać własnego opisu” nie jest poparte cytowanym przez ciebie twierdzeniem. Właściwie myślę, że to jest złe: jeśli funkcja obliczana przez TM zależy od jej indeksu, jak wyglądałyby wszystkie nieskończenie wiele TM obliczających tę samą funkcję?
Raphael
T.liarTruenot liar()False
T.RR(x)=T.(R;x)T.RR(x)=T.(R;x)
5

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.

vzn
źródło
addendum, istnieje rzeczywiście bardzo „intuicyjny” sposób patrzenia na nierozstrzygalność, ale wymaga dużo większej matematyki do zrozumienia (tj. intuicja neofity znacznie różni się od intuicji eksperta). matematycy zastanawiają się nad problemem zatrzymania i dowodzą identycznymi dowodami za pomocą twierdzenia Lawvere'a o punkcie stałym, ale jest to zaawansowany fakt, który nie jest zbyt dostępny dla studentów „jeszcze”. widzisz problem zatrzymania, niepoliczalne zestawy, powszechny problem matematyczny? Informatyka teoretyczna i powiązany link do
referencji
3

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.

cody
źródło