Przyjrzymy się najpierw kilku przykładom problemów, którymi będziemy się zajmować.

1.

Dana jest liczba naturalna, czy jest to liczba pierwsza?

2.

Dana jest liczba naturalna, oblicz jej kwadrat.

3.

Dane jest słowo, czy jest ono palindromem (palindrom to słowo, które brzmi tak samo czytane od tyłu, np. kajak)?

4.

Dane jest słowo, oblicz, ile ma różnych liter.

5.

Dana jest liczba rzeczywista, oblicz jej pierwiastek.

6.

Dany jest graf, czy z każdego wierzchołka da się przejść do każdego?

Już na tych przykładach możemy zauważyć, że nasze problemy są różnorakich rodzajów. Jedne domagają się jedynie odpowiedzi TAK lub NIE, inne natomiast chcą, żeby podać im jakiś bardziej skomplikowany obiekt, często liczbę. Pierwszy rodzaj problemów będziemy nazywać problemami decyzyjnymi, a drugi problemami obliczeniowymi. Wśród naszych przykładów problemy decyzyjne mają numery 1, 3 i 6, a problemy obliczeniowe 2, 4 i 5. Skupimy się głównie na problemach decyzyjnych.

Czym jednak ma być rozwiązanie takiego problemu? Domyślni Czytelnicy pewnie już wiedzą: oczekiwanym rozwiązaniem jest program, który wczytuje wejście, np. liczbę naturalną, a na końcu swojego działania zwraca odpowiedź TAK lub NIE. Czy więc każdy problem da się rozwiązać? Okazuje się, że nie!

Najprostszy argument za tym, że istotnie nie każdy problem można rozwiązać, jest taki, że możliwych problemów jest więcej niż możliwych rozwiązań (czyli programów). To stwierdzenie może nam się wydać dziwne, przecież zarówno problemów, jak i programów jest nieskończenie wiele. Czy możemy w ogóle mówić, że jedna nieskończoność jest większa niż druga i co by to miało znaczyć? Możemy! Żeby to zrozumieć, musimy zagłębić się trochę w teorię mocy, dziedzinę matematyki, która zajmuje się wielkościami zbiorów. A teoria, którą zobaczymy, sama w sobie jest niezwykle ciekawa.

Równoliczność

Dla dwóch zbiorów skończonych i intuicyjnie mówimy, że są równoliczne, jeśli po prostu wielkość jednego jest równa wielkości drugiego. Można jednak powiedzieć, że i są równoliczne, jeśli elementy i elementy da się połączyć w pary: w każdej parze jeden element z i jeden z tak, żeby wszystkie elementy trafiły do którejś pary, ale żaden nie trafił do dwóch par. Okazuje się, że ta druga definicja jest właściwym spojrzeniem na sprawę i bardzo dobrze zachowuje się również dla zbiorów nieskończonych. Spójrzmy teraz na kilka przykładów nieskończonych zbiorów równolicznych. Czy zbiór liczb całkowitych dodatnich i zbiór liczb całkowitych większych od dziesięciu są równoliczne? Tak, łatwo zobaczyć, że można elementy obu zbiorów poustawiać w nieskończenie wiele par: To już może nam się wydać dziwne, przecież zbiór powstał przez usunięcie ze zbioru dziesięciu liczb: jak więc może być równoliczny? Może - taka jest nasza definicja, musimy po prostu pożegnać się z intuicją wziętą ze skończonych zbiorów, że jeśli usuwamy coś ze zbioru, to staje się on istotnie mniejszy. Teraz będą się działy rzeczy jeszcze dziwniejsze. Czy zbiór dodatnich liczb całkowitych jest równoliczny ze zbiorem dodatnich liczb parzystych Nietrudno zauważyć, że tak, połączenie w pary wygląda następująco: każda liczba ze zbioru jest w parze z dwa razy większą liczbą ze zbioru Możemy teraz dokonać obserwacji, dzięki której później łatwiej będzie nam sprawdzać, czy pewien zbiór jest równoliczny ze zbiorem liczb naturalnych (zakładamy tu, że 0 też jest liczbą naturalną). Zauważmy mianowicie, że nieskończony zbiór jest równoliczny z wtedy i tylko wtedy, gdy da się ustawić elementy w nieskończony ciąg. Po pierwsze, jeśli istotnie jest równoliczny z to ustawienie w nieskończony ciąg jest łatwe: najpierw stoi element będący w parze z potem element będący w parze z potem element będący w parze z itd. Z drugiej strony jeśli umiemy ustawić elementy w nieskończony ciąg, to możemy połączyć je w pary w elementami : pierwszy element ciągu będzie w parze z drugi będzie w parze z a ogólnie -ty element ciągu będzie w parze z liczbą naturalną

