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