關於丟番圖方程(Diophantine Equation)，勾股定理(Pythagorean Theorem)，費馬最後定理(Fermat's Last Theorem)，希爾伯特第十問題(Hilbert's Tenth Problem)， Entscheidungsproblem(decision problem in Germen)

丟番圖方程又叫不定方程，整數多項式方程，即形如a1x1^b1+a2x2^b2...+anxn^bn=c的方程。
其中ai,bi,c都是整數。如果找到其中一組整數解，則稱為有解。
丟番圖方程的例子有貝祖等式、勾股定理的整數解、四平方和定理和費馬最後定理等。

勾股定理很簡單，即為形如a^2+b^2=c^2的等式，滿足這樣的式子有無限個。

而費馬最後定理說明，對於形如a^n+b^n=c^n的方程，其中n>2，不存在非零(a=b=c=0)整數解。
"I have a truly marvelous proof of this proposition which this margin is too narrow to contain."
費馬最後定理于1994年被英國數學家Andrew Wiles解決。

Hilbert's Tenth Problem是這樣一個問題，即給出一個丟番圖方程，要求給出一個可行的方法，通過有限次運算可以判定該方程有無整數解。這裡的方法，實際就是我們現在 所說的算法！1970年被Yuri Matiyasevich 證明這個判定問題的不可解，并給出了定理。這個定理是：
所有遞歸可枚舉集都是丟番圖方程。

Entscheidungsproblem是hilbert于1928年提出的問題。要求給出一個算法，讀入一個形式語言的描述以及數學命題，並且輸出Y or N。因此，這個算法可以判定，如哥德巴赫猜想以及黎曼猜想是否正確的。Church與Turing分別獨立地給出了證明，說明它以及包括停機問題在內的一 系列問題是不可判定問題。