Problem nierozstrzygalny to kwestia, której nie da się rozwiązać jednym algorytmem. Jest to przedmiot zainteresowania matematyki i programowania komputerowego, gdzie nierozstrzygalny problem ma istotne implikacje. Naukowcy zainteresowani maszynami Turinga, na przykład, zajęli się problemem zatrzymania, przyglądając się, kiedy programy komputerowe przestają działać, a nie działać w nieskończoność. Podobnie jak w przypadku innych wyzwań w matematyce, liczne badania dotyczą sposobów obejścia nierozstrzygalnych problemów, a także identyfikowania nowych problemów do dalszej oceny i badania.
Temat ten obejmuje problemy decyzyjne, pytania z odpowiedziami „tak” lub „nie”. W matematyce są one często przedstawiane w postaci wzorów. Prostym przykładem może być „Dla dowolnych liczb rzeczywistych, czy X jest równomiernie podzielne przez Y?” Jest to problem rozstrzygający, ponieważ jeśli komputer otrzyma jakieś wartości X lub Y, może użyć algorytmu, aby odpowiedzieć na pytanie. Bardziej złożone problemy mogą nie być możliwe do rozwiązania za pomocą jednego algorytmu dla wszystkich możliwych wartości.
W takich przypadkach algorytm może być dokładny dla niektórych odpowiedzi, ale może nie być w stanie odpowiedzieć na inne wartości. Biorąc pod uwagę pewne wartości, algorytm mógł przejść przez serię kroków, aby określić, czy odpowiedź na pytanie brzmi tak, czy nie. W innych przypadkach nie byłby w stanie tego zrobić, ponieważ nie miałby niezbędnych informacji. Jest to znany problem z niektórymi problemami związanymi z macierzami, analizą złożoną i niektórymi innymi funkcjami.
Identyfikacja nierozstrzygalnego problemu może wystąpić w kontekście badań matematycznych i informatycznych. Gdy problem zostanie uznany za nierozstrzygnięty, naukowcy mogą zastosować różne taktyki, aby obalić tę teorię. Może to obejmować opracowanie algorytmów, które działają dla niektórych wartości, omówienie specyfiki problemu, który uniemożliwia skuteczne leczenie za pomocą algorytmu dla wszystkich wartości, oraz powiązanych działań. Publikacje z dziedziny matematyki i informatyki mogą omawiać najnowsze postępy w tej dziedzinie na przykładach algorytmów, które badacze wykorzystali do zbadania granic nierozstrzygalnego problemu.
Daleki od bycia tematem jedynie zainteresowań teoretycznych, ten nierozstrzygalny problem może mieć ważne implikacje dla świata rzeczywistego. Na przykład niektóre wirusy komputerowe powodują nierozstrzygalne problemy z systemami. Próba rozwiązania problemu przez system może pochłaniać zasoby, powodując zawieszenie się systemu lub tworzenie luk w zabezpieczeniach. Podobnie, technicy mogą spowodować problem z systemem, nieświadomie przedstawiając mu problem, którego nie może rozwiązać. Mogą potrzebować zakończyć program lub operację, co może spowodować utratę danych.