Dowód nierozstrzygalności, a nie redukcja problemu zatrzymania

Zwykłym sposobem udowodnienia nierozstrzygalności jest redukcja problemu RE-zupełnego, takiego jak problem zatrzymania, trafność w logice pierwszego rzędu, spełnienie równań diofantycznych itp.

Wiadomo, że istnieją rekurencyjnie wyliczalne, ale nierozstrzygalne problemy, które nie są uzupełniane ponownie, ale są to sztuczne konstrukcje (to znaczy zestawy, które zostały zdefiniowane tylko w celu pokazania tego wyniku „gęstości”).

Jak poradzić sobie z udowodnieniem nierozstrzygalności bez ograniczenia problemu RE-zupełnego? Przekątna?

computability David Monniaux
źródło

Może właściwe pytanie brzmi: „jakie są różne bezpośrednie metody dowodzenia nierozstrzygalności”?

Suresh Venkat

twierdzenie o niekompletności Godela jest nieco postrzegane jako „inny sposób” ... inny dowód diagonalizacji opiera się na tym, że liczba programów / par wejściowych jest policzalna, ale języki są niepoliczalne, a zatem w ten sposób jest podobny do niewspółmierności reali z liczbami całkowitymi. zobacz także to pytanie

dniu

Możliwy duplikat: czy istnieją jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samodzielnego odniesienia lub diagonalizacji?

Kaveh

@vzn: Uważam niekompletność Godela za zasadniczo ten sam dowód ...

Joshua Grochow

Tylko z ciekawości, dla jakiego problemu lub języka próbujesz udowodnić nierozstrzygalność? Myślę, że istnieje wiele znanych nierozstrzygalnych problemów (patrz na przykład mała lista na Wikipedii), które można zmniejszyć, więc zastanawiam się, czy przynajmniej jeden z nich jest podobny do twojego, czy też jest to zupełnie nowy problem.

Marzio De Biasi

Odpowiedzi:

Można pokazać dość bezpośrednio, że złożoność Kołmogorowa nie jest obliczalna, patrz np. Sipser, wydanie trzecie, problem 6.23.

Bjørn Kjos-Hanssen
źródło

Powinno to również wynikać bezpośrednio z twierdzenia Chaitin o niekompletności , którego dowód jest dość podobny.

Yonatan N

Wydaje mi się, że z poprzednich problemów Sipser zamierza wykorzystać nierozstrzygalność problemu zatrzymania dla tego dowodu, więc może warto naszkicować bezpośredni dowód nieobliczalności w odpowiedzi.

usul

W rzeczywistości pomaga porównanie z ćwiczeniami 6.24 i 6.25.

Bjørn Kjos-Hanssen

