TLDR;
This video explores the inherent limitations of mathematics, revealing that there will always be true statements that are impossible to prove. It begins with an explanation of undecidability using Conway's Game of Life and then traces the historical development of set theory, paradoxes, and formal systems of proof. The video then explains Gödel's incompleteness theorems and Turing's work on computability, demonstrating that mathematics is undecidable. It concludes by showing how these concepts manifest in various systems, including quantum mechanics and computer science, and highlights the impact of these discoveries on modern technology.
- Undecidability in mathematics means some true statements can never be proven.
- Gödel's incompleteness theorems and Turing's halting problem demonstrate the limits of formal systems.
- These concepts have had a profound impact on the development of computer science and our understanding of the universe.
The Hole in Mathematics [0:00]
The video starts by stating that there is a fundamental limitation in mathematics: we can never know everything with certainty. There will always be true statements that cannot be proven. An example of such a statement is the Twin Prime Conjecture, which posits that there are infinitely many twin primes (prime numbers separated by only one number). Although no one has proven this conjecture true or false, it is possible that we may never know, as any mathematical system capable of basic arithmetic will inevitably contain true statements that are impossible to prove.
Conway's Game of Life [1:07]
Conway's Game of Life, created by mathematician John Conway, illustrates undecidability. The game is played on an infinite grid of cells that are either live or dead, governed by two simple rules: a dead cell with exactly three live neighbours comes to life, and a live cell with fewer than two or more than three neighbours dies. Despite these simple rules, the game can generate complex behaviours. Determining the ultimate fate of a pattern in the Game of Life is undecidable; there is no algorithm guaranteed to provide an answer in a finite amount of time. This undecidability is not unique to the Game of Life, as many other systems, such as Wang tiles, quantum physics, airline ticketing systems, and even Magic the Gathering, also exhibit this property.
The Revolt in Mathematics [3:36]
In 1874, Georg Cantor introduced set theory, which sparked a revolution in mathematics. A set is a well-defined collection of things. Cantor explored sets of numbers, such as natural numbers and real numbers, and questioned whether there were more natural numbers or more real numbers between zero and one. To investigate this, Cantor imagined matching each natural number with a real number between zero and one in an infinite list. He then devised a method to create a new real number that would not appear anywhere on the list by altering the digits on the diagonal (Cantor's diagonalisation proof). This demonstrated that there are more real numbers than natural numbers, leading to the concepts of countable and uncountable infinities.
Hilbert's Formalist Dream [6:44]
Cantor's work contributed to a period of upheaval in mathematics, challenging long-held beliefs. Mathematicians began to closely examine the foundations of their field, leading to debates between intuitionists and formalists. Intuitionists rejected Cantor's infinities, believing that mathematics was a creation of the human mind. Formalists, led by David Hilbert, aimed to establish mathematics on secure logical foundations using set theory. However, Bertrand Russell identified a paradox in Cantor's set theory, known as Russell's paradox, which involved the set of all sets that do not contain themselves. This paradox challenged the formalist approach, but mathematicians like Zermelo resolved it by restricting the concept of a set to eliminate self-reference.
Wang Tiles and Self-Reference [10:43]
In the 1960s, mathematician Hao Wang explored square tiles with coloured edges, requiring that touching edges must have the same colour. The question was whether a given set of these tiles could tile the plane infinitely without gaps. It turns out that determining whether an arbitrary set of tiles can tile the plane is undecidable, similar to the fate of a pattern in Conway's Game of Life. This undecidability stems from self-reference, a concept that Hilbert and the formalists were about to confront in their quest to secure the foundations of mathematics.
Hilbert's System of Proof [11:33]
Hilbert sought to secure the foundations of mathematics by developing a formal system of proof. Such systems begin with axioms (basic statements assumed to be true) and use rules of inference to derive new statements while preserving truth. Hilbert envisioned a symbolic logical language with rigid manipulation rules, allowing mathematical statements to be translated into this system. Russell and Whitehead developed such a system in their "Principia Mathematica," a comprehensive but dense work. Hilbert posed three key questions about mathematics: Is it complete (can every true statement be proven)? Is it consistent (free of contradictions)? Is it decidable (is there an algorithm to determine if a statement follows from the axioms)? Hilbert believed the answer to all three questions was yes.
Gödel's Incompleteness Theorems [13:36]
In 1930, Kurt Gödel demonstrated that a complete formal system of mathematics was impossible, answering Hilbert's first question negatively. Gödel's proof involved assigning a unique number (Gödel number) to each symbol and equation in a mathematical system. This allowed him to create a statement that essentially said, "This statement is unprovable." If this statement were false, it would lead to a contradiction, meaning the system would be inconsistent. If the statement were true, it would mean the system contained true statements that could not be proven, thus proving the system incomplete. Gödel's incompleteness theorem showed that any basic mathematical system capable of fundamental arithmetic will always have true statements within it that have no proof. Furthermore, Gödel's second incompleteness theorem stated that any consistent formal system of mathematics cannot prove its own consistency.
Turing and Undecidability [22:13]
In 1936, Alan Turing addressed Hilbert's third question by inventing the modern computer. Turing conceived of a theoretical machine that could perform any computation, given enough time. This Turing machine takes an infinitely long tape of cells containing zeros or ones as input and can overwrite values, move left or right, or halt. Turing then explored the "halting problem": is it possible to determine beforehand if a program will halt or not on a particular input? Turing proved that it is impossible to create a machine that can always determine whether another Turing machine will halt. This implies that mathematics is undecidable; there is no algorithm that can always determine whether a statement is derivable from the axioms.
Turing Completeness [27:14]
The problem of undecidability extends to physical systems, such as quantum mechanics, where determining the spectral gap (the energy difference between the ground state and the first excited state) is undecidable. Turing designed his machines to be as powerful as possible, leading to the concept of Turing completeness. A system is Turing complete if it can perform any computation that a Turing machine can. Many systems are Turing complete, including Wang tiles, complex quantum systems, the Game of Life, airline ticketing systems, Magic the Gathering, PowerPoint slides, and Excel spreadsheets. Each Turing-complete system has its own version of the halting problem, an undecidable property specific to that system.
Legacy and Impact [30:09]
David Hilbert's dream led to the development of modern computational devices. Kurt Gödel faced mental health challenges later in life, while Alan Turing made practical use of his ideas during World War II by leading the team at Bletchley Park that cracked Nazi codes. After the war, Turing and John von Neumann designed the first true programmable electronic computer, ENIAC, based on Turing's designs. Despite his contributions, Turing was convicted of gross indecency in 1952 for being gay and tragically committed suicide in 1954. Turing's work transformed the concept of infinity, influenced the outcome of a world war, and led to the invention of the computer. The video concludes by noting that the limitations of mathematics, while initially disheartening, have spurred innovation and changed the world.