Czy istnieje jakikolwiek konkretny związek między twierdzeniem o niekompletności Gödla, problemem zatrzymania a uniwersalnymi maszynami Turinga?

Zawsze myślałem niejasno, że odpowiedź na powyższe pytanie była twierdząca w następujący sposób. Twierdzenie Gödela o niekompletności i nierozstrzygalność problemu zatrzymania są zarówno negatywnymi wynikami rozstrzygalności, jak i ustalonymi na podstawie przekątnych argumentów (w latach 30. XX wieku), więc muszą być jakoś dwoma sposobami spojrzenia na te same sprawy. Pomyślałem, że Turing zastosował uniwersalną maszynę Turinga, aby pokazać, że problem zatrzymania jest nierozwiązywalny. (Zobacz także to pytanie matematyczne .).

Ale teraz, gdy (prowadząc kurs z zakresu obliczeń) przyjrzę się bliżej tym zagadnieniom, jestem raczej zdumiony tym, co znajduję. Chciałbym więc pomóc w uporządkowaniu moich myśli. Zdaję sobie sprawę, że z jednej strony przekątny argument Gödela jest bardzo subtelny: potrzeba dużo pracy, aby skonstruować zdanie arytmetyczne, które można interpretować jako mówienie o jego pochodnej. Z drugiej strony znaleziony tutaj dowód nierozstrzygalności problemu zatrzymania jest niezwykle prosty i nawet nie wspomina wprost o maszynach Turinga, nie mówiąc już o istnieniu uniwersalnych maszyn Turinga.

Praktyczne pytanie o uniwersalne maszyny Turinga brzmi, czy ważne jest, aby alfabet uniwersalnej maszyny Turinga był taki sam jak alfabet maszyn Turinga, które symuluje. Pomyślałem, że byłoby to konieczne, aby wymyślić właściwy przekątny argument (automatyczna symulacja maszyny), ale nie zwróciłem uwagi na to pytanie w oszałamiającym zbiorze opisów uniwersalnych maszyn, które znalazłem w sieci. Jeśli nie problem zatrzymania, czy uniwersalne maszyny Turinga są przydatne w jakimkolwiek przekątnym sporze?

Wreszcie jestem zaskoczony tą dalszą sekcjątego samego artykułu WP, który mówi, że słabsza forma niekompletności Gödela wynika z problemu zatrzymania: „pełna, konsekwentna i solidna aksjatyzacja wszystkich stwierdzeń o liczbach naturalnych jest nieosiągalna„ tam, gdzie „dźwięk” ma być osłabieniem. Wiem, że teoria jest spójna, jeśli nie można wyprowadzić sprzeczności, a pełna teoria liczb naturalnych wydaje się oznaczać, że można w niej wyprowadzić wszystkie prawdziwe twierdzenia o liczbach naturalnych; Wiem, że Gödel twierdzi, że taka teoria nie istnieje, ale nie rozumiem, w jaki sposób taka hipotetyczna bestia mogłaby nie być zdrowa, tzn. Również wyprowadzać twierdzenia, które są fałszywe dla liczb naturalnych: negacja takiego stwierdzenia byłaby prawdziwa , a zatem przez kompletność również pochodną, ​​co byłoby sprzeczne z konsekwencją.

Byłbym wdzięczny za wyjaśnienie jednej z tych kwestii.

Polecam sprawdzić post na blogu Scotta Aaronsona na dowodzie twierdzenia o niekompletności za pośrednictwem maszyn Turinga i twierdzenia Rossera. Jego dowód twierdzenia o niekompletności jest niezwykle prosty i łatwy do naśladowania.

Odpowiedź Neela Krishnaswamiego na problem Haltinga, niepoliczalne zbiory: wspólny dowód matematyczny? na CSTheory wskazuje na odnośniki łączące powyższe wyniki w ramach teorii kategorii.

(To ma być komentarz do odpowiedzi Suresha, ale po prostu jest za długi, żeby się tam zmieścić. Z góry przepraszam, że tak naprawdę nie odpowiada na pytanie Marca.)

Znajduję odpowiedź Neela Problem zatrzymania, niepoliczalne zbiory: wspólny dowód matematyczny? na blogu CSTheory i Andreja Bauera niezadowalające z dwóch powodów.

$\mathbb{N}$$\mathbb{N}$$\mathcal{P}(\mathbb{N})$$\mathbb{N}$$\mathcal{P}(\mathbb{N})$

Po drugie, powyższy dowód jest niezadowalający, ponieważ chcemy również „zobaczyć” przykład rozsądnego nierozstrzygalnego języka. Powyższy dowód może być postrzegany jako liczący się argument, a zatem nie do końca „konstruktywny” w tym sensie. Turing odkrył problem zatrzymania jako taki przykład.

$\mbox{DTIME}(f(n)^3)$$\mbox{DTIME}(f(n/2))$

$K$$¬KK$

„Jeśli nie problem zatrzymania, czy uniwersalne maszyny Turinga są przydatne w jakimkolwiek przekątnym sporze?”

Twierdzenie Rice'a jest zasadniczo uogólnieniem diagonalizacji względem maszyn Turinga. Pokazuje, że nie ma absolutnie żadnej właściwości na temat maszyn Turinga, którą można zdecydować dla wszystkich maszyn Turinga za pomocą jednego algorytmu, chyba że ta właściwość obowiązuje dla wszystkich maszyn Turinga lub żadnych maszyn Turinga. Należy zwrócić uwagę na fakt, że właściwość przechowująca dla wszystkich maszyn Turinga lub brak maszyn Turinga zapobiega temu, że obiekt diagonalizacji jest maszyną Turinga, dlatego też nie może być na liście, aby zaprzeczyć decyzji o nieruchomości. Rzeczywiście to jest jedynarzeczy, które zapobiegają pojawieniu się obiektu diagonalizacji na liście i są sprzeczne z decyzją dotyczącą właściwości, którą są wszystkie właściwości maszyn Turinga, są nierozstrzygalne. Ten wzorzec obiektu diagonalizacji, który musi być członkiem listy rzeczy, o których próbujesz podjąć decyzję, a jednocześnie ją negować, jest krytyczną abstrakcją, którą przechwytuje twierdzenie Lawvere'a (wymienione w linku w odpowiedzi Suresha) w celu pełnego uogólnienia pojęcia diagonalizacji. Teraz, ponieważ wiemy z doświadczenia, że ​​prawie każda diagonalizacja wydaje się mieć wspólną właściwość doprowadzenia do jakiegoś niezwykle ważnego wyniku w logice matematycznej, co czyni twierdzenie Lawvere'a dość interesującym narzędziem.