School navigation

Mathematical Sciences

Revisiting Turing’s Computable Numbers, in Python

Date: 3:30pm - 4:30pm PDT March 17, 2016 Location: John Howard 254

John Howard 254

Dr. Adam A. Smith

Lewis & Clark Class of 1999

Assistant Professor of Computer Science

University of Puget Sound


Alan Turing’s seminal 1936 paper “On computable numbers, with an application to the Entscheidungsproblem” kickstarted the entire field of computer science. Turing attempted to formalize the process of problem solving, by imagining theoretical automatons that worked through a problem in a precise, mechanical way.

Today, we recognize these “Turing machines” as the forerunners of modern digital computers.

In his paper, Turing defined computable numbers as the set of numbers that can be calculated to an arbitrary precision in a finite amount of time. Surprisingly, this set of numbers is countably infinite, naturally extending the work of Georg Cantor.

Professor Smith will repeat Turing’s proofs, though using Python to make them more approachable to a modern audience.

He is not going to assume that you have any specific, previous math or computer science knowledge, so come hear about this fascinating bit of history.  However, he will get into a little number theory that might be better understood by sophomore level students or above.