Alan Turing: Algorithms, Computation, Machines
What is computation? What is an algorithm? In 1936, a 24-year old graduate student named Alan Turing published a paper titled “On Computable Numbers, with an Application to the Entscheidungsproblem,” in which he defined certain “logical computing machines” that came to be known as Turing machines. These were not machines in the physical sense, but rather a mathematical definition of algorithmic computation. The paper marked the origin of computer science, i.e., a theory of computation, and Turing machines became the standard model for understanding computation, a key foundation for the first physical computers, and central to subsequent discussions in philosophy of mind and cognitive science (e.g., the computational theory of mind). However, Turing also used his definition of computing machines to showcase the limits of computation: that there are problems that cannot be solved by any algorithm. How can we engage Turing and the foundations of computability in the context of the increasingly algorithmic society we inhabit?
In this course, we will explore the concepts and impact of Turing’s 1936 paper, focusing primarily on “Turing machines.” Students will explore the intellectual context for Turing’s breakthrough in debates regarding the foundations of mathematics, particularly in the work of David Hilbert and Kurt Gödel. We will also study the definition of a Turing machine, and discuss evidence for the Church-Turing thesis. Do Turing machines completely capture the intuitive concept of computability? What is Turing’s legacy today? Alongside Turing’s original paper, readings will include selections from Chris Bernhardt’s Turing’s Vision: The Birth of Computer Science, Charles Petzold’s The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine, and portions of Andrew Hodges’s definitive biography, Alan Turing: The Enigma.
Course ScheduleThursday, 6:30-9:30pm
April 06 — May 04, 2017
4 sessions over 5 weeks
Class will not meet on April 13