Czy możliwa jest meta-nierozstrzygalność?

Istnieją problemy, które można rozstrzygnąć, niektóre są nierozstrzygalne, istnieje możliwość rozstrzygnięcia itp.

W tym przypadku zastanawiam się, czy problem może być nierozstrzygalny. Oznacza to (przynajmniej w mojej głowie), że nie możemy stwierdzić, czy jest to rozstrzygalne, czy nie.

Być może wiadomo, że rozstrzygalność jest nierozstrzygalna (wszystko jest meta-nierozstrzygalne) i nie istnieje żaden algorytm, który mógłby udowodnić rozstrzygalność dla czegokolwiek, więc rozstrzygalność należy udowodnić ręcznie dla każdego przypadku z osobna.

Może moje pytanie nie ma sensu. Może zakładam, że jesteśmy maszynami węglowymi z bardzo złożonymi algorytmami i dlatego pytanie ma sens tylko w mojej głowie.

Daj mi znać, jeśli pytanie wymaga dalszego wyjaśnienia. W tej chwili mogę tego potrzebować.

Dziękuję Ci.

Oto krótki szkic pokazujący, że nie ma maszyny Turinga, która decydowałaby o rozstrzygnięciu dowolnej klasy problemów.

Powinienem wyjaśnić, co rozumiem przez klasę problemów: klasę problemów $T$jest maszyną Turinga, która wylicza elementy (powiedzmy liczby naturalne) zestawu rekurencyjnie wyliczalnego jeden po drugim, tak że każdy element zestawu jest ostatecznie drukowany. Problem intuicyjnie uchwycony przez$T(n)$ is: ”to liczba $n$ w tym zestawie? ”. To wychwytuje typowe problemy w dziedzinie obliczalności, takie jak„ czy i jest indeksem maszyny Turinga, która zatrzymuje się przy pustym wejściu? ”.

Załóżmy, że była maszyna $M$ który jako dane wejściowe przedstawia klasę problemów $T$ odpowiedział $\mathit{true}$ jeśli ta klasa jest rozstrzygalna i $\mathit{false}$ Inaczej.

Teraz weź dowolną maszynę Turinga $T$. Budujemy następującą klasę problemów$T'$ W następujący sposób:

1. Symulować $T$.
2. Gdyby $T$ zatrzymuje się, wyliczyć wskaźniki maszyn Turinga, które zatrzymują się przy pustych danych wejściowych.

Teraz jest jasne, że jeśli $T$ więc zatrzymuje się $M(T')$ zwroty $\mathit{false}$, ponieważ zbiór wskaźników zatrzymujących maszyny Turinga nie jest zbiorem rozstrzygalnym (rekurencyjnym).

Gdyby $T$więc nie zatrzymuje się$T'$nie wylicza żadnych liczb, co sprawia, że ​​jest to dokładnie klasa problemów bez żadnych indeksów! W związku z tym$M(T')$ odpowiedzi $\mathit{true}$, ponieważ ta klasa jest rozstrzygalna (przez maszynę, która zawsze odrzuca).

W związku z tym, $M(T')$ zwroty $\mathit{true}$ iff $T$ nie zatrzymuje się i $\mathit{false}$Inaczej. Tak więc istnienie$M$ pozwala nam rozwiązać problem zatrzymania dowolnej maszyny $T$, co jest sprzecznością.

Bardzo fajny pomysł!

Pomysł: Możemy wykorzystać aksjomat zrozumienia w teorii zbiorów ZF do zdefiniowania języka zależnego od niezależnego stwierdzenia.

Krok 1: Weź swoje ulubione stwierdzenie, które jest niezależne od ZF, takie jak AC - aksjomat wyboru.

Krok 2: Zdefiniuj język L = {x w {0,1} | x = 0, jeśli AC, i x = 1, jeśli NIE AC}. Zauważ, że L to {0} lub {1}. Teraz L jest rozstrzygalne, ale nie jesteśmy w stanie zapewnić z pewnością programu, który decyduje o L. Możemy dostarczyć program, który decyduje o {0} lub możemy zapewnić program, który decyduje o {1}, ale nie wiemy z całą pewnością który decyduje L.

Krok 3: Użyj tego pomysłu, aby zdefiniować język, który będzie rozstrzygalny, jeśli AC, i nierozstrzygalny, jeśli NIE AC. Niech H będzie zbiorem zatrzymującym, który jest nierozstrzygalny. Zdefiniuj L = {x | x jest łańcuchem, jeśli AC, a x jest w H, jeśli NIE AC}. Jeśli AC, to L = zbiór wszystkich łańcuchów, a L jest rozstrzygalne. Jeśli NIE, to L = H i L są nierozstrzygalne. To, czy L jest rozstrzygalne, jest niezależne od ZF.