There is a hole at the bottom of math a hole that
means we will never know everything with certainty There will always be true statements that
cannot be proven. Now no one knows what those statements are exactly but they could be something like the Twin Prime Conjecture. Twin primes are prime numbers that are separated
by just one number like 11 and 13, or 17 and 19. And as you go up the number line primes occur less
frequently and twin primes are rarer still. But the Twin Prime Conjecture is that there are infinitely
many twin primes. You never run out them. As of right now no one has proven this conjecture true or false. But the crazy thing is this: we may never know because what has been proven is that in any system
of mathematics where you can do basic arithmetic there will always be true statements
that are impossible to prove. That is life. Specifically this is the Game of Life,
created in 1970 by mathematician John Conway Sadly he passed away in 2020 from covet
19. Conway's game of life is played on an infinite grid of square cells each of which is
either live or dead and there are only two rules one any dead cell with exactly three neighbors
comes to life and two any living cell with less than two or more than three neighbors dies once
you've set up the initial arrangement of cells the two rules are applied to create the
next generation and then the one after that and the one after that and so on it's totally
automatic Conway called it a zero player game but even though the rules are simple the game
itself can generate a wide variety of behavior some patterns are stable once they arise they
never change others oscillate back and forth in a loop a few can travel across the grid forever like
this glider here many patterns just fizzle out but a few keep growing forever
they keep generating new cells now you would think that given the
simple rules of the game you could just look at any pattern and determine what will happen
to it will it eventually reach a steady state or will it keep growing without limit but it
turns out this question is impossible to answer the ultimate fate of a pattern in Conway's
game of life is undecidable meaning there is no possible algorithm that is guaranteed to
answer the question in a finite amount of time you could always just try running the pattern and
see what happens i mean the rules of the game are a kind of algorithm after all but that's not
guaranteed to give you an answer either because even if you run it for a million generations
you won't be able to say whether it'll last forever or just 2 million generations
or a billion or a googleplex is there something special about the game of life
that makes it undecidable nope there are actually a huge number of systems that are undecidable
like Wang tiles quantum physics airline ticketing systems and even magic the gathering to understand
how undecidability shows up in all of these places we have to go back 150 years to a
full-blown revolt in mathematics in 1874 Georg Cantor a german mathematician
published a paper that launched a new branch of mathematics called set theory a set is
just a well-defined collection of things so the two shoes on your feet are a set as are
all the planetariums in the world there's a set with nothing in it the empty set and a set with
everything in it now Cantor was thinking about sets of numbers like natural numbers positive
integers like 1 2 3 4 and so on and real numbers which include fractions like a third five
halves and also irrational numbers like pi e and the square root of two basically any number
that can be represented as an infinite decimal he wondered are there more natural numbers
or more real numbers between zero and one the answer might seem obvious there are
an infinite number of each so both sets should be the same size but to check this logic
canter imagined writing down an infinite list matching up each natural number on one side with
a real number between zero and one on the other now since each real number is an infinite decimal
there is no first one so we can just write them down in any random order the key is to make sure
we get them all with no duplicates and line them up one to one with an integer if we can do that
with none left over well then we know that the set of natural numbers and the set of real numbers
between 0 and 1 are the same size so assume we've done that we have a complete infinite list with
each integer acting like an index number a unique identifier for each real number on the list now
Cantor says start writing down a new real number and the way we're going to do it is by taking the
first digit of the first number and adding one then take the second digit of the second number
and again add one take the third digit of the third number add one and keep doing this all the
way down the list if the digit is a nine just roll it back to an eight and by the end of this process
you'll have a real number between zero and one but here's the thing this number won't appear anywhere
on our list it's different from the first number in the first decimal place different from the
second number in the second decimal place and so on down the line it has to be different from
every number on the list by at least one digit the number on the diagonal that's why this
is called Cantor's diagonalization proof it shows there must be more real numbers between
0 and 1 then there are natural numbers extending out to infinity so not all infinities are the same
size Cantor call these countable and uncountable infinities respectively and in fact there are many
more uncountable infinities which are even larger now Cantor's work was just the latest blow to
mathematics for 2000 years Euclid's elements were considered the bedrock of the discipline but
at the turn of the 19th century Lobashevsky and gauss discovered non-Euclidean geometries and
this prompted mathematicians to examine more closely the foundations of their field and they
did not like what they saw the idea of a limit at the heart of calculus turned out to be poorly
defined and now Cantor was showing that infinity itself was much more complex than anyone had
imagined in all this upheaval mathematics fractured and a huge debate broke out among
mathematicians at the end of the 1800s on the one side were the intuitionists who thought that
Cantor's work was nonsense they were convinced that math was a pure creation of the human mind
and that infinities like Cantors weren't real Henri Poincaré said that later generations will
regard set theory as a disease from which one has recovered Leopold Kronecker called Cantor a
scientific charlatan and a corrupter of the youth and he worked to keep Cantor from getting a job
he wanted on the other side were the formalists they thought that math could be put on absolutely
secure logical foundations through Cantor's set theory the informal leader of the formalists
was the german mathematician David Hilbert Hilbert was a living legend a hugely influential
mathematician who had worked in nearly every area of mathematics he almost beat Einstein to the
punch on general relativity he developed entirely new mathematical concepts that were crucial for
quantum mechanics and he knew that Cantor's work was brilliant Hilbert was convinced that a more
formal and rigorous system of mathematical proof based on set theory could solve all the issues
that had cropped up in math over the last century and most other mathematicians agreed with him no
one shall expel us from the paradise that Cantor has created Hilbert declared but in 1901 Bertrand
Russell pointed out a serious problem in Cantor's set theory Russell knew that if sets can contain
anything they can contain other sets or even themselves for example the set of all sets must
contain itself as does the set of sets with more than five elements in them you could even talk
about the set of all sets that contain themselves but this leads straight to a problem what about r
the set of all sets that don't contain themselves if r doesn't contain itself well then it must
contain itself but if r does contain itself then by definition it must not contain itself so r
contains itself if and only if it doesn't Russell had found another paradox of self-reference and
he later explained his paradox using a hairy analogy let's say there's a village populated
entirely by grown men with a strange law against beards specifically the law states that the
village barber must shave all and only those men of the village who do not shave themselves but the
barber himself lives in the village too of course and he's a man so who shaves him if he doesn't
shave himself then the barber has to shave him but the barber can't shave himself because the
barber doesn't shave anyone who shaves themselves so the barber must shave himself if and only if
he doesn't shave himself it's a contradiction the intuitionists rejoiced at Russell's
paradox thinking it had proven set theory hopelessly flawed but zermelo and other
mathematicians from Hilbert school solved the problem by restricting the concept of
a set so the collection of all sets for example is not a set anymore and neither is the collection
of all sets which don't contain themselves this eliminated the paradoxes that
come with self-reference Hilbert and the formalists lived to fight another day but
self-reference refused to die quite that easily fast forward to the 1960s and mathematician Hao
Wang was looking at square tiles with different colors on each side like these the rules were
that touching edges must be the same color and you can't rotate or reflect tiles only slide
them around the question was if you're given an arbitrary set of these tiles can you tell if they
will tile the plane that is will they connect up with no gaps all the way out to infinity it
turns out you can't tell for an arbitrary set of tiles whether they will tile the plane or not
the problem is undecidable just like the fate of a pattern in Conway's game of life in fact
it's exactly the same problem and that problem ultimately comes from self-reference as Hilbert
and the formalists were about to discover Hilbert wanted to secure the foundations of
mathematics by developing a new system for mathematical proofs systems of proof were an old
idea going back to the ancient greeks a system of proof starts with axioms basic statements that
are assumed to be true like a straight line can be drawn between any two points proofs are then
constructed from those axioms using rules of inference methods for using existing statements
to derive new statements and these are chosen to preserve truth the existing statements are true
then so are the new ones Hilbert wanted a formal system of proof a symbolic logical language with a
rigid set of manipulation rules for those symbols logical and mathematical statements could then
be translated into this system if you drop a book then it will fall would be a then b and no
human is immortal would be expressed like this Hilbert and the formalists wanted to express
the axioms of mathematics as symbolic statements in a formal system and set up the rules
of inference as the system's rules for symbol manipulation so Russell
along with Alfred North Whitehead developed a formal system like this in
their three-volume Principia Mathematica published in 1913. Principia Mathematica is vast a
total of nearly 2 000 pages of dense mathematical notation it takes 762 pages just to get to a
complete proof that one plus one equals two at which point Russell and Whitehead dryly note
the above proposition is occasionally useful the authors had originally planned
a fourth volume but unsurprisingly they were too worn out to complete it so yes
the notation is dense and exhausting but it is also exact unlike ordinary languages it leaves
no room for errors or fuzzy logic to creep in and most importantly it allows you to prove
properties of the formal system itself there were three big questions that
Hilbert wanted answered about mathematics number one is math complete meaning is there a
way to prove every true statement does every true statement have a proof number two is mathematics
consistent meaning is it free of contradictions i mean if you can simultaneously prove a and not
a then that's a real problem because you can prove anything at all and number three is math
decidable meaning is there an algorithm that can always determine whether a statement follows
from the axioms now Hilbert was convinced that the answers to all three of these questions was
yes at a major conference in 1930 Hilbert gave a fiery speech about these questions he ended it
with a line that summed up his formalist dream in opposition to the foolish ignorabimus which means we
will not know our slogan shall be we must know we will know these words are literally on his grave
but by the time Hilbert gave this speech his dream was already crumbling just the day before at a
small meeting at the same conference a 24 year old logician named Kurt Gödel explained that he had
found the answer to the first of Hilbert's three big questions about completeness and the answer
was no a complete formal system of mathematics was impossible the only person who paid much
attention was John von Neumann one of Hilbert's former students who pulled Gödel aside to ask a
few questions but the next year Gödel published a proof of his incompleteness theorem and this
time everyone including Hilbert took notice this is how Gödel's proof works Gödel
wanted to use logic and mathematics to answer questions about the very system
of logic and mathematics and so he took all these basic symbols of a mathematical
system and then he gave each one a number this is known as the symbol's Gödel number
so the symbol for not gets the number one or has the Gödel number two if then it's Gödel
number three now if you're expressing all of these symbols with numbers then what do you do about
the numbers themselves well zero gets its own Gödel number six and if you want to write a one
you just put this successor symbol next to it the immediate successor of zero is 1. and if you
want to write 2 then you have to write ss0 and that represents 2 and so on so you could
represent any positive integer this way granted it is cumbersome but it works
and that is the point of this system so now that we have Gödel numbers for all of
the basic symbols and all of the numbers we might want to use we can start to write equations
like we could write zero equals zero so these symbols have the Gödel numbers six five six and
we can actually create a new card that represents this equation zero equals zero and the way we
do it is we take the prime numbers starting at 2 and we raise each one to the power of the Gödel
number of the symbol in our equation so we have 2 to the power of 6 times 3 to the power of 5
times 5 to the power of 6 equals 243 million so 243 million is the Gödel number
of the whole equation zero equals zero we can write down Gödel numbers for
any set of symbols that you can imagine so really this is an infinite deck of cards where
any set of symbols that you want to write down in a sequence you can represent with a unique
Gödel number and the beauty of this Gödel number is you can do a prime factorization of it
and you can work out exactly what symbols made up this card so in this whole pack of cards
there are going to be true statements and there are going to be false statements so how
do you prove that something is true well you need to go to the axioms the axioms also have their own
Gödel numbers which are formed in the same way so here's an axiom which says not the successor of
any number x equals zero which makes sense because in this system there are no negative numbers and
so the successor of any number cannot be zero so we can put down this axiom and then we can
substitute in zero for x saying that one does not equal zero and we've created a proof this is the
simplest proof i can think of that shows that one does not equal zero now this card for the proof of
one does not equal zero gets its own Gödel number and the way we calculate this Gödel number
is just as before we take the prime numbers and we raise 2 to the power of the axiom times
3 to the power of 1 does not equal 0 and we get a tremendously large number it would have 73
million digits if you calculated it all out so i've just left it here in exponential notation as
you can see these numbers get very large and so you might want to start just calling them by
letters so we could say this one is Gödel number a this is Gödel number b Gödel number
c and so on Gödel goes to all this trouble to find this card which says there is no proof for the
statement with Gödel number g the trick is that the Gödel number of this card is
g so what this statement is really saying is this card is unprovable there is no proof
anywhere in our infinite deck for this card now think about it if it's
false and there is a proof then what you have just proven is there is
no proof so you're stuck with a contradiction that would mean the mathematical system is
inconsistent the other alternative is that this card is true there is no proof for the
statement with Gödel number g but that means this mathematical system has true statements
in it that have no proof so your mathematical system is incomplete and that is Gödel's
incompleteness theorem this is how he shows that any basic mathematical system that can do
fundamental arithmetic will always have statements within it which are true but which have no proof
there's a line in the tv show the office that echoes the self-referential paradox of Gödel's
proof jim is my enemy but it turns out the jim is also his own worst enemy and the enemy of my
enemy is my friend so jim is actually my friend but because he is his own worst enemy the enemy of my friend is my enemy so
actually jim is my enemy but Gödel's incompleteness theorem means that
truth and provability are not at all the same thing Hilbert was wrong there will always be true
statements about mathematics that just cannot be proven now Hilbert could console himself with
the hope that at least we could still prove maths consistent that is free of contradictions
but then Gödel published his second incompleteness theorem in which he showed
that any consistent formal system of math cannot prove its own consistency so taken together
Gödel's two incompleteness theorems say that the best you can hope for is a consistent yet
incomplete system of math but a system like that cannot prove its own consistency so some
contradiction could always crop up in the future revealing that the system you'd been working with
had been inconsistent the whole time and that leaves only the third and final big question from
Hilbert is mathematics decidable that is is there an algorithm that can always determine whether
a statement follows from the axioms and in 1936 Alan Turing found a way to settle this question
but to do it he had to invent the modern computer in his time computers weren't machines
they were people often women who carried out long and tedious calculations Turing
imagined an entirely mechanical computer he wanted it to be powerful enough to perform any
computation imaginable but simple enough that you could reason through its operation so he came up
with a machine that takes as input an infinitely long tape of square cells each containing a zero
or a one the machine has a read write head that can read one digit at a time then it can perform
one of only a few tasks overwrite a new value move left move right or simply halt
halting means the program has run to completion the program consists of a set of
internal instructions you can think of it like a flow chart that tells the machine what to do
based on the digit it reads and its internal state you could imagine exporting these instructions to
any other Turing machine which would then perform in exactly the same way as the first although
this sounds simple a Turing machine's arbitrarily large memory and program mean it can execute any
computable algorithm if given enough time from addition and subtraction to the entire youtube
algorithm it can do anything a modern computer can that's what made the Turing machine so useful in
answering Hilbert's question on decidability when a touring machine halts the program has finished
running and the tape is the output but sometimes a touring machine never halts maybe it gets stuck in
an infinite loop is it possible to tell beforehand if a program will halt or not on a particular
input Turing realized this halting problem was very similar to the decidability problem if
he could find a way to figure out if a Turing machine would halt then it would also be possible
to decide if a statement followed from the axioms for example you could solve the twin prime
conjecture by writing a Turing machine program that starts with the axioms and constructs
all theorems that can be produced in one step using the rules of inference then it constructs
all theorems that can be produced in one step from those and so on each time it generates a
new theorem it checks if it's the twin prime conjecture and if it is it halts if not it never
halts so if you could solve the halting problem you could solve the twin prime conjecture
and all sorts of other unsolved questions so Turing said let's assume we can make a
machine h that can determine whether any Turing machine will halt or not on a particular
input you insert the program and its input and h simulates what will happen printing out
either halts or never halts for now we don't worry about how h works we just know that it always
works it always gives you the right answer now we can modify the h machine by adding additional
components one if it receives the output halts immediately goes into an infinite loop another if
it receives never holds then it immediately halts we can call this entire new machine h plus and
we can export the program for that entire machine now what happens if we give this machine
its own code both as program and input well now h is simulating what h plus
would do given its own input essentially h has to determine the behavior of a machine
that it itself is a part of in this exact circumstance if h concludes that h plus never
halts well this makes h plus immediately halt if h thinks h plus will halt well then
that necessarily forces h plus to loop whatever output the halting machine h gives it
turns out to be wrong there's a contradiction the only explanation can be that a machine like
h can't exist there's no way to tell in general if a touring machine will halt or not on a given
input and this means mathematics is undecidable there is no algorithm that can always determine
whether a statement is derivable from the axioms so something like the twin prime conjecture
might be unsolvable we might never know whether there are infinite twin primes or not
the problem of undecidability even crops up in physical systems in quantum mechanics one
of the most important properties of a many-body system is the difference in energy between
its ground state and its first excited state this is known as the spectral gap some systems
have a significant spectral gap whereas others are gapless there are a continuum of energy levels
all the way down to the ground state and this is important because at low temperatures gapless
quantum systems can undergo phase transitions while gapped systems cannot they don't have
the energy needed to overcome the spectral gap but figuring out if a system is gapped or gapless
has long been known to be a very difficult problem only recently in 2015 did mathematicians
prove that in general the spectral gap question is undecidable to quote the authors even a
perfect complete description of the microscopic interactions between a material's particles is not
always enough to deduce its macroscopic properties now remember that Turing designed his machines to
be as powerful computers as it is possible to make to this day the best computational systems are
those that can do everything a touring machine can this is called touring completeness and it turns
out there are many such during complete systems although they are powerful every touring complete
system comes with a catch its own analog of the halting problem some undecidable property of
the system Wang tiles are touring complete their halting problem is whether or not they'll tile the
plane complex quantum systems are Turing complete and their halting problem is the spectral gap
question and the game of life is Turing complete its halting problem is literally whether or
not it halts there are many more examples of this like airline ticketing systems magic the
gathering powerpoint slides and excel spreadsheets nearly every programming language in existence is
designed to be Turing complete but in theory we only need one programming language because
well you can program anything at all using any Turing complete system so here's a touring
machine inside the game of life and since the game of life is itself touring complete it should
be capable of simulating itself and indeed it is this is the game of life
running on the game of life the real legacy of David Hilbert's dream
is all of our modern computational devices Kurt Gödel suffered bouts of mental instability
later in life convinced that people were trying to poison him he refused to eat eventually
starving himself to death Hilbert died in 1943 his epitaph was his slogan from 1930. we must know
we will know the truth is we don't know sometimes we can't know but in trying to find out we can
discover new things things that change the world Alan Turing put his ideas about computing to
practical use in world war ii leading the team at Bletchley Park that built real calculating
machines to crack nazi codes for the allies by one estimate the intelligence Turing and
his colleagues gathered from decrypted messages shortened the war by two to four years after
the war Turing and John von Neumann designed the first true programmable electronic
computer eniac based on touring's designs but Turing didn't live to see
his ideas develop much further in 1952 the british government convicted him of
gross indecency upon learning he was gay he was stripped of his security clearance and forced
to take hormones in 1954 he committed suicide touring changed the world he is widely
considered to be the most important founding figure in computer science all modern
computers are descended from his designs but touring's ideas about computability
came from his concept of the Turing machine which came from thinking about Hilbert's question
is math decidable so touring's code breaking machines and indeed all modern computers stem from
the weird paradoxes that arise from self-reference there is a hole at the bottom of math a hole that
means we will never know everything with certainty there will always be true
statements that cannot be proven and you might think this realization
would have driven mathematicians mad and led to the disintegration of the entire
mathematical enterprise but instead thinking about this problem transformed the concept
of infinity changed the course of a world war and led directly to the invention of the
device you're watching this on right now hey this video was sponsored by brilliant a
website full of interactive courses and quizzes that delve deep into topics like math physics and
computer science now if you've gotten this far into this video you're likely someone who would
love brilliant i've been going through their logic course and it's really got me thinking
the problems start out easy but get more and more challenging as you develop your understanding
and that's what i love about the site i love how it guides you not by telling you exactly but by
exposing you to increasingly sophisticated puzzles and at the end i feel like i've worked it out
for myself which essentially i have through their carefully curated selection of problems
and with helpful hints and explanations for when i get stuck now there were a lot of things
i wanted to include in this video but couldn't because it's already over half an hour long so if
you want to explore these ideas further i'd highly recommend their courses on number theory and
computer science fundamentals for viewers of this channel brilliant are offering 20 off an annual
subscription to the first 200 people to sign up just go to brilliant.org veritasium and i
will put that link down in the description so i want to thank brilliant for sponsoring
veritasium and i want to thank you for watching