Kind: captions
Language: en
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
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 kanter 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
auri puankere said that later
generations will regard set theory as a
disease from which one has recovered
leopold chronicler 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 hal 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 ignorabus
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 gerdel 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 godel aside
to ask a few questions
but the next year goodell published a
proof of his incompleteness theorem and
this time everyone including hilbert
took notice
this is how goodle's proof works
goodl 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 goodall
number
so the symbol for not
gets the number one
or
has the goodall number two
if then is goodall 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 goodal 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 goodall 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 goodal 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
goodal 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 goodal number of
the whole equation zero equals zero
we can write down little 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 goodell number
and the beauty of this goodell 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 goodal
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 goodal
number and the way we calculate this
goodall 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 zero
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
goodal number a this is goodall number b
goodall number c and so on
goodl goes to all this trouble to find
this card
which says there is no proof for the
statement with goodall number g
the trick is
that the goodall 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 goodall
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 goodall'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 goodell'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
goodell'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 goodell
published his second incompleteness
theorem in which he showed that any
consistent formal system of math cannot
prove its own consistency
so taken together goodl'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
[Music]
the real legacy of david hilbert's dream
is all of our modern computational
devices
kurt godel 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
[Music]
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