10. problem Hilberta i równanie diofantyczne Chaitina „Komputer”?

W Chaimin's Meta Math! W Quest For Omega krótko mówi o 10. problemie Hilberta. Następnie mówi, że dowolne równanie diofantyczne można zmienić na dwa równe wielomiany o dodatnich współczynnikach całkowitych: .p = $p=0$$p=0 \iff p_1 = p_2$

Następnie mówi, że możemy myśleć o tych równaniach jak o „komputerze”:

Komputer z równaniem diofantycznym :

$$L(k,n,x,y,z,...)=R(k,n,x,y,z,...)$$ Program: $k$ , Wyjście: $n$ , Czas: $x,y,z,...$

Z lewej strony $L$ , z prawej strony $R$ . Mówi, że $k$ jest programem tego komputera, który wypisuje $n$ . Mówi także, że niewiadome są wielowymiarową zmienną czasową .

Tym, co mnie dezorientuje, jest to, że następnie mówi, że 10. Problem Hilberta nie jest wyraźnie do rozwiązania, gdy patrzymy w ten sposób. Mówi w zasadzie „z powodu problemu zatrzymania Turinga”. Ale nie widzę związku (dopiero zaczynam uczyć się teorii). Miałem nadzieję, że ktoś może lepiej wyjaśnić, o co tu chodzi.

Wiem, że problem zatrzymania Turinga zasadniczo mówi, że nie można przewidzieć, kiedy program się zatrzyma, zanim się zatrzyma (biorąc pod uwagę określony czas). Jakie zastosowanie ma 10. problem Hilberta z wykorzystaniem notacji przedstawionej przez Chaitina?

Dobre pytanie. Wygląda na to, że możesz potrzebować dodatkowej wiedzy na temat 10. problemu Hilberta. Mam nadzieję, że to nie jest przesada.

Problem dotyczy:

Czy istnieje algorytm, który biorąc pod uwagę wielomian diofantyczny, decyduje, czy istnieje ustawienie jego zmiennych, które czynią go równym ?$0$

Zostało to rozwiązane w latach 70. jako konsekwencja MRDP (zwanego także twierdzeniem Matijasewicza, jeśli masz ochotę je przeszukać), który stwierdza:

Zdefiniuj: zestaw to Diofantyna, jeśli istnieje wielomian Diofantyny na wejściach tak że . p k + 1 D = { $D \subset \mathbb{N}$$p$$k+1$$D = \{ x \, | \, \exists y \in \mathbb{R}_+^k \, p(x, y) = 0\}$

Zestawy diofantyczne są dokładnie tymi, które są rozpoznawalne przez maszyny Turinga.

Twierdzenie to jest oczywiste w jednym kierunku (każdy zestaw Diofantyny jest rozpoznawany przez maszynę Turinga - na wejściu po prostu poproś maszynę o rozpoczęcie zgadywania wektorów , oceń i zatrzymaj się, jeśli / kiedy okaże się, że ). Z drugiej strony jest to bardzo nieoczywiste - dlaczego prawdą jest, że każdy rozpoznawalny zestaw Turinga to Diofantyna? Schematy kodowania są obrzydliwe, ale zaufaj mi, można to zrobić.y ∈ R k + p ( x , y ) p ( x , y ) $x$$y \in \mathbb{R}_+^k$$p(x, y)$$p(x, y) = 0$

W każdym razie, w jaki sposób twierdzenie MRDP rozwiązuje 10. problem Hilberta? Dobrze...

Dla sprzeczności udajmy, że mamy algorytm, który, biorąc pod uwagę wielomian diofantyczny , decyduje, czy istnieje wektor wejściowy który powoduje .y p ( $p(y)$$y$$p(y) = 0$

Teraz użyję tego magicznego algorytmu do rozwiązania problemu zatrzymania. Biorąc pod uwagę maszynę, użyję obrzydliwego kodowania równań diofantycznych do przekształcenia problemu „Czy zatrzymuje się na wejściu ?” w problem „Czy wielomian diofantyczny ma zestaw danych wejściowych, które czynią go równym ?” Następnie użyję mojego magicznego algorytmu, aby rozwiązać ten problem, a teraz rozwiązałem problem zatrzymania.x p ( y | x $M$$x$$p(y | x)$$0$

Oczywiście jest to niemożliwe, więc w rzeczywistości nie może istnieć magiczny algorytm, który szuka wektora wejściowego, który powoduje . Podobnie nie może istnieć algorytm, który analizuje dwa wielomiany diofantyczne i decyduje, czy kiedykolwiek będą one równe. Tak mówi Chaitin.$p(y) = 0$