Zastanówmy się teraz, czy zbiór liczb naturalnych jest równoliczny ze zbiorem wszystkich liczb całkowitych Nietrudno zobaczyć, że tak, elementy zbioru liczb całkowitych da się ustawić w nieskończony ciąg, na przykład w taki sposób:

na miejscach nieparzystych będziemy ustawiać coraz większe liczby nieujemne, a na miejscach parzystych coraz mniejsze liczby ujemne. Pokażemy teraz nawet więcej: że zbiór dodatnich liczb wymiernych jest równoliczny ze zbiorem liczb naturalnych. To wygląda bardzo dziwnie, bo przecież liczb wymiernych wydaje się dużo więcej, przyjrzyjmy się jednak konstrukcji. Wyobraźmy sobie nieskończoną tablicę ułamków, gdzie w -tej kolumnie i -tym wierszu od dołu wpisujemy ułamek Pokażemy teraz, jak wszystkie elementy ustawić w nieskończony ciąg. Będziemy chodzić po tablicy zygzakiem i dodawać nowe liczby wymierne do ciągu. Najpierw ustalmy trasę przemarszu. Zaczniemy z pola pójdziemy w prawo do i po skosie do Teraz w górę do i po skosie przez do Teraz w prawo do i po skosie przez dwa pola do W ten sposób kontynuujemy chodzenie po kolejnych skosach coraz dalszych od pola A jak tworzymy ciąg? Jeśli wchodzimy na pewne pole i ułamek przez nas zobaczony jest nową liczbą (czasem może się zdarzyć, że tę liczbę już widzieliśmy, np. ), to dodajemy go na koniec i idziemy dalej. Czyli początkowe wartości nieskończonego ciągu wyglądają następująco: ( nie ustawiamy, bo i ta liczba już jest w ciągu), itd. Nietrudno zauważyć, że wszystkie dodatnie liczby wymierne zostaną kiedyś dodane do ciągu, bo nasz zygzak dojdzie w końcu do każdego ułamka. Co więcej, żadna liczba nie zostanie przydzielona więcej niż raz. Pokazaliśmy więc, że liczby naturalne i dodatnie liczby wymierne są równoliczne. Niewiele więcej wysiłku potrzeba, żeby pokazać, że zbiór wszystkich liczb wymiernych jest również równoliczny z (Czytelników Ambitnych zachęcamy do samodzielnego stworzenia odpowiedniego ciągu).

Metoda przekątniowa

Czyż więc istnieją w ogóle zbiory nieskończone, które nie są równoliczne z Tak, i to jest treścią słynnej konstrukcji Georga Cantora, który w roku 1891 wskazał pierwszy taki przykład. Konstrukcja zwana jest przekątniową, zaraz zobaczymy dlaczego. Metoda przekątniowa, czyli konstrukcje tego typu stały się standardem w matematyce, zresztą i w naszej historii jeszcze się pojawią. Pokażemy teraz, że liczby rzeczywiste nie są równoliczne z liczbami naturalnymi, a konkretnie, że nie da się ustawić ich w ciąg. Wystarczy wykazać, że nawet liczb rzeczywistych, które zaczynają się od 0 i mają rozwinięcia dziesiętne po przecinku zawierające tylko zera i jedynki, nie da się ustawić w nieskończonym ciągu.

Przypuśćmy nie wprost, że jednak da się je ustawić w ciąg: Przyjmijmy oznaczenie na -tą cyfrę po przecinku w rozwinięciu dziesiętnym liczby

