Skip to content

Turing’s Halting Problem in Computing

Categories: Logical Science
Wishlist Share
Share Course
Page Link
Share On Social Media

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.

Show More

Course Content

A Brief History of Computers
We explore the history of ideas that led us from handlooms that used punched cards to mechanical calculators to programmable calculators, to the generalization of programming to include all of mathematics. In the process, an area called "computer science" was invented that defined the theoretical ingredients for mechanizing and automating mathematics.

  • 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

Limitations of Computing
Computers are incapable of solving several problems due to the inherent limitations of mathematics imposed by Gödel’s incompleteness theorems. We discuss different types of unsolvable problems in this topic.

Student Ratings & Reviews

No Review Yet
No Review Yet