Matiyasevich's theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations (polynomials with integer coefficients) has a solution among the integers. David Hilbert posed the problem in his 1900 address to the International Congress of Mathematicians. 1970 was a common year starting on Thursday. ... Hilberts problems are a list of 23 problems in mathematics put forth by German mathematician David Hilbert in the Paris conference of the International Congress of Mathematicians in 1900. ... Flowcharts are often used to represent algorithms. ... In mathematics, a Diophantine equation is a polynomial equation that only allows the variables to be integers. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... David Hilbert David Hilbert (January 23, 1862 – February 14, 1943) was a German mathematician born in Wehlau, near Königsberg, Prussia (now Znamensk, near Kaliningrad, Russia) who is recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ...

A typical system of diophantine equations looks like this:

3x²y − 7y²z³ = 18

− 7y² + 8z² = 0

The question is whether there exist integers x, y and z which satisfy both equations simultaneously. It turns out that it is always equivalent to ask whether a single Diophantine equation with several variables has any solutions among the natural numbers. For instance, the above system is solvable over the integers if and only if the following equation is solvable over the natural numbers: Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...

( 3(x₁ − x₂)²(y₁ − y₂) − 7(y₁ − y₂)²(z₁ − z₂)³ − 18 )² + ( −7(y₁ − y₂)² + 8(z₁ − z₂)²)² = 0.

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. In mathematics, the Fibonacci numbers form a sequence defined recursively by: In other words: one starts with 0 and 1, and then produces the next Fibonacci number by adding the two previous Fibonacci numbers. ... In mathematics, a quantity that grows exponentially is one that grows at a rate proportional to its size. ... Julia Hall Bowman Robinson (December 8, 1919 - July 30, 1985) was an American mathematician, born in Saint Louis, Missouri. ... Martin Davis, (born 1926, New York City) is an American mathematician, known for his work on Hilberts tenth problem. ... Hilary Whitehall Putnam (born July 31, 1926) is a key figure in the philosophy of mind during the 20th century. ...

Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992). Zhi-Wei Sun (孙智伟, b. ...

Matiyasevich's theorem itself is much stronger than the unsolvability of the Tenth Problem. It says:

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₁, ..., x_k) such that an integer n is in S if and only if there exist some integers x₁, ..., x_k such that f(n, x₁, ..., x_k) = 0. In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if it... In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ...

It is not hard to see that every Diophantine set is recursively enumerable: consider a Diophantine equation f(n, x₁, ..., x_k) = 0. Now we make an algorithm which simply tries all possible values for n, x₁, ..., x_k and prints n every time f(n, x₁, ..., x_k) = 0. This algorithm will obviously run forever and will list exactly the n for which f(n, x₁, ..., x_k) = 0 has a solution in x₁, ..., x_k.

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 non-recursive. 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 yes-or-no answer to the question of whether n is a member of S. It follows that there are Diophantine equations which cannot be solved by any algorithm, unless one can construct a hypercomputer (Kieu, 2003); however, this is generally held physically implausible. Hypercomputation refers to methods for the computation of non-computable functions. ...

(It is amusing to observe that that is one of the very few places in modern mathematics where an argument taking exactly the form of an Aristotelian syllogism is of great interest, and not dismissed as trivial: In traditional logic, a syllogism is an inference in which one proposition (the conclusion) follows of necessity from two others (known as premises). ...

(Major premise): All recursively enumerable sets are Diophantine.

(Minor premise): Some recursively enumerable sets are non-recursive.

(Conclusion): Therefore some Diophantine sets are non-recursive.

The conclusion of this syllogism 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. For other uses of the term calculus see calculus (disambiguation) Calculus is a central branch of mathematics, developed from algebra and geometry, and built on two major complementary ideas. ... In mathematics, a differential equation is an equation in which the derivatives of a function appear as variables. ...

One can also derive the following stronger form of Gödel's incompleteness theorem from Matiyasevich's result: In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...

Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.

References

• Y. Matiyasevich. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. English translation in Soviet Mathematics. Doklady, vol. 11, no. 2, 1970.
• M. Davis. "Hilbert's Tenth Problem is Unsolvable." American Mathematical Monthly 80, pp. 233-269, 1973.
• T. Kieu. "Quantum Algorithm for the Hilbert's Tenth Problem", Int. J. Theor. Phys. 42, pp. 1461-1478, 2003. e-print archive quant-ph/0110136 (PDF)