Hilbert’s tenth problem asks whether there is an algorithm that given a polynomial with integer coefficients (in an arbitrary number of variables) determines whether it has integer roots. A celebrated theorem of Davis, Matiyasevich, Putnam and Robinson shows that this is not the case. Their result shows that the class of Diophantine sets coincides with the a priori larger class of r.e. (or 
We proved this result under the assumption that exponentiation is Diophantine. This is the key result, and will be dealt with in the following lecture.
A kind of library 