Computability Learning Seminar

Luke MacLean, Department of Pure Mathematics, University of Waterloo

"A proof sketch of Hilbert's tenth problem"

In 1900 David Hilbert presented his list of 23 influential problems in mathematics. The tenth problem asks if there is a general algorithm that, given a Diophantine equation, can decide whether there is a solution in the integers. Partial work was done by Davis, Putnam, and Robinson over 20 years, and the final negative answer was given in 1970 by Matiyasevich. The problem of solving Diophantine equations is unquestionably one of algebraic number theory, but the proof of this theorem shows an unlikely connection with computability theory.

I will give as thorough a proof of this result as 80 minutes allows, though it is incredibly technical, so some pieces must be omitted. No knowledge of computability theory is required, but a general idea of Turing machines would be helpful.

MC 5417