SOME HISTORICAL NOTES From: Stephen Wolfram, A New Kind of Science Notes for Chapter 12: The Principle of Computational Equivalence Section: Implications for Mathematics and Its Foundations Page 1161 Hilbert's tenth problem. Beginning in antiquity various procedures were developed for solving particular kinds of Diophantine equations (see page 1171). In 1900, as one of his list of 23 important mathematical problems, David Hilbert posed the problem of finding a single finite procedure that could systematically determine whether a solution exists to any specified Diophantine equation. The original proof of Gödel’s Theorem from 1931 in effect involves showing that certain logical and other operations can be represented by Diophantine equations - and in the end Gödel’s Theorem can be viewed as saying that certain statements about Diophantine equations are unprovable. The notion that there might be universal Diophantine equations for which Hilbert’s Tenth Problem would be fundamentally unsolvable emerged in work by Martin Davis in 1953. And by 1961 Davis, Hilary Putnam and Julia Robinson had established that there are exponential Diophantine equations that are universal. Extending this to show that Hilbert’s original problem about ordinary polynomial Diophantine equations is unsolvable required proving that exponentiation can be represented by a Diophantine equation, and this was finally done by Yuri Matiyasevich in 1969 (see note above). By the mid-1970s, Matiyasevich had given a construction for a universal Diophantine equation with 9 variables - though with a degree of about 10^45. It had been known since the 1930s that any Diophantine equation can be reduced to one with degree 4 - and in 1980 James Jones showed that a universal Diophantine equation with degree 4 could be constructed with 58 variables. In 1979 Matiyasevich also showed that universality could be achieved with an exponential Diophantine equation with many terms, but with only 3 variables. As discussed in the main text I believe that vastly simpler Diophantine equations can also be universal. It is even conceivable that a Diophantine equation with 2 variables could be universal: with one variable essentially being used to represent the program and input, and the other the execution history of the program - with no finite solution existing if the program does not halt. Stephen Wolfram, A New Kind of Science (Wolfram Media, 2002), page 1161. © 2002, Stephen Wolfram, LLC