Turing’s Halting Problem in Computing
About Course
Computer science was invented by Alan Turing shortly after his graduation when he proved the equivalence between mathematics and machines: The things that could be done using mathematics, could also be done by machines, and the things that could not be done using mathematics, also could not be done by machines. In that process, Turing reformulated Gödel’s Incompleteness proofs in mechanical terms, showing that the limitations of number theory that Gödel had demonstrated earlier also applied to machines. Turing’s work on the equivalence between machines and mathematics, including their shared limitations, paved the way for modern computing theory and science. Specifically, computer science is the study of how to mechanize or automate mathematics using a machine. Having shown the equivalence between machines and mathematics, it is a natural step to ask: Is the human mind a mathematical machine? It turns out that the human mind evades the limitations of mathematics and machines. In this course, we will explore the relation between minds, mathematics, and machines in greater detail. The goal is to understand how mathematics and machines are logically equivalent, but the mind is not a machine. The mind’s capacity to do tasks that cannot be described in mathematics makes it intriguing.
Course Content
A Brief History of Computers

The Jacquard Weaving Machine

Babbage Mechanical Calculators

Hilbert’s Second Problem

Gödel’s Incompleteness Theorems

Turing’s Mechanization of Mathematics

The Abstract Turing Machine

Realizing the Abstract Turing Machine