Problemy klasy NPC, o których mówiliśmy w poprzednich punktach wykładu, były problemami "trudnymi", jednak nie możemy z całą stanowczością powiedzieć, że nie da się ich rozwiązać w sposób "łatwy". Po prostu nie wiemy, czy istnieją dla nich wielomianowe algorytmy. Są jednak problemy, dla których udowodniono, że są trudne, że nie istnieją  i nigdy nie będą mogły być wynalezione wielomianowe algorytmy ich rozwiązywania. Do takich problemów należy m.in. problem "wież Hanoi", należą uogólnione wersje gry w szachy, w której gra toczy się na planszy n ´ n, problem spełniania własności algorytmicznych wyrażonych w pewnym rozszerzeniu rachunku zdań.  Dla tych problemów udowodniono, wykładnicze dolne oszacowanie złożoności.

Zapomnijmy na chwilę o sprawie kosztu algorytmów. Wszystkie problemy omawiane do tej pory miały jakieś rozwiązania w postaci algorytmów. Nawet, jeśli to rozwiązanie wymagało bardzo dużo czasu, to jednak mogliśmy określić metodę postępowania prowadzącą do rozwiązania problemu. O problemach decyzyjnych tego typu mówimy, że są rozstrzygalne. Są jednak problemy, które tej cechy nie posiadają: nie istnieje dla nich metoda postępowania, która po skończonej liczbie kroków da rozwiązanie. Takie problemy  nazywamy nieobliczalnymi, a problemy decyzyjne tego typu nazywamy nierozstrzygalnymi.

Przykład 5.1

Problem sprawdzenia, czy formuła klasycznej logiki predykatów jest tautologią, jest nierozstrzygalny. Jeśli dana formuła rachunku predykatów jest tautologią, to umiemy się o tym przekonać w skończonym czasie. Jeśli jednak nie jest to tautologia, to nie ma takiej metody, która po skończonej liczbie kroków pozwoliłaby przerwać postępowanie i zdecydować, że to nie jest tautologia. J

Przykład 5.2

Rozważmy problem, który przypomina zadanie układania kafelków w domu. Niech będą dane "kafelki" -kwadraty podzielone przekątnymi na cztery części, z których każda została w pewien sposób pokolorowana. Mamy skończony zbiór X wzorców "kafli". Zadanie polega na znalezieniu odpowiedzi na pytanie, czy dowolną skończoną powierzchnię można pokryć za pomocą "kafli" takich jak w zbiorze X, w taki sposób, że sąsiadujące "kafelki" pasują do siebie ( np. zgadzają się ich kolory). Zakładamy, podobnie jak w problemie układanki (por. punkt 15.1), że "kafle" mają ustaloną orientację i nie można ich obracać, oraz że liczba kafli każdego typu jest nieograniczona. Problem ten nazywa się problemem domina (por. D. Harel, Rzecz o istocie informatyki, WNT 1992). Udowodniono, że nie ma i nigdy nie będzie w przyszłości, algorytmu, który po skończonej liczbie kroków odpowiadałby, że pokrycie danej powierzchni jest lub, że pokrycie nie jest możliwe. Problem domina jest nierozstrzygalny. J

Do klasy problemów nierozstrzygalnych należą też problemy szczególnie ważne dla informatyków. Jednym z nich jest problem stopu.

Dany jest pewien algorytm i dane do tego algorytmu. Zadanie polega na sprawdzeniu, czy dla tych danych algorytm kończy obliczenia po skończonym czasie, czy nie.

Stop(A, d) = true  wttw A kończy obliczenie dla danych d.

Możemy sprawdzić, co się stanie, uruchamiając po prostu algorytm A na jakimś komputerze. Jeśli jednak algorytm A dla pewnych danych ma obliczenie nieskończone, to jak się o tym przekonać? A może uda się znaleźć postępowanie algorytmiczne, metodę, która potrafi przeanalizować nasz algorytm A i jego dane, i odpowie na nasze pytanie, bez konieczności wykonywania algorytmu A?

Rozważmy zadanie ogólniejsze: spytajmy, czy istnieje algorytm (jednorodna metoda postępowania), który dla dowolnego algorytmu i danych do niego potrafi stwierdzić, czy algorytm zatrzyma się dla tych danych, czy też nie zatrzyma się? Tak sformułowany problem nosi nazwę problemu stopu (halting problem). Niestety odpowiedź jest negatywna: nie istnieje algorytm, który rozwiązuje problem stopu.

Dowód. Załóżmy przeciwnie, że istnieje algorytm Q(A,x), który dla dowolnego algorytmu A napisanego w pewnym ustalonym języku programowania i dla ustalonych danych x, po skończonej liczbie kroków odpowiada na pytanie, czy A zapętla się dla danych x, czy też nie. Przyjmijmy, że Q daje wynik "tak", gdy dany program A zatrzymuje się, i daje wynik "nie", gdy program A ma dla danych x nieskończoną pętlę. Użyjemy teraz algorytmu Q do skonstruowania nowego programu S. Po pierwsze wejściem do programu S będzie treść badanego algorytmu A, następnie wykonamy algorytm Q dla danych  (A, A), tzn. A jest raz traktowane, jako tekst algorytmu, a drugi raz jako napis opisujący jego dane wejściowe. Ponadto w przypadku, gdy Q(A,x) odpowiada  "tak" dopiszmy nieskończoną pętlę. Nowy algorytm S ma więc np. postać:

S(A) = {x := kopia(A); Q(A,x); if  wynik="tak" then while true do i := i od fi}

Program S dla dowolnego algorytmu A albo powinien się zatrzymać, albo nie. Użyjmy programu S do sprawdzenia, jak zachowuje się sam program S. Jeżeli  S(S) zatrzymuje się, to znaczy, że algorytm Q(S,S) odpowiedział "nie". Oznacza to jednak, że algorytm S nie zatrzymuje się dla danych S. Otrzymaliśmy sprzeczność. Przypuśćmy więc przeciwnie, że program S(S) nie zatrzymał się. Mogło się tak stać tylko wtedy, gdy program S wpadł w nieskończoną pętlę, którą dopisaliśmy do programu Q. To oznacza, że algorytm Q musiał odpowiedzieć "tak". Jednak taka odpowiedź znaczy, że program będący argumentem Q, tzn. S, nie zapętla się dla rozważanych danych, czyli program S nie zapętla się dla danych S. Znów sprzeczność. Ale przecież zgodziliśmy się na początku, że program albo się zatrzymuje, albo nie zatrzymuje się.  Wynika stąd, że S nie ma prawa istnieć, a dokładniej, nie istnieje hipotetyczny algorytm Q. J

Pytanie 8: Czy problem spełniania dla formuł rachunku zdań jest rozstrzygalny ?