Czy istnieją problemy, których komputery nie mogą rozwiązać?

Informacje, rozrywka, praca, edukacja, szybkie rozwiązania złożonych problemów… zwykle mamy całkiem solidne wyobrażenie o tym, czego chcemy, używając komputera. Właściwie bywają momenty, gdy system wydaje się zdolny rozwiązać wszystko, co prowadzi nas do bardzo ciekawego ćwiczenia logicznego: wyobraź sobie komputer z nieskończonym czasem, energią i mocą obliczeniową. Czy istnieje coś, czego – mimo tych zalet – nie potrafi rozwiązać? Krótka odpowiedź brzmi „tak”, ale do reszty potrzebujemy pomocy Toma Scotta…

Problem Hilberta i Entscheidungsproblem

Ile razy to się zdarzyło? Proste pytanie wrzuca nas w czarną dziurę logiki i rozumu. Matematyk David Hilbert (ten sam od nieskończonego hotelu) wraz ze swoim kolegą Wilhelmem Ackermannem utknął w takiej sytuacji w 1928 roku, kiedy obaj przedstawili wyzwanie Entscheidungsproblem, czyli „Problem decyzyjny”. W bardzo luźnym ujęciu problem ten proponuje: czy można ustalić, czy dane stwierdzenie lub zdanie jest dowodliwe czy nie? Czy przy wystarczającym czasie i energii możemy znaleźć odpowiedź na wszystko?

Co to ma wspólnego z komputerami?

A co to ma wspólnego z komputerami? Właściwie pytanie Hilberta można przełożyć na świat informatyki w bardzo szczególny sposób: wyobraź sobie kod programu – dowolnego programu. Czy można przeanalizować ten kod i automatycznie określić, czy się zatrzyma, czy wpadnie w nieskończoną pętlę? W tym momencie ktoś podaje przykład:

10 PRINT “HOLA MUNDO”
20 GOTO 10
RUN

Oczywiście ten fragment kodu prowadzi do nieskończonej pętli… ale różnica polega na tym, że został tak zaprojektowany. Ustalenie, czy niektóre programy się zatrzymują, czy działają wiecznie, to łatwizna. Pomysł wzięcia dowolnego kodu – wszystkich kodów – i przeanalizowania ich, aby definitywnie stwierdzić, czy kończą pracę, czy zapętlają się, może wydawać się prosty na pozór, jednak jest matematycznie niemożliwy. Skąd to wiemy? Dzięki niejakiemu Alanowi Turingowi i słynnej maszynie noszącej jego nazwisko, z roku 1936.

Paradoks Toma Scotta

W tym miejscu Tom Scott przychodzi nam z pomocą ze swoim wyjaśnieniem: wyobraźmy sobie program o nazwie „Halts”, który potrafi spojrzeć na próbkę dowolnego kodu i ustalić, czy się zatrzyma (nie musimy wiedzieć, jak to robi – ważne, że działa). I znowu: „Halts” widzi kod i odpowiada „tak” (zatrzymuje się) albo „nie” (nieskończona pętla). Teraz wyobraźmy sobie drugi program połączony z „Halts”, który robi dokładnie odwrotność jego odpowiedzi. To znaczy: jeśli „Halts” stwierdził, że kod się zatrzyma, drugi program wpada w nieskończoną pętlę, a jeśli stwierdził, że kod zapętli się, drugi program się zatrzymuje.

Ten system nazwano „Opuesto”, ponieważ w istocie robi odwrotność tego, co do niego wprowadzisz… ale w tym miejscu Turing łamie wszystko swoją propozycją: weź cały kod składający się na „Opuesto” i pozwól mu przeanalizować samego siebie. Wynik… jest taki, że nie ma wyniku. To paradoks, matematyczna niemożliwość. Nawet przy idealnych warunkach początkowych minimalna zmiana powoduje kolaps procesu. I tu znajduje się nasza odpowiedź na pierwotne pytanie: istnieje co najmniej jedna rzecz, której komputery nie mogą i nie będą mogły rozwiązać.