Introduction to Computing Theory

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
00:00 -
Babbage Mechanical Calculators
00:00 -
Hilbert’s Second Problem
00:00 -
Gödel’s Incompleteness Theorems
00:00 -
Turing’s Mechanization of Mathematics
00:00 -
The Abstract Turing Machine
00:00 -
Realizing the Abstract Turing Machine