Czy są jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samoreferencji lub diagonalizacji?

To pytanie jest z tym związane . Po wielu rozmowach po raz kolejny, w znacznie prostszej formie, wydawało się, że to zupełnie inne pytanie.

Klasyczny dowód nierozstrzygalności problemu zatrzymania zależy od wykazania sprzeczności przy próbie nałożenia na siebie hipotetycznego decydenta HALT. Myślę, że oznacza to po prostu niemożność posiadania decydenta HALT, który decyduje o tym, czy sam się zatrzyma, czy nie, ale nie podaje żadnych informacji poza tym o możliwości rozstrzygania jakichkolwiek innych przypadków.

Pytanie brzmi:

Czy istnieje dowód, że problem zatrzymania jest nierozstrzygalny, co nie zależy od wykazania, że ​​HALT nie może sam zdecydować, ani nie zależy od argumentu diagonalizacji?

Mała edycja: zobowiązuję się do pierwotnego sformułowania pytania, które wymaga dowodu, który w ogóle nie zależy od diagonalizacji (zamiast po prostu wymaganie, aby nie zależała od diagonalizacji zależnej od HALT).

Tak, istnieją takie dowody w teorii obliczalności (aka teoria rekurencji).

Możesz najpierw pokazać, że problem zatrzymania (zbiór ) może być użyty do obliczenia zbioru który jest 1-ogólny, co oznacza, że ​​w pewnym sensie każdy fakt o jest określony przez skończony przedrostek . Łatwo jest zatem udowodnić, że taki zestaw nie może być obliczalny (tj. Rozstrzygalny). G ⊆ N Σ 0 1 G G $0'$$G\subseteq\mathbb N$$\Sigma^0_1$$G$$G$$G$

Możemy zastąpić tutaj 1- generyczny 1-losowym, tj. Losowym Martin-Löf , dla tego samego efektu. Wykorzystuje to twierdzenie Jockusch-Soare Low Basis .

(Ostrzeżenie: można rozważyć tylko pokazanie, że oblicza Chaitina , która jest 1 losowa, ale tutaj musimy uważać, czy dowód, że jest 1 losowy, polega na nierozstrzygnięciu problemu zatrzymania! bezpieczniej jest po prostu użyć twierdzenia o niskiej podstawie).Ω$0'$$\Omega$$\Omega$

Przesłane z mojego komentarza na żądanie:

Zacznij od spostrzeżenia, że ​​istnieją nierozstrzygalne problemy (prosty argument liczności), a ponadto, że istnieje nierozstrzygalny problem P, który ma TM M, który rozpoznaje jego członków (ale może nie kończyć się na nie-członkach). Teraz rozwiązywanie HALT (M) daje ci decyzję o P. Najpierw sprawdzamy, czy M zatrzymuje się na x. Jeśli tak, uruchamiamy go i zwracamy to samo co M. W przeciwnym razie odrzucamy, ponieważ M zatrzymuje się na każdym elemencie P. To jest teraz sprzeczność, ponieważ zakładamy, że P jest nierozstrzygalny.

Uwaga: Wyjaśnił, że szuka argumentu, który unikałby diagonalizacji za pomocą HALT bezpośrednio, a nie argumentu, który unikałby całkowicie diagonalizacji.

EDYCJA: Ten argument utknął. Czy możesz bezpośrednio pokazać, że RE - REC nie jest pusty, oprócz pokazania, że ​​HALT tam jest?

Kolejny plakat nawiązywał do tego (odnosząc się do Chaitin), ale możesz użyć paradoksu Berry, aby udowodnić, że problem zatrzymania jest nierozstrzygalny. Oto krótki szkic dowodu:

Niech HALT będzie maszyną, która decyduje, czy jakakolwiek maszyna M zatrzyma się na wejściu I. Pokażemy, że sam HALT nie zatrzymuje się na określonym wejściu, co pokazuje, że nie jest w stanie zdecydować o języku.

Rozważ następującą funkcję f:

f (M, n) = a, gdzie a jest najmniejszą liczbą całkowitą dodatnią nieobliczalną przez maszynę M na żadnym wejściu I z | I | <n

Zakładając, że HALT jest funkcją obliczalną, f jest również funkcją obliczalną; po prostu symuluj HALT (M, I) dla każdej maszyny M i ciąg wejściowy I o długości I mniejszej niż n. Jeśli symulacja się zatrzyma, symuluj M (I) i zapisz, co to jest wyjście, i znajdź najmniejsze wyjście a, które nie jest wyprowadzane przez żadną z par M, n.

Teraz pokazujemy, że f nie jest obliczalny: rozważmy f (f, 10000000 * | f | +10000000). Cokolwiek wyprowadza, powinna być (dodatnią) liczbą całkowitą, która nie może być obliczona przez maszynę obliczającą f na wejściu I o długości mniejszej niż podana ... a jednak właśnie wyprowadziliśmy taką liczbę całkowitą zf i znacznie krótszym wkład.

Zatem f nie jest obliczalne, a zatem nasze założenie, że HALT był obliczalny, jest fałszywe. Nie wierzę, że ten dowód w jakikolwiek sposób korzysta z przekątnej.

Nie jestem pewien, czy to się liczy, ale możesz to udowodnić za pomocą twierdzenia o rekurencji. Twierdzenie o rekurencji mówi, że jeśli jest skutecznym listowaniem wszystkich maszyn Turinga, a jest funkcją rekurencyjną, to jest takie , że na wszystkich wejściach. Jeśli mógłbyś zdecydować, czy dana maszyna zatrzymuje się na powiedzmy wejściu możesz napisać rekurencyjną która na wejściu wypisuje indeks maszyny Turinga, która zatrzymuje się na iff nie zatrzymuje się na . Przez twierdzenia rekursji istnieje tak, że = f e W e = W f ( e ) 0 f e 0 W e 0 e W e ( 0 ) W f ( e ) ( 0 $\{W_e\}_{e=1}^{\infty}$$f$$e$$W_e = W_{f(e)}$$0$$f$$e$$0$$W_e$$0$$e$$W_e(0)$$W_{f(e)}(0)$ co jest sprzecznością.