Redukcje wśród nierozstrzygniętych problemów

Przykro mi, jeśli na to pytanie ma jakąś trywialną odpowiedź, której mi brakuje. Ilekroć badam jakiś problem, który okazał się nierozstrzygalny, zauważam, że dowód polega na zmniejszeniu do innego problemu, który okazał się nierozstrzygalny. Rozumiem, że tworzy to pewien porządek na poziomie trudności problemu. Ale moje pytanie brzmi - czy udowodniono, że wszystkie problemy, których nie można rozstrzygnąć, można zredukować do innego problemu, którego nie można rozstrzygnąć. Czy nie jest możliwe, że istnieje nierozwiązywalny problem, który nie może zostać zredukowany do żadnego innego nierozstrzygalnego problemu (stąd, aby udowodnić nierozstrzygalność takiego problemu, nie można stosować redukcji). Jeśli zastosujemy redukcje do stworzenia kolejności stopnia obliczalności, problemowi temu nie będzie można przypisać takiego stopnia.

computability reductions undecidability swarnim_narayan
źródło

Krótka odpowiedź: daleka od trywialności! Spójrz na hierarchię arytmetyczną .

Hendrik

Co o tym: Jeśli jest językiem nierozstrzygalny i być najmniejszy element w

. Następnie

sprowadza (i odwrotnie) i

. Jeśli dodatkowo dodasz element do

(powiedz, że najmniejszy element nie znajduje się w

), masz redukcję 1-1.

L

$L$

x min L

$x \min L$

L

$L$

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$

L

$L$

L^{'}

$L'$

L

$L$

Pål GD

Odpowiedzi:

Jak wspomniał Hendrik Jan, w rzeczywistości istnieją różne stopnie nierozstrzygalności. Na przykład problem decydowania o tym, czy maszyna Turinga zatrzyma się na wszystkich wejściach, jest trudniejszy niż problem zatrzymania, w tym sensie: nawet biorąc pod uwagę wyrocznię dotyczącą problemu zatrzymania, nie możemy zdecydować, czy dana maszyna Turinga zatrzyma się na wszystkich wejściach .

Jedną ważną techniką stosowaną do pokazywania takich relacji jest diagonalizacja . Stosując diagonalizację, mając problem , zawsze możemy znaleźć trudniejszy problem, mianowicie problem zatrzymania dla maszyn Turinga z dostępem do wyroczniNowy problem jest trudniejszy w tym sensie: maszyna Turinga z dostępem do wyroczni do nie może rozwiązać . W tym sensie nie ma „najtrudniejszego” problemu. $P$ $P$ $P'$ $P$ $P'$

Yuval Filmus
źródło

Dziękuję za Twoją odpowiedź. Zrozumiałem, co mówisz. Możemy budować „trudniejsze” problemy z „trudnych”. Ale czy te schematy konstruowania trudniejszych problemów od trudnych (na przykład powiedz, że diagonalizacja jest jednym z takich schematów, jak wspomniałeś) koniecznie obejmują „wszystkie” istniejące nierozwiązywalne problemy (tj. Czy gwarantuje się zbudowanie zestawu wszystkich nierozstrzygalnych problemów). Czy nie jest możliwe, że niektóre zostały pominięte w konstrukcji i nie można ich zbudować z innych nierozstrzygalnych?

swarnim_narayan

Przeciwnie, wiemy, że większość problemów zostanie pominięta, ponieważ istnieje tylko policzalnie wiele możliwych do zdefiniowania problemów, ale w sumie niezliczona ilość problemów. Mówiąc konkretniej, pytasz, jak zdefiniować „naprawdę trudne” problemy, teoretyczny analog rekurencji dużych kardynałów. Jeśli jesteś tym zainteresowany, zadaj nowe pytanie dotyczące tego aspektu.

Yuval Filmus

Podobny problem pojawia się przy konstruowaniu hierarchii szybko rosnących funkcji rekurencyjnych, w którym to przypadku wiadomo, że w pewnym sensie nie ma możliwości zbudowania ładnej, wyczerpującej hierarchii.

Yuval Filmus,