Skonstruujemy teraz liczbę która zawiera tylko zera i jedynki po przecinku, ale nie występuje w ciągu, co doprowadzi do sprzeczności. Zaczynamy zerem przed przecinkiem, a jej -tą cyfrę po przecinku definiujemy jako Innymi słowy, zapewniamy, że -ta cyfra jest inna niż -ta cyfra liczby Czy może występować w naszym ciągu? Powiedzmy, że występuje, na pewnej pozycji o numerze Czyli Zaraz, ustaliliśmy jednak, że -ta cyfra jest różna od -tej cyfry Zatem i otrzymujemy sprzeczność z założeniem, że wszystkie liczby występują w ciągu. Wykazaliśmy więc, że zbiory liczb rzeczywistych i naturalnych nie są równoliczne. Tak naprawdę to wykazaliśmy, że zbiór i zbiór nieskończonych ciągów zero-jedynkowych nie są równoliczne. A tak właściwie to wykazaliśmy nawet więcej: że zbiór nieskończonych ciągów zero-jedynkowych jest większy niż Bo co oznacza, że nie można go ustawić w nieskończony ciąg? To, że jak byśmy nie wybrali nieskończonego ciągu nieskończonych ciągów zero-jedynkowych, to któreś ciągi zero-jedynkowe nie zostaną wybrane. Jeśli mamy osób i krzeseł i jakkolwiek byśmy nie wybrali osób, by siadły na krzesłach, to pewne osoby będą stać, to znaczy, że Tę intuicję ze skończonych zbiorów możemy przenieść na zbiory nieskończone: nieskończonych ciągów zero-jedynkowych (i liczb rzeczywistych też) jest więcej niż liczb naturalnych. Pozostają tu pewne kłopoty techniczne, jednak da się je przezwyciężyć i pokazać, że z taką definicją większego zbioru wszystko jest w porządku (pisaliśmy o tym w Delcie 2/2016 w artykule Czy trzeba dowodzić rzeczy oczywistych?).

Problem bez rozwiązania

Jak to wszystko wykorzystać do pokazania, że nie każdy problem da się rozwiązać? Zastanówmy się najpierw, ile jest programów zapisanych za pomocą skończonego alfabetu? Takich ustalonej długości jest, oczywiście, skończenie wiele. Nietrudno więc zauważyć, że wszystkie programy można ustawić w nieskończony ciąg: zaczynamy od najkrótszych, a dla tej samej długości ustawiamy alfabetycznie. A więc programów jest tyle co liczb naturalnych. A ile jest problemów? Skupmy się na problemach decyzyjnych dla liczb naturalnych, już tych będzie dużo. Zauważmy, że dla każdego podzbioru liczb naturalnych mamy inny problem decyzyjny: "Czy dana liczba naturalna należy do zbioru " A zatem problemów jest przynajmniej tyle, co podzbiorów liczb naturalnych. Zauważmy jednak, że można łatwo wskazać odpowiedniość między nieskończonymi ciągami zero-jedynkowymi a podzbiorami liczb naturalnych. Zbiorowi odpowiada ciąg, który ma jedynki dokładnie na miejscach o indeksach należących do a zera w pozostałych miejscach. A zatem problemów decyzyjnych jest przynajmniej tyle, co nieskończonych ciągów zero-jedynkowych, czyli więcej niż liczb naturalnych, czyli więcej niż programów. Tym samym wykazaliśmy, że nie dla każdego problemu decyzyjnego istnieje odpowiadający mu program!

Zastanówmy się jednak chwilę, czy to jest naprawdę satysfakcjonująca odpowiedź. Powinny nas tak naprawdę interesować nie dowolne problemy, tylko takie, które jesteśmy w stanie wyrazić. Wyrazić w jakiś rozsądny, skończony sposób. Czyli właściwie tytułowe pytanie powinno brzmieć: "czy każdy opisany w skończony sposób problem da się rozwiązać?" Tu jednak widać od razu mankamenty naszej metody. Sensownie opisywalnych problemów jest co najwyżej tyle, ile skończonych opisów, więc co najwyżej tyle, ile skończonych tekstów. A skończone teksty, jak już wcześniej mówiliśmy, dadzą się ustawić w nieskończony ciąg (coraz dłuższe, a równie długie alfabetycznie), więc jest ich tyle co liczb naturalnych. Czyli sensownie opisywalnych problemów i ich potencjalnych rozwiązań (programów) jest tyle samo.

