Dziesiąty problem Hilberta

Dziesiąty problem Hilberta jest jednym z 23 matematycznych problemów przedstawionych przez Davida Hilberta w 1900 roku. Treść problemu można wyrazić w następujący sposób:

Podać efektywną skończoną procedurę algorytmiczną, która, przyjmując współczynniki równania diofantycznego, zwraca odpowiedź „tak” lub „nie” na pytanie, czy istnieje rozwiązanie tego równania w dziedzinie liczb całkowitych.

Na przykład równanie ${\displaystyle xy-5-(x+y)=0}$ ma rozwiązanie w dziedzinie liczb całkowitych, co można uzasadnić np. poprzez podanie przykładu takiego rozwiązania ${\displaystyle (x=3,\ y=4).}$ Natomiast równanie ${\displaystyle (6x-y^{3})^{2}+(4x+1-y)^{2}=0}$ nie ma takiego rozwiązania co pokazujemy w sposób następujący: Jedyna możliwość dopuszczająca istnienie rozwiązania powyższego równania to przypadek, gdy zarówno ${\displaystyle (6x-y^{3})=0,}$ jak i ${\displaystyle (4x+1-y)=0}$ jest spełnione (jedyny przypadek, gdy suma kwadratów jest równa zero, zachodzi wówczas, gdy składniki tej sumy są równe zero). Jednak jednoczesne spełnienie równania pierwszego i drugiego jest niemożliwe, ponieważ z pierwszego wynika, że y jest liczbą parzystą ${\displaystyle (6x=y^{3})}$ natomiast z drugiego, że y jest liczbą nieparzystą ${\displaystyle (4x+1=y).}$ Żadna liczba całkowita nie może być jednocześnie parzysta i nieparzysta, zatem powyższe równanie nie ma rozwiązanie w dziedzinie liczb całkowitych. Dziesiąty problem Hilberta jest żądaniem zredukowania takich rozumowań do skończonej, algorytmicznej procedury.

Ostatecznie dziesiąty problem Hilberta znalazł negatywne rozwiązanie, taka procedura w ogólnej postaci nie istnieje.

Historia

Dziesiąty problem Hilberta ma duże znaczenie historyczne, ponieważ próby jego rozwiązania doprowadziły do znacznego rozwoju ścisłej notacji „obliczalności”. W latach trzydziestych trzej matematycy Kurt Gödel, Alan Turing i Alonzo Church zaproponowali niezależnie trzy precyzyjne definicje obliczalności, które okazały się równoważne. Od tego czasu dziesiąty problem Hilberta zaczęto precyzować jako pytanie o maszynę Turinga, która, działając na podaną listę współczynników równania diofantycznego, kończy pracę wtw., gdy równanie o takich współczynnikach nie posiada rozwiązania w dziedzinie liczb całkowitych.

Pierwsze poważne próby rozwiązania dziesiątego problemu Hilberta zostały poczynione przez Martina Davisa w 1950 roku. Próbowano wykazać, że dla każdego rekurencyjnie przeliczalnego zbioru ${\displaystyle S}$ istnieje odpowiadający mu wielomian ${\displaystyle P_{S}(k,y_{1},...,y_{n})}$ z całkowitymi współczynnikami, taki że równanie diofantyczne ${\displaystyle P_{S}(k,y_{1},...,y_{n})=0}$ ma rozwiązanie wtw., gdy ${\displaystyle k}$ należy do ${\displaystyle S}$ (a więc mówiąc krócej, że każdy rekurencyjnie przeliczalny zbiór ${\displaystyle S}$ jest zbiorem diofantycznym). Możemy zauważyć, że istnienie algorytmicznej procedury ${\displaystyle H}$ determinującej postać wielomianu ${\displaystyle P_{S}}$ dla określonego zbioru ${\displaystyle S}$ jest sprzeczne z pozytywnym rozstrzygnięciem problemu Hilberta. Załóżmy, że algorytm ${\displaystyle H}$ istnieje i niech ${\displaystyle S}$ będzie rekurencyjnie przeliczalnym zbiorem liczb całkowitych, który nie jest zbiorem rekurencyjnym. Wtedy (wbrew nierekurencyjności zbioru ${\displaystyle S}$) można by w skończonej liczbie kroków ustalić przynależność dowolnej liczby całkowitej ${\displaystyle k}$ do zbioru ${\displaystyle S}$ najpierw stosując algorytm ${\displaystyle H}$ w celu ustalenia postaci ${\displaystyle P_{S},}$ a następnie pytając algorytm Hilberta, czy ${\displaystyle P_{S}(k,y_{1},...,y_{n})=0}$ ma rozwiązanie. Zatem istnienie algorytmu Hilberta determinującego rozwiązywalność wszystkich równań diofantycznych sprowadzałoby się do sprzeczności.

Z powyższego powodu wysiłki matematyków skupiły się na próbach wykazania, że dowolnemu rekurencyjnie przeliczalnemu zbiorowi ${\displaystyle S}$ odpowiada wielomian ${\displaystyle P_{S}.}$ W tym samym czasie Julia Robinson, nieświadoma prac Davisa, starając się dowieść, że zbiór tych trójek uporządkowanych ${\displaystyle (a,b,c)}$ dla których spełnione jest ${\displaystyle a=b^{c}}$ (tzw. EXP) jest zbiorem diofantycznym, postawiła pomocniczą hipotezę (nazywaną dalej J.R) w następującej postaci:

