In 1936, Alan Turing wrote a paper that invented computer science. Not a piece of computer science, not a contribution to it. The whole thing. On Computable Numbers, with an Application to the Entscheidungsproblem asked a question that nobody had thought to formalize: what does it mean to compute something? And in answering it, Turing proved something that most people find shocking.
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. What is the best way to characterize Turing’s paper? Simple. It changed the world.
