Math's Fundamental Flaw

27 Nov 2023 (1 year ago)

Game of Life (1m8s)

John Conway, creator of the Game of Life, passed away in 2020 due to COVID-19.
The Game of Life involves an infinite grid of cells which are either alive or dead.
It's governed by two rules: a dead cell with three live neighbors becomes alive, a live cell with less than two or more than three neighbors dies.
The game evolves automatically, generating a variety of patterns that may be stable, oscillatory, or even move across the grid.
Some patterns grow indefinitely, but predicting the ultimate fate of any pattern is undecidable.
No algorithm can determine in finite time whether a pattern will stabilize or grow without limit.
Many systems besides the Game of Life are also undecidable, such as Wang tiles, quantum physics, and even the game Magic: The Gathering.

Georg Cantor's proof showed that natural numbers and real numbers between 0 and 1 are not the same in size; real numbers are more numerous.
Cantor's diagonalization argument constructs a new number that cannot be on any list pairing naturals with real numbers, showing the existence of uncountable infinities.
His work was part of a greater reevaluation of mathematics, challenging notions like the concept of a limit and the true nature of infinity.
A divide among mathematicians arose, with intuitionists rejecting Cantor's work and formalists embracing it, aiming to establish a rigorous mathematical foundation through set theory.
Cantor's set theory led to paradoxes highlighted by Bertrand Russell, such as the set of all sets that don't contain themselves, which prompted further scrutiny of mathematical foundations.

Russell discovered a paradox using a village barber analogy, which led to a contradiction about who shaves the barber.
Intuitionists believed this paradox proved set theory was flawed.
Mathematicians, including Zermelo, resolved this issue by redefining set concepts to remove problematic sets.
Despite these resolutions, self-reference problems in math persisted, highlighted by Hao Wang's undecidable tiling problem, similar to Conway's Game of Life.

Gödel demonstrated that any sufficient mathematical system will contain true statements that lack proofs.
His work proved Hilbert's belief in the absolute completeness, consistency, and decidability of mathematics was incorrect.
Gödel's Incompleteness Theorem suggests that truth and provability are not synonymous.
Gödel's second theorem shows that a consistent formal system cannot verify its consistency, leaving the possibility of future contradictions.
The only remaining question from Hilbert is whether math is decidable, an issue addressed separately.

In 1936, Alan Turing invented the concept of the modern computer, originally imagined as a mechanical device to determine the decidability of mathematics.
Turing's machine consists of an infinite tape with zeroes or ones, a read/write head, and a set of instructions.
The Turing machine can perform any computable algorithm with its simple operations: overwrite, move left or right, and halt.
Turing machines can potentially solve problems like the twin prime conjecture by halting when a solution is found or running infinitely if unsolvable.
Turing proposed a hypothetical 'H machine' capable of determining whether any Turing machine would halt on a specific input.
Upon modifying H to create H+, it was proven that such a machine could not consistently predict its own behavior, leading to a contradiction.
Consequently, Turing concluded that mathematics is undecidable, implying some problems might be unsolvable, such as the twin prime conjecture.

Gapless quantum systems can undergo phase transitions at low temperatures, whereas gapped systems cannot.
Determining if a quantum system is gapped or gapless was shown to be an undecidable problem in 2015.
Even complete knowledge of a system's micro-level interactions does not guarantee the ability to predict its macro-level properties.
Turing's machines, representing the pinnacle of computational systems, still define the limits of what computation can achieve.