Editing Diophantine set (section)

==Matiyasevich's theorem==

Matiyasevich's theorem, also called the [[Yuri Matiyasevich|Matiyasevich]]–[[Julia Robinson|Robinson]]–[[Martin Davis (mathematician)|Davis]]–[[Hilary Putnam|Putnam]] or MRDP theorem, says:

:Every [[recursively enumerable set|computably enumerable set]] is Diophantine, and the converse.

A set ''S'' of integers is '''[[recursively enumerable|computably enumerable]]''' if there is an algorithm such that: For each integer input ''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''<sub>1</sub>, ..., ''x''<sub>''k''</sub>)
such that an integer ''n'' is in ''S'' if and only if there exist some integers
''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>
such that ''f''(''n'', ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>) = 0.

Conversely, every Diophantine set is [[recursively enumerable|computably enumerable]]:
consider a Diophantine equation ''f''(''n'', ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>) = 0.
Now we make an algorithm that simply tries all possible values for
''n'', ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub> (in, say, some simple order consistent with the increasing order of the sum of their absolute values),
and prints ''n'' every time ''f''(''n'', ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>) = 0.
This algorithm will obviously run forever and will list exactly the ''n''
for which ''f''(''n'', ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>) = 0 has a solution
in ''x''<sub>1</sub>, ..., ''x''<sub>''k''</sub>.

===Proof technique===

[[Yuri Matiyasevich]] utilized a method involving [[Fibonacci number]]s, which [[exponential growth|grow exponentially]], in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by [[Julia Robinson]], [[Martin Davis (mathematician)|Martin Davis]] and [[Hilary Putnam]] – hence, MRDP – had shown that this suffices to show that every [[recursively enumerable set|computably enumerable set]] is Diophantine.