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
Bibliografia
Kategoria:Teoria obliczeń Kategoria:Teoria liczb Kategoria:Problemy Hilberta Kategoria:Równania diofantyczne