Redirected from Matiyasevichs theorem
A typical system of diophantine equations looks like this:
Matiyasevich utilized an ingenious trick involving Fibonacci numbers in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by Julia Robinson, Martin Davis and Hilary Putnam had shown that this suffices to show that no general algorithm deciding the solvability of Diophantine equations can exist.
Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the number of variables is only 6.
Matiyasevich's theorem itself is somewhat more general than the unsolvability of the Tenth Problem; it can be stated as "Every recursively enumerable set is Diophantine". A set S of integers is recursively enumerable precisely 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,x_{1},...,x_{k}) such that an integer n is in S if and only if there exist some integers x_{1},...,x_{k} such that f(n,x_{1},...,x_{k})=0. The conjunction of Matiyasevich's theorem with a result discovered in the 1930s implies that a solution to Hilbert's tenth problem is impossible. The result discovered in the 1930s by several logicians can be stated by saying that some recursively enumerable sets are nonrecursive. In this context, a set S of integers is called "recursive" if there is an algorithm that, when given as input an integer n, returns as output a correct yesorno answer to the question of whether n is a member of S.
(It is amusing to observe that one of the very few places in modern mathematics where an argument that takes exactly the form of an oldfashioned Aristotelian syllogism is of great interest and is not contemptuously dismissed as uninteresting because trivial. That argument is as follows. Major premise: All recursively enumerable sets are Diophantine. Minor premise: Some recursively enumerable sets are nonrecursive. Conclusion: Some Diophantine sets are nonrecursive. The conclusion of this syllogism is what entails that Hilbert's 10th problem cannot be solved.)
Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.
One can also derive the following stronger form of Gödel's incompleteness theorem from Matiyasevich's result:
Search Encyclopedia

Featured Article
