Editing Hilbert's tenth problem (section)

{{Short description|On solvability of Diophantine equations}}
'''Hilbert's tenth problem''' is the tenth on the [[Hilbert's problems|list of mathematical problems]] that the German mathematician [[David Hilbert]] posed in 1900.  It is the challenge to provide a general [[algorithm]] that, for any given [[Diophantine equation]] (a [[polynomial]] equation with [[integer]] coefficients and a finite number of unknowns), can decide whether the equation has a solution with all unknowns taking integer values.

For example, the Diophantine equation <math>3x^2-2xy-y^2z-7=0</math> has an integer solution: <math>x=1,\ y=2,\ z=-2</math>. By contrast, the Diophantine equation <math>x^2+y^2+1=0</math> has no such solution.

Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist. This is the result of combined work of [[Martin Davis (mathematician)|Martin Davis]], [[Yuri Matiyasevich]], [[Hilary Putnam]] and [[Julia Robinson]] that spans 21 years, with Matiyasevich completing the theorem in 1970.<ref>{{cite journal|journal=Doklady Akademii Nauk SSSR |language=Russian |title=The diophantineness of enumerable sets |first=Yu. V. |last=Matiyasevich |volume=191 |year=1970 |page=279-282 |url=http://mi.mathnet.ru/dan35274}}</ref><ref>{{cite book|first=S. Barry |last=Cooper |author-link=S. Barry Cooper |title=Computability theory |date=17 November 2003 |publisher=Chapman & Hall/CRC mathematics |page=98 |isbn=9781584882374 |oclc=909209807}}</ref>{{sfn|Matiyasevich|1993}} The theorem is now known as [[Matiyasevich's theorem]] or the MRDP theorem (an initialism for the surnames of the four principal contributors to its solution).

When all coefficients and variables are restricted to be ''positive'' integers, the related problem of [[polynomial identity testing]] becomes a decidable (exponentiation-free) variation of [[Tarski's high school algebra problem]], sometimes denoted <math>\overline{HSI}.</math><ref name="BurrisLee">Stanley Burris, Simon Lee, ''Tarski's high school identities'', [[American Mathematical Monthly]], '''100''', (1993), no.3, pp.&nbsp;231&ndash;236.</ref>