Marzenie o jednej mechanicznej procedurze rozstrzygającej całą logikę pierwszego rzędu zostało matematycznie obalone
Entscheidungsproblem, sformułowany przez Hilberta i Ackermanna, pytał o algorytm, który dla dowolnej formuły logiki pierwszego rzędu zawsze rozstrzygnie, czy jest ona logicznie prawdziwa we wszystkich strukturach. W 1936 roku Alonzo Church i Alan Turing, używając różnych formalizmów obliczalności, wykazali że taka ogólna procedura nie istnieje. Wynik nie oznacza, że żadnych fragmentów logiki nie da się automatycznie rozstrzygać — wiele szczególnych teorii ma procedury decyzyjne. Upadł pomysł jednego uniwersalnego mechanizmu dla całej logiki pierwszego rzędu.
Hilbert chciał zmechanizować rozstrzyganie
Na początku XX wieku rozwój formalnej logiki rodził nadzieję, że poprawność twierdzeń można sprowadzić do skończonej, mechanicznej procedury. Entscheidungsproblem pytał o metodę, która po otrzymaniu dowolnego zdania logiki pierwszego rzędu zawsze zakończy się odpowiedzią „ważne” albo „nieważne”. Gdyby istniała, duża część formalnego rozumowania mogłaby zostać sprowadzona do algorytmu.
Church i Turing zdefiniowali obliczalność na dwa sposoby
Church używał rachunku lambda i funkcji rekurencyjnych, Turing — abstrakcyjnych maszyn wykonujących elementarne kroki na taśmie. Oba formalizmy okazały się równoważne pod względem klasy funkcji obliczalnych. Niezależne negatywne wyniki pokazały, że nie istnieje algorytm decydujący pełną logikę pierwszego rzędu.
Nie należy mylić tego z twierdzeniem o zupełności Gödla
Twierdzenie Gödla o zupełności dla logiki pierwszego rzędu mówi, że każde logicznie ważne zdanie ma formalny dowód. Można więc systematycznie wyliczać dowody i w końcu znaleźć dowód zdania ważnego. Problem polega na przypadku nieważnym: samo oczekiwanie może nigdy nie dać końcowej odpowiedzi. Zupełność dowodowa nie oznacza istnienia procedury decyzyjnej.
Po negatywnym wyniku zaczęto szukać mniejszych obszarów, które są rozstrzygalne
Brak jednego algorytmu dla całej logiki nie zakończył automatycznego wnioskowania. Przeciwnie, skierował uwagę na fragmenty, w których decyzja jest możliwa, oraz na procedury półdecyzyjne i heurystyki. Współczesne systemy weryfikacji i solvery logiczne działają skutecznie właśnie dlatego, że korzystają ze struktury konkretnych klas problemów zamiast próbować rozwiązać wszystko.
Jaki rodzaj granicy tu widzimy?
Ten przykład warto czytać bardzo precyzyjnie. W matematyce „nie ma rozwiązania” może oznaczać kilka zupełnie różnych sytuacji: problem może być nadal otwarty, może istnieć dowód niemożliwości przy zadanych regułach, może nie istnieć uniwersalny algorytm, albo dane zdanie może być niezależne od wybranego systemu aksjomatów. Te przypadki nie są zamienne. Siła matematycznego wyniku bierze się właśnie z dokładnego określenia warunków: dowód nie mówi ogólnie, że „człowiek tego nie potrafi”, lecz wskazuje, czego nie można uzyskać przy konkretnych założeniach. To odróżnia granicę matematycznej wiedzy od zwykłego braku pomysłu.
Redukcja jest podstawowym narzędziem dowodzenia niemożliwości algorytmicznej
Zamiast analizować wszystkie możliwe programy, matematycy często pokazują: gdyby istniał algorytm dla problemu X, można byłoby za jego pomocą rozwiązać problem Y, o którym już wiadomo, że jest nierozstrzygalny. Taka redukcja przenosi niemożliwość z jednego obszaru do drugiego. Jest to metoda niezwykle mocna, bo pozwala wykazać brak algorytmu nawet dla problemów, które z zewnątrz wyglądają jak czysta algebra czy elementarna teoria liczb.
Nierozstrzygalność nie oznacza braku użytecznych algorytmów
Twierdzenie o braku uniwersalnej procedury nie wyklucza algorytmów dla ogromnych podklas, metod kończących się na typowych danych, półalgorytmów znajdujących odpowiedź w jednej z dwóch sytuacji ani narzędzi, które czasem odpowiadają „nie wiem”. W praktyce właśnie tak działa duża część automatycznego wnioskowania. Granica pojawia się dopiero wtedy, gdy wymagamy jednej procedury, która dla każdego dozwolonego wejścia zawsze się zatrzyma i zawsze poda poprawną odpowiedź. W praktyce wynik uczy też, jak czytać słowo „nierozstrzygalny”: nie oznacza ono, że żadna instancja nie ma odpowiedzi albo że nie można rozwiązać bardzo wielu przypadków. Oznacza brak jednej gwarantowanej procedury dla całej klasy wejść. To subtelna, ale fundamentalna różnica między trudnością obliczeniową a nieobliczalnością.