Informatyka i programowanieGranice obliczeń — problemy łatwe, trudne i niemożliwe

Nawet równanie z liczbami całkowitymi może nie mieć algorytmicznego testu rozwiązania

Dziesiąty problem Hilberta pytał o ogólną procedurę, która dla wielomianowego równania z całkowitymi współczynnikami rozstrzygnie, czy istnieje rozwiązanie w liczbach całkowitych. Odpowiedź okazała się negatywna. Prace Davisa, Putnama, Robinson i ostateczny krok Jurija Matiyasevicha doprowadziły do wyniku, że nie istnieje algorytm rozwiązujący ten problem dla wszystkich równań diofantycznych. To niezwykłe, bo każde konkretne podstawienie liczb można łatwo sprawdzić, a rozwiązania można systematycznie wyszukiwać. Nie ma jednak uniwersalnej procedury, która zawsze potrafi również potwierdzić brak rozwiązania i zakończyć pracę.

Hilbert chciał procedury

W 1900 roku David Hilbert sformułował listę problemów, a dziesiąty dotyczył równań diofantycznych — wielomianów o całkowitych współczynnikach i całkowitych lub naturalnych rozwiązaniach, zależnie od równoważnego sformułowania. Pytanie miało charakter algorytmiczny avant la lettre: znaleźć metodę, która po otrzymaniu równania w skończonej liczbie kroków odpowie, czy rozwiązanie istnieje.

Szukanie „tak” jest łatwiejsze niż potwierdzenie „nie”

Jeżeli równanie ma rozwiązanie całkowite, można w zasadzie enumerować coraz większe zakresy kandydatów i testować podstawienia. Kiedy trafimy na rozwiązanie, mamy certyfikat. Jeżeli jednak rozwiązania nie ma, takie ślepe przeszukiwanie będzie trwało bez końca i nie powie nam, że dalsze próby są bezcelowe. Właśnie potrzeba zawsze kończącego rozstrzygnięcia obu przypadków jest tutaj kluczowa.

DPRM i reprezentacja obliczeń przez wielomiany

Martin Davis, Hilary Putnam i Julia Robinson zbudowali ogromną część mostu między zbiorami rekurencyjnie enumerowalnymi a równaniami diofantycznymi. Matiyasevich dostarczył brakującego elementu, a jego praca z 1970/1971 roku dała wynik, że każdy zbiór rekurencyjnie enumerowalny ma reprezentację diofantyczną. Ponieważ istnieją zbiory rekurencyjnie enumerowalne nierozstrzygalne, wynika stąd nierozstrzygalność ogólnego problemu Hilberta.

Nie każde równanie jest tajemnicą

Wynik nie mówi, że matematycy nie potrafią rozwiązać żadnych równań diofantycznych. Ogromne klasy mają znane metody, a wiele konkretnych równań można rozstrzygnąć. Nierozstrzygalność dotyczy istnienia jednego algorytmu obsługującego wszystkie wielomiany dopuszczone przez ogólne sformułowanie. To typowy wzorzec granic obliczalności: problemy szczególne pozostają osiągalne, lecz pełna klasa wymyka się automatyzacji.

Matematyka potrafi kodować program

Najbardziej zaskakującym aspektem jest to, że równania z dodawaniem i mnożeniem liczb całkowitych są wystarczająco ekspresywne, by odzwierciedlać zachowania obliczeń. Dzięki temu nierozstrzygalność nie jest wyłącznie własnością kodu programów czy maszyn Turinga. Pojawia się wewnątrz klasycznej teorii liczb, w pytaniu o istnienie rozwiązań zwykłych wielomianów.

Możemy szukać rozwiązania, ale brak rozwiązania jest trudniejszy

Dla konkretnego równania diofantycznego można systematycznie przeglądać coraz większe zakresy całkowitych kandydatów. Jeżeli rozwiązanie istnieje, taka procedura w końcu może na nie trafić i je zweryfikować. Jeżeli rozwiązania nie ma, samo bezowocne przeszukiwanie niczego nie kończy: po sprawdzeniu miliona zakresów nadal może istnieć rozwiązanie dalej. Dziesiąty problem Hilberta domagał się algorytmu, który zawsze kończy i poprawnie rozstrzyga oba przypadki dla dowolnego równania z tej klasy. Wynik Matiyasevicha, domykający prace Davisa, Putnama i Robinson, pokazuje, że takiej uniwersalnej procedury nie ma. To dobry przykład różnicy między możliwością enumerowania kandydatów a pełną rozstrzygalnością.

Nierozstrzygalność nie zamknęła teorii równań diofantycznych

Negatywne rozwiązanie dziesiątego problemu Hilberta nie oznacza, że matematycy przestali rozwiązywać konkretne równania diofantyczne. Wiele rodzin ma wyspecjalizowane metody, a dla pojedynczych równań można prowadzić bardzo głęboką analizę. Bariera dotyczy jednego uniwersalnego algorytmu obejmującego wszystkie wielomiany o całkowitych współczynnikach. To rozróżnienie powtarza się w całej teorii obliczalności: brak procedury dla pełnej klasy nie usuwa ogromnej liczby rozstrzygalnych podklas.

#Hilbert#Matiyasevich#nierozstrzygalność#równania diofantyczne#teoria liczb
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki