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.