machine learning, ai, cs · slides
Intuitive Intro to Gödel's Incompleteness Theorem
An informal walk towards Gödel’s incompleteness theorems, built on intuition and puzzles rather than formal logic. It starts with The Book of All True Sentences and the sentence “This sentence is not in The Book”: either the book leaves out a true sentence and is incomplete, or it includes a false one and is inconsistent. The same trick is then played on a language that generates such a book, and on Raymond Smullyan’s printing machine with the alphabet ~ P N ( ), where the sentence ~PN(~PN) says of itself that the machine will never print it. The first part follows the blog post On Gödel’s theorems and the universe.
Reading “printable” as “provable” turns the puzzle into the theorem: any consistent, effectively generated formal system that can express elementary arithmetic contains true statements it cannot prove. The slides then cover ω-consistency and the second incompleteness theorem: such a system cannot prove its own consistency.























































