The MRDP Theorem


Συγγραφέας: Peter Smith


Peter Smith: The MRDP Theorem (pdf, 265K)
Here is Hilbert is his famous address of 1900: The supply of problems in mathematics is inexhaustible, and as soon as one problem is solved numerous others come forth in its place. Permit me in the following, tentatively as it were, to mention particular definite problems, drawn from various branches of mathematics, from the discussion of which an advancement of science may be expected. He goes on to highlight no less than 23 problems. The first, of course, is Cantor’s problem of the cardinal number of the continuum. The tenth, not as profound but still of considerable interest to logicians, is this: Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. 1’ll explain what a diophantine equation is in just a moment: talk of a devising a process for determining something in a Hnite number of operations we’ll take as a request for an algorithm. Hilbert’s Tenth Problem took seventy years to resolve. Important work towards a solution was done by Julia Robinson and Martin Davis, with a contribution from Hilary Putnam. The final, and key, step however was made by a young Russian mathematician, Yuri Matiyasevich. Putting everything together, we get the MDRP theorem, settling the Tenth Problem in the negative: provably, there is no algorithmic way of determining whether some arbitrary diophantine equation has a solution. l’m not going to do say more than a sentence or two about the proof of the key step in establishing the MDRP theorem. My aim in this talk, rather, is to explain in broad terms what the result amounts to e and explain too why it is indeed of interest to logicians.