Course Outline

Description

This is not your typical class in computer science, or in formal logic; but you will learn a lot about both by taking it. Our subject will be one of the most important and influential papers that has ever been written—“On Computable Numbers, with an Application to the Entscheidungsproblem,” by Alan Turing. This is the paper that birthed computer science as a discipline. Understanding it requires that you be comfortable with some mathematical concepts (powers and roots) and with thinking abstractly; but the most important prerequisite for understanding this paper is determination.

Turing’s 1936 paper proves something very interesting. We usually believe we have made progress in solving a mathematical problem when we come up with a general procedure. When you were young, you learned a procedure to subtract one number from another. Later, you learned a procedure to solve for the unknown in a quadratic equation. What Turing shows is that there is a large class of mathematical problems that cannot be solved procedurally. By this, we mean not merely that we do not know what the procedure is, but that no procedure will ever be found!

This is a shocking result! How can we know that no procedure will ever be found? Could it not be that we simply have yet to stumble on the right procedure to solve the problem? No, says Turing! In fact, he proves it, and his mind-bending proof is the centerpiece of our course. His proof lies at the center of three disciplines that have profoundly shaped the modern world: formal logic, foundations of mathematics, and theoretical computer science. Each of these disciplines looks back to Turing’s paper as a flashpoint, a moment which defined how each understands reality. What is the best way to characterize Turing’s paper? Simple. It changed the world.

Learning Outcomes

1. Understand and articulate Turing’s proof of uncomputability, together with its implications.
2. Engage with complex logical and computational concepts, and enhance the ability to think abstractly.
3. Explore the intersection of formal logic, mathematics, and theoretical computer science, and understand how Turing shaped these disciplines.
4. Gain a critical appreciation for the historical and philosophical impact of Turing’s paper, as well as its influence on theory of computation.
5. Cultivate the ability to read, analyze, and interpret a foundational text computer science.

Topics include: computation, computability, formal logic, philosophy, infinity, Turing Machines