Editing Hilbert's tenth problem (section)

==History==
{| class="wikitable"
! 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:
:<math> \left \{a \mid \exists y \, \forall k \leqslant y \, \exists x_1,\ldots , x_n : p \left (a,k,y,x_1,\ldots ,x_n \right )=0 \right \}</math>
where <math>p</math> is a polynomial with integer coefficients. Purely formally, it is only the bounded universal quantifier that stands in the way of this being a definition of a Diophantine set.

Using a non-constructive but easy proof, he derives as a corollary to this normal form that the set of Diophantine sets is not closed under complementation, by showing that there exists 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, investigates the connection of the exponential function to the problem, and attempts to prove that EXP, the set of triplets <math>(a,b,c)</math> for which <math>a=b^c</math>, is Diophantine. Not succeeding, she makes the following ''hypothesis'' (later called J.R.):<br />
:''There is a Diophantine set'' <math>D</math> ''of pairs'' <math>(a,b)</math> ''such that'' <math>(a,b)\in D \Rightarrow b < a^a</math> ''and for every positive'' <math>k,</math> there exists <math>(a,b)\in D</math> ''such that'' <math>b>a^k.</math>
Using properties of the Pell equation, she proves that J.R. implies that EXP is Diophantine, as well as 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, and assuming the then unproved conjecture that ''[[Green–Tao theorem|there are arbitrarily long arithmetic progressions consisting of prime numbers]]'', they prove that every recursively enumerable set is exponential Diophantine. They also prove as a corollary that J.R. implies that every recursively enumerable set is Diophantine, which in turn implies that Hilbert's tenth problem is unsolvable.
|-
|1960
|Robinson simplifies the proof of the [[conditional proof|conditional result]] for exponential Diophantine sets and makes it independent from the conjecture about primes and thus a formal theorem. This makes the J.R. hypothesis a sufficient condition for the unsolvability of Hilbert's tenth problem. However, many doubt that J.R. is true.{{efn|A review of the joint publication by Davis, Putnam, and Robinson in [[Mathematical Reviews]] ({{MathSciNet|id=0133227}}) conjectured, in effect, that J.R. was false.}}
|-
|1961–1969
|During this period, Davis and Putnam find various propositions that imply J.R., and Robinson, having previously shown that J.R. implies that the set of primes is a Diophantine set, proves that this is an [[if and only if]] condition. [[Yuri Matiyasevich]] publishes some reductions of Hilbert's tenth problem. 
|-
|1970
|Drawing from the recently published work of [[Nikolai Nikolayevich Vorobyov (mathematician)|Nikolai Vorob'ev]] on Fibonacci numbers,<ref>{{cite journal|title=My Collaboration with Julia Robinson|first=Yuri|last=Matiyasevich|journal=[[The Mathematical Intelligencer]]|volume=14|issue=4|year=1992|pages=38–45|url=http://logic.pdmi.ras.ru/~yumat/Julia/|doi=10.1007/bf03024472|s2cid=123582378 }}</ref> [[Yuri Matiyasevich|Matiyasevich]] proves that the set <math>P =\{(a,b) \mid a >0, b = F_{2a} \},</math> where <math>F_n</math> is the ''n''<sup>th</sup> [[Fibonacci number]], is Diophantine and exhibits exponential growth.<ref>{{cite book|title=Mathematical Logic in the 20th century|first=Gerald E.|last=Sacks|publisher=World Scientific|year=2003|pages=269–273}}</ref> This proves the J.R. hypothesis, which by then had been an open question for 20 years. Combining J.R. with the theorem that every recursively enumerable set is exponential Diophantine, proves that recursively enumerable sets are Diophantine. This makes Hilbert's tenth problem unsolvable.
|}