¿­ÐýÃŹÙÍø

Course Description

Summary

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. Topics include: computation, computability, formal logic, philosophy, infinity, Turing Machines