In the late sixties Matiyasevich, building on the work of Davis, Putnam and Robinson, showed that there was no algorithm to determine whether a polynomial equation in several variables and with integer coefficients has integer solutions. Hilbert gave...