Czyżby to jednak oznaczało, że całe wcześniejsze rozważania przydały nam się tylko do tego, żeby rozwiązać głupio sformułowany problem? Bynajmniej! Oprócz tego, że poznaliśmy kawałek ciekawej teorii matematycznej, to użyjemy teraz opisanej wyżej metody przekątniowej, żeby rozwiązać ten już właściwie sformułowany problem.

Nierozstrzygalność

Zdefiniujemy teraz pewną dziwną funkcję, która posłuży nam później do dalszych konstrukcji. Zachęcamy Czytelników do tropienia podobieństw z konstrukcją Cantora. Rozważmy wszystkie programy, które na wejściu oczekują liczby naturalnej i na wyjściu zwracają też liczbę naturalną (zapewne inną). Istnieje ustawienie takich programów od najkrótszych do coraz dłuższych; niech będzie to ciąg Zdefiniujmy funkcję jako czyli 1 plus to, co -ty program zwraca, gdy dostaje liczbę Zastanówmy się teraz, czy istnieje pewien program, który oblicza naszą funkcję, czyli gdy dostanie liczbę na wejściu, to zwróci liczbę Zauważmy, że nie jest to możliwe. Przypuśćmy, że pewien program oblicza funkcję Wtedy dla każdego mamy Z drugiej jednak strony z definicji funkcji otrzymujemy A zatem sprzeczność. Już tu widać, że pewnych sensownych problemów nie da się rozwiązać, to znaczy nie istnieje program, który oblicza funkcję My szukamy jednak problemu decyzyjnego, który nie ma rozwiązania, a obliczenie funkcji to problem obliczeniowy.

O taki jednak nietrudno. Udowodnimy, że słynny Problem Stopu jest nierozstrzygalny, to znaczy, że nie istnieje żaden program, który go rozwiązuje. Problem ten jest następujący: mamy dany program pytanie brzmi, czy zatrzymuje się dla dowolnego wejścia, tzn. czy nie działa przypadkiem w nieskończoność dla któregoś z nich. Wróćmy jednak na chwilę do poprzedniego rozważanego zagadnienia: jak to - nie można obliczyć funkcji Jeśli chcemy obliczyć to wystarczy przeglądać programy od najkrótszych aż w końcu znajdziemy ten -ty, czyli Wtedy każemy mu obliczyć i na końcu dodamy 1. Coś tu nie gra, gdzie jest błąd? Błąd jest w założeniu, że możemy znaleźć -ty program. Trochę wynika on z tego, że nie zdefiniowaliśmy porządnie, czym jest program. Nie każdy przecież tekst jest programem. Przyjmijmy więc, że program to poprawny tekst w pewnym ustalonym języku programowania. To można łatwo sprawdzić, są kompilatory różnych języków programowania, które sprawdzają, czy dany tekst jest istotnie kodem programu w wybranym języku. Wymagamy jednak jeszcze od programu, żeby zawsze się kończył i zwracał jakąś liczbę. Istotnie: to wymaganie jest konieczne, żeby w ogóle mówić, iż program definiuje jakąś funkcję. I tu właśnie jest haczyk. Gdybyśmy umieli sprawdzać, czy dany program zawsze się kończy, to umielibyśmy zrealizować opisaną wyżej procedurę obliczania funkcji Wiemy jednak, że funkcja jest nieobliczalna, więc nie może istnieć metoda sprawdzania, czy dany program się zawsze kończy.

W ten sposób wykazaliśmy, że problem stopu istotnie jest nierozstrzygalny. Pierwszy zrobił to Alan Turing, jeden z pionierów informatyki, w 1936 roku. Przedstawiony dowód jest jednak nieco inny, bardziej bezpośrednio stosuje metodę przekątniową.

Problemów nierozstrzygalnych jest wiele, problem stopu nie jest tu jakiś wyjątkowy. Nierozstrzygalne są m.in. problem istnienia rozwiązań równań diofantycznych, obliczania złożoności Kołmogorowa (patrz Delta 8/2012, artykuł Niemożliwy skrót), pytanie, czy da się ułożyć nieskończoną płaszczyznę z ustalonego zbioru kolorowych kafelków, tak by kolory do siebie pasowały i wiele, wiele innych. To jednak temat na zupełnie inną opowieść.