History
| Year | Events |
|---|---|
| 1944 | Emil Leon Post declares that Hilbert's tenth problem "begs for an unsolvability proof". |
| 1949 | Martin Davis uses Kurt Gödel's method for applying the Chinese Remainder Theorem as a coding trick to obtain his normal form for recursively enumerable sets:
where is a polynomial with integer coefficients. Purely formally, it is only the bounded universal quantifier that stands in the way of this being a Diophantine definition. Using a non-constructive but easy proof, he notes that there is a Diophantine set whose complement is not Diophantine. Because the recursively enumerable sets also are not closed under complementation, he conjectures that the two classes are identical. |
| 1950 | Julia Robinson, unaware of Davis's work, but grasping the key importance of the exponential function, attempts to prove that EXP, the set of triplets
is Diophantine. Not succeeding, she is led to her hypothesis (later called J.R.): There is a Diophantine set of pairs such that but for every ,
Using properties of the Pell equation, she proves that J.R. implies that EXP is Diophantine. Finally she shows, that if EXP is Diophantine so are the binomial coefficients, the factorial, and the primes. |
| 1959 | Working together, Davis and Putnam study exponential Diophantine sets: sets definable by Diophantine equations in which some of the exponents may be unknowns. Using the Davis normal form together with Robinson's methods, but assuming the then unproved conjecture that there are arbitrarily long arithmetic progressions consisting of prime numbers, they prove that every recursively enumerable set is exponential Diophantine, and as a consequence, that J.R. implies that every recursively enumerable set is Diophantine, and that Hilbert's tenth problem is unsolvable. |
| 1960 | Robinson shows how to avoid the unproved conjecture about primes in arithmetic progression and then greatly simplifies the proof. J.R. is revealed as the key to further progress, though many doubt that it is true. |
| 1961–1969 | Davis and Putnam find various propositions that imply J.R. Yuri Matiyasevich publishes some reductions of Hilbert's tenth problem. Robinson shows that the existence of an infinite Diophantine set of primes would suffice to establish J.R. |
| 1970 | Matiyasevich exhibits a system of 10 simultaneous first and second degree equations which provide a Diophantine definition of the set of pairs such that
This proves J.R. and thus completes the proof that all recursively enumerable sets are Diophantine, and that therefore Hilbert's tenth problem is unsolvable. |
Read more about this topic: Hilbert's Tenth Problem
Famous quotes containing the word history:
“Postmodernism is, almost by definition, a transitional cusp of social, cultural, economic and ideological history when modernism’s high-minded principles and preoccupations have ceased to function, but before they have been replaced with a totally new system of values. It represents a moment of suspension before the batteries are recharged for the new millennium, an acknowledgment that preceding the future is a strange and hybrid interregnum that might be called the last gasp of the past.”
—Gilbert Adair, British author, critic. Sunday Times: Books (London, April 21, 1991)
“the future is simply nothing at all. Nothing has happened to the present by becoming past except that fresh slices of existence have been added to the total history of the world. The past is thus as real as the present.”
—Charlie Dunbar Broad (1887–1971)
“Don’t you realize that this is a new empire? Why, folks, there’s never been anything like this since creation. Creation, huh, that took six days, this was done in one. History made in an hour. Why it’s a miracle out of the Old Testament!”
—Howard Estabrook (1884–1978)