Lesson 5

A more complex example is the negative answer to Hilbert's tenth problem: is the language of polynomials in several variables that have a zero in some integer point decidable? David Hilbert formulated it (as part of twenty-three problems) in 1900.

It is easy to see that this language is enumerable: the proof of membership is a point where the polynomial vanishes. In 1970, Yuri Vladimirovich Matiyasevich, building on the results of Martin Davis, Hilary Putnam, and Julia Robinson, proved that this language is undecidable. The proof of this remarkable fact, known as the DPRM theorem, is beyond the scope of this course.