Czy możliwa jest meta-nierozstrzygalność?

9

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.

Trylks
źródło
Rozważmy stwierdzenie „monadyczna (drugiego rzędu) teoria wszystkich rzędów liniowych jest obliczalna”. Istnieją powody, by sądzić (ale nie jestem pewien, czy udowodniono niezależność), że to stwierdzenie jest niezależne (tzn. Nierozstrzygalne) w ZFC. Więcej szczegółowych informacji na temat przyczyn można znaleźć w books.google.es/books?id=y3YpdW-sbFsC&pg=PA397
boumol
1
Kiedy mówisz „rozstrzygalność jest nierozstrzygalna”, jakie są dane wejściowe?
Mahdi Cheraghchi
2
Mógł być również zainteresowany en.wikipedia.org/wiki/Turing_degree, ale nie jest jasne, w jaki sposób pytanie jest zadawane. :)
Daniel Apon
1
@ Boumol Shelah („Monadyczna teoria porządku”, Ann. Math. 102 (3), 1975) udowodnił (zakładając CH), że „monadyczna teoria porządku jest nierozstrzygalna” (Twierdzenie 7 (B), s. 409).
Yuval Filmus
1
L={halting problemif the continuum hypothesis holdsotherwise
sdcvvc

Odpowiedzi:

8

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 Tjest 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 przezT(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ł true jeśli ta klasa jest rozstrzygalna i false Inaczej.

Teraz weź dowolną maszynę Turinga T. Budujemy następującą klasę problemówT 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 false, ponieważ zbiór wskaźników zatrzymujących maszyny Turinga nie jest zbiorem rozstrzygalnym (rekurencyjnym).

Gdyby Twięc nie zatrzymuje sięTnie wylicza żadnych liczb, co sprawia, że ​​jest to dokładnie klasa problemów bez żadnych indeksów! W związku z tymM(T) odpowiedzi true, ponieważ ta klasa jest rozstrzygalna (przez maszynę, która zawsze odrzuca).

W związku z tym, M(T) zwroty true iff T nie zatrzymuje się i falseInaczej. Tak więc istnienieM pozwala nam rozwiązać problem zatrzymania dowolnej maszyny T, co jest sprzecznością.

cody
źródło
Cześć Cody! Mam nadzieję, że masz się dobrze. Będziesz tego lata w Pittsburghu?
Michael Wehar
Hej! Nie jestem pewny. Wyślij mi e-mail!
cody
1

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.

Michael Wehar
źródło