Matiyasevich's Theorem
Matiyasevich's theorem says:
- Every computably enumerable set is Diophantine.
A set S of integers is computably enumerable if there is an algorithm that behaves as follows: When given as input an integer n, if n is a member of S, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of S. A set S is Diophantine precisely if there is some polynomial with integer coefficients f(n, x1, ..., xk) such that an integer n is in S if and only if there exist some integers x1, ..., xk such that f(n, x1, ..., xk) = 0.
It is not hard to see that every Diophantine set is recursively enumerable: consider a Diophantine equation f(n, x1, ..., xk) = 0. Now we make an algorithm which simply tries all possible values for n, x1, ..., xk, in the increasing order of the sum of their absolute values, and prints n every time f(n, x1, ..., xk) = 0. This algorithm will obviously run forever and will list exactly the n for which f(n, x1, ..., xk) = 0 has a solution in x1, ..., xk.
Read more about this topic: Diophantine Set
Famous quotes containing the word theorem:
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)