Problem nierozstrzygalny - w teorii obliczeń - problem decyzyjny, dla którego nie istnieje algorytm, który po skończonej liczbie kroków jednoznacznie odpowie tak albo nie dla dowolnych danych wejściowych.
Turing w 1937 roku wykazał, że udzielenie odpowiedzi na pytanie, czy Maszyna Turinga o numerze n wykonując działania nad liczbą m zakończy dawniej swoją pracę, czy też przewidziany dla niej algorytm będzie realizowany w nieskończoność, jest problemem nierozstrzygalnym.
Innym przykładem dylematu nierozstrzygalnego jest tzw. zadanie Gödla o postaci 17 Gen r (generalizacja {kwantyfikator ogólny} formuły r względem zmiennej z numerem 17) Jest to zdanie posiadające tę własność, że ani ono ani jego negacja nie dają się formalnie dowieść. Zdanie nierozstrzygalne 17 gen r powstało w wyniku odwzorowania antynomii logicznej (zwanej antynomią Richarda) poprzez tak zwaną arytmetyzacją języka klasycznego rachunku zdań. Arytmetyzacja języka dopuszcza na odwzorowanie relacji logicznych jakie zachodzą pomiędzy zdaniami w relacje arytmetyczne pomiędzy liczbami stanowiącymi numery tych zdań. Dzięki temu zamiast o relacjach logicznych da się mówić o relacjach arytmetycznych.
Istnienie zdania 17 gen r jest powodem nierozstrzygalności arytmetyki, uważanej do czasów Gödla za system rozstrzygalny, to znaczy taki, w którym albo da się dowieść dowolna formuła arytmetyczna albo negacja tej formuły. Inaczej mówiąc zbiór twierdzeń arytmetycznych jest nieobliczalny, co znaczy że nie da się w skończonej ilości kroków rozstrzygnąć czy dany element tego zbioru, będący bez wątpienia twierdzeniem arytmetycznym, jest czy nie jest elementem zbioru twierdzeń.
Dla przykładu wspomniane zdanie 17 Gen r trzeba do zbioru twierdzeń arytmetycznych wtedy oraz tylko wtedy kiedy do niego nie należy. Tymczasem zbiór dowodów twierdzeń arytmetycznych jest obliczalny, albowiem w skończonej ilości kroków da się rozstrzygnąć, czy dany ciąg napisów jest czy nie jest dowodem danego twierdzenia. Tak więc zbiór zdań prawdziwych nie pokrywa się ze zbiorem twierdzeń. Istnieją bowiem zdania prawdziwe, których nie da się dowieść. Jednym z nich jest właśnie zdanie 17Gen r. Z faktu nierozstrzygalności arytmetyki wynika z kolei niemożliwość udowodnienia jej niesprzeczności.
Nierozstrzygalność dylematu stopu
-
Osobny artykuł: Problem stopu.
Sprawdź też