Pomyślałem, że warto zwrócić uwagę - biorąc pod uwagę, że OQ zapytał konkretnie o diagonalizację - że dowodem, że K jest niepoliczalny, jest również zasadniczo diagonalizacja. (Rzeczywiście, jest to w zasadzie ta sama, zwykła waniliowa diagonalizacja, która służy do udowodnienia, że HALT jest nieobliczalny, co jest tym samym, co oryginalny dowód Cantora na temat liczności, który jest taki sam, jak dowody niekompletności Godela i Chaitina, które są tylko słusznym twierdzeniem- wersje paradoksu Russella ...

Joshua Grochow

Zastanów się, co lubię nazywać problemem ZGODNYM ODGADZANIEM.

Jako dane wejściowe podano opis maszyny Turinga : $M$

Jeśli akceptuje na czystej taśmie, musisz zaakceptować. $M$
Jeśli odrzuci na czystej taśmie, musisz odrzucić. $M$
Jeśli działa wiecznie na czystej taśmie, możesz zaakceptować lub odrzucić, ale w obu przypadkach musisz się zatrzymać. $M$

(Oczywiście nie jest to całkiem język, ale bardziej analogiczny do obliczenia analogicznego problemu.)

Teraz, poprzez modyfikację oryginalnego dowodu Turinga, dość łatwo jest wykazać, że ZGODNE Zgadywanie jest nierozstrzygalne (zostawię to jako ćwiczenie dla ciebie).

Z drugiej strony można również wykazać, że nie ma redukcji od problemu zatrzymania do ZGADNEGO Zgadywania --- tj. Że możliwe jest zbudowanie wyroczni która zwraca poprawną odpowiedź akceptacji / odrzucenia dla każdej zatrzymującej TM, ale której odpowiedzi dla non-wstrzymywania bazach zabić każdą możliwą redukcję z wstrzymaniem problemu do . Dlatego ZGODNE ZGADNIANIE powinno być naprawdę postrzegane jako trudność pośrednia między obliczalnością a problemem zatrzymania. $A$ $A$

Scott Aaronson
źródło

Dzięki, ale ... znowu dowód na przekątną. ;-) Moim problemem jest to, że mam coś, co moim zdaniem jest nierozstrzygalne (w zasadzie od ponad 35 lat ludzie zawsze szukali algorytmów heurystycznych lub algorytmów ważnych dla podklas, aby je rozwiązać), ale dla których wydaje się, że nie ma ani „oczywistych” redukcje z powodu ponownego lub jakiś miły argument przekątny ...

David Monniaux

Zauważ, że nie ma „naturalnych” problemów, o których wiadomo, że są nierozstrzygalne, ale nie mają (znanej) redukcji Turinga do problemu zatrzymania. W szczególności jedynym „zalecanym” podejściem do wykazania, że coś jest nierozstrzygalne, jest sprowadzenie go do innego nierozstrzygalnego problemu (np. Półjednoznaczności lub osiągalności macierzy )

cody

cody: Tak też myślałem. Ale jeśli chcesz wziąć pod uwagę bardziej ogólne zadania niż decydowanie o języku, to ZGODNE ODGRYWANIE to całkiem naturalny kontrprzykład! (Nawiasem mówiąc, zakładam, że miałeś na myśli, redukując znane nierozwiązywalne problemy do swojego problemu, a nie na odwrót.)

Scott Aaronson

Jeśli to, czego szukasz, to nie jest ani a) redukcja znanego pełnego problemu, ani b) prosta diagonalizacja (na co wskazują twoje różne komentarze), to o ile wiem, nie masz szczęścia. Wszystkie dowody, o których wiem, że nie są redukowane - w tym te w innych doskonałych odpowiedziach podanych tutaj przez Aaronsona i Kjosa-Hanssena - następują po prostej diagonalizacji.

Wszystkie te diagonalizacje są zasadniczo tym samym dowodem . Niektóre z nich są niewielkimi wariantami dowodu, które dają nieco silniejsze / słabsze stwierdzenia, ale same dowody są zwykle tylko bardzo niewielkimi zmianami. (I wszystkie te dowody są w zasadzie takie same jak oryginalny dowód Cantora o licznościach, który jest taki sam jak dowody niekompletności Godela i Chaitina, które są tylko sprawiedliwymi wersjami twierdzeń paradoksu Russella ... Tak bardzo, że jednocześnie zastanawiałem się, czy można sformalizować w jakiś sposób matematyki odwrotnej twierdzenie, które mówiło, że istniał tylko jeden taki dowód).

Warto jednak zauważyć, że istnieją dowody na inne stwierdzenia - zwykle innego smaku - które są diagonalizacjami, które są naprawdę, naprawdę, możliwe do udowodnienia, inne niż diagonalizacja stosowana w celu udowodnienia np. Nierozstrzygalności problemu zatrzymania.

Joshua Grochow
źródło

Nie znam dużo tego tematu, ale czy twierdzenie Lawve'a o stałym punkcie nie jest powszechnym uogólnieniem prawie wszystkich z nich?

Sasho Nikolov