Course Outline

Computability and Logic

Professor Dr K Darcy Otto
Title Computability and Logic
Code CS 4383
Credits 4
Term Spring 2027
Times Wednesday 8h30–12h10
Location TBD
Delivery Fully in-person
Contact Email
Office Hours TBD

Description

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.

We often think of mathematical progress as finding procedures. When you were young, you learned a procedure to subtract one number from another. Later, maybe you learned one to solve a quadratic equation. What Turing showed is that there is a large class of mathematical problems for which no procedure exists. Not that we haven’t found one yet. That none will ever be found. And he proved it.

His proof is the centerpiece of this course. Understanding it will require you to think carefully and abstractly, and to sit with ideas that feel strange at first. You’ll need comfort with basic mathematical concepts like powers and roots, but the real prerequisite is perseverance. Turing’s proof lies at the intersection of formal logic and theoretical computer science, and it settled one of the fundamental questions in the foundations of mathematics.

This is not a typical course in computer science or in formal logic, but you will learn a lot about both.

Learning Objectives

  1. Read, analyze, and interpret Turing’s 1936 paper as a primary text, engaging directly with a foundational document in computer science and formal logic.
  2. Understand and articulate Turing’s proof of uncomputability, including why it guarantees that certain problems can never be solved by any procedure.
  3. Work with the core concepts of formal logic and computation that Turing’s proof depends on, including the formalization of what it means to compute.
  4. Trace the connections between Turing’s paper and the fields of formal logic, theoretical computer science, and the foundations of mathematics.
  5. Develop the capacity to think abstractly about problems where intuition is unreliable and the results are counterintuitive.