Istnieje taki diofantyczny zbiór par ${\displaystyle (a,b)}$ który nazywamy ${\displaystyle D}$ że ${\displaystyle (a,b)\in D\Rightarrow b<a^{a}}$ i dla każdego dodatniego ${\displaystyle k,}$ istnieje para ${\displaystyle (a,b)\in D}$ taka że ${\displaystyle b>a^{k}}$

Następnie dowiodła, że J.R implikuje, że zbiór EXP jest zbiorem diofantycznym.

Pomimo że hipoteza J.R pozostała nieudowodniona aż do ostatecznego rozwiązania problemu Hilberta 20 lat później, odegrała kluczową rolę w próbach znalezienia dowodu. W 1959 roku Martin Davis i Hilary Putnam (pod wpływem prac Robinson) pokazali, że hipoteza J.R implikuje, że każdy rekurencyjnie przeliczalny zbiór ${\displaystyle S}$ jest zbiorem diofantycznym (a więc w połączeniu z dowodami Davisa udowodnienie hipotezy J.R oznaczałoby rozwiązanie dziesiątego problemu Hilberta). Udowodniono także, że hipoteza J.R jest prawdziwa wtw., gdy zbiór liczb pierwszych jest zbiorem diofantycznym.

W 1970 roku Rosjanin Jurij Matijasiewicz pokazał, że zbiór ${\displaystyle P=\{(a,b)|a>0,b=F_{2a}\},}$ gdzie ${\displaystyle F_{n}}$ jest n-tą liczbą Fibonacciego, spełnia warunki zbioru D z hipotezy J.R tym samym dopełniając dowód, na który trzech amerykańskich matematyków pracowało przez dwadzieścia lat.

Związek z problemem stopu

Zauważmy, że gdyby problem stopu był algorytmicznie rozstrzygalny, to również dziesiąty problem Hiberta miałby pozytywne rozwiązanie. Dowód nierozwiązywalności danego równania diofantycznego jest jednocześnie dowodem, że maszyna Turinga poszukująca kontrprzykładu do tezy o nierozwiązywalności danego równania nie zakończy pracy. Z uwagi na to, że iloczyn kartezjański zbiorów liczb całkowitych jest nadal przeliczalny, tyczy się to każdego równania diofantycznego ze skończoną liczbą współczynników (iterowanie po zbiorze wszystkich możliwych konfiguracji współczynników możemy interpretować jako iterowanie po zbiorze liczb całkowitych).

Zachodzi również zależność odwrotna. Znając odpowiedź na pytanie o rozwiązywalność dowolnego równania diofantycznego można uzyskać odpowiedź na pytanie o własność stopu dowolnej maszyny Turinga. Wykazanie tego faktu jest trudne i było zasadniczą częścią dowodu równoważności dziesiątego problemu Hilberta i problemu stopu.

Warto zauważyć, że jeśli dane równanie diofantyczne ma rozwiązanie i co równoważne odpowiadająca mu maszyna Turinga kończy pracę, to fakt ten zawsze można stwierdzić algorytmicznie, np. poprzez jawne pokazanie skończonej listy kroków, w której dana maszyna osiąga instrukcje stop. Jeśli jednak odpowiedź brzmi „nie”, to nie można tego stwierdzić w oparciu o jakikolwiek skończony zbiór reguł, który da się zredukować do postaci maszyny Turinga. Można podać różne zbiory reguł pozwalające w niektórych przypadkach dowieść, że rozwiązanie nie istnieje (jak np. pokazany wyżej dowód opierający się na parzystości zmiennych), ale taki zbiór nigdy nie będzie wystarczający do uwzględnienia wszystkich przypadków równań, które nie posiadają rozwiązania w dziedzinie liczb całkowitych. Co więcej fakt, że dana maszyna Turinga jest skuteczna w odniesieniu do pewnego podzbioru równań, pociąga prawdziwość nowego twierdzenia o nierozwiązywalności innego równania, którego jednak już ta maszyna nie rozstrzyga. To pokazuje, że dowolna możliwa do dokonania systematyzacja rozwiązań w oparciu o maszynę Turinga nie wyczerpuje wszystkiego, co wiemy dzięki zrozumieniu problemu.

Rozwiązanie

Dziesiąty problem Hilberta znalazł negatywne rozwiązanie w 1970 roku ostatecznie za sprawą rosyjskiego matematyka Jurija Matijasiewicza. Ogólnie dowód sprowadza się do pokazania, w jaki sposób działanie dowolnej maszyny Turinga można zakodować w postaci układu równań diofantycznych. To pozwala na sprowadzenie pytania o własność stopu dowolnej maszyny Turinga do pytania o rozwiązywalność pewnego równania diofantycznego. Należy podkreślić, że negatywne rozwiązanie dziesiątego problemu Hilberta nie oznacza, że istnieją problemy dotyczące rozwiązywalności równań diofantycznych, które są matematycznie nierozstrzygalne. Pytanie o istnienie takich problemów pozostaje otwarte.

Zobacz też

• problem stopu
• równanie diofantyczne

Bibliografia

• Yuri Matiyasevich, M. Davis, H. Putnam: Hilbert’s 10th Problem (Foundations of Computing). The MIT Press, 1993. ISBN 978-0262132954.
• Devlin Keith: Mathematics: the New Golden Age. London: Penguin Books, 1988. ISBN 978-0231116398.