- Thank you to ExpressVPN for sponsoring this episode.
Hi, there welcome to Up and Atom, I'm Jade.
Today's video is about one of the deepest theorems
in mathematical logic
and a fundamental limit on human understanding.
We'll explore logical paradoxes,
the nature of information,
and the possibility of an algorithm for truth.
My hope is that by the end of the video,
you'll have a new appreciation
for the beauty and power of mathematics.
So are you ready?
Our journey begins with an odd question,
what's the biggest number you can think of?
Maybe it's a googol, a 1 followed by 100 zeros.
To give you an idea of how big this number is,
there are between 10 to the power of 78
and 10 to the power of 82 atoms in the observable universe.
It's a pretty big number,
but what about a googol plus 1.
Whatever number you think of,
can't you just add one more,
or multiply it by itself,
or take it to the power of itself?
Numbers go on forever,
so is it even possible to think of a biggest number?
Also thoughts of vague, maybe you're thinking of a number,
but you can't quite say what it is, it's more of an idea.
So let's make the question a bit more concrete,
let's instead ask,
what's the biggest number you can describe?
Let's think about this question.
If there is a biggest number you can describe,
logically, that means
there are some numbers you can't describe, right?
There's bigger than the biggest number you can describe,
but why shouldn't you be able
to describe any number you like?
Well, while there are infinitely many natural numbers,
our lives aren't infinitely long.
So even if I started counting a new number every second,
from the moment I was born,
and lived to be 100 years old,
I could only count to 3,155,760,000.
But this is a pretty stupid way to describe that number.
In fact, just saying the number
is already a description of it
'cause you know what number I'm talking about.
I could also describe it
as the number of seconds in 100 years,
which took even less time.
So here we've just described a number
in three different ways.
One took a whole lifetime and one took only eight words.
But are there some numbers we can't describe?
Well, what about a number that was a googol digits long?
If we tried to write out this number,
it would fill the space out
to the most distant visible star.
It would be impossible for a human
to read out all of these digits in their lifetime.
But maybe there's a clever,
or a shorter way we can describe it.
But imagine the number is so irregular
that there simply isn't another way to describe it,
other than just reading out its digits one by one.
There is a realm of natural numbers
that simply can't be described by a human being.
As you can't describe all numbers,
it logically follows
that there must be a biggest number you can't describe.
So the next number after that
is the first number that cannot be described by a human.
But wait, didn't we just describe it?
This is Berry's paradox,
named after the Oxford librarian, G.G. Berry.
It can be restated as the smallest positive integer
that cannot be described in fewer than 15 English words.
The paradox being that we've just described it
in 14 English words.
At the moment, this might all seem like trivial wordplay
or language trickery,
but we'll see that it reveals one of the deepest theorems
in mathematical logic.
How?
Well, the story starts in 1942, Cleveland, Ohio
with a 16 year old boy named Ray Solomonoff.
Solomonoff was searching for a general method
to solve mathematical problems and algorithm for truth.
Now, because the rest of the video revolves heavily
around this idea,
I want you to really understand it,
both to do justice to Solomonoff's genius,
and also so you can appreciate the brilliance involved.
So let me show you what I mean by algorithm for truth.
Here's me playing rock paper scissors against an AI.
Anyone who's played knows that the best way to win
is by guessing what the opponent will choose,
and then picking the object that beats it.
The AI is programmed to detect my choosing patterns,
but I'm trying to be random.
The more we play the better the AI models what I'll choose.
It's aware of a pattern in my behavior that I'm not.
You might be thinking,
Jade, maybe you just suck at pattern detection.
I can tell the difference between randomness and a pattern.
Oh yeah?
Here are sequence of numbers,
can you identify the pattern or rule they follow?
Pause the video if you'd like to try.
They're the digits 100 to 1000 of pi.
I took out the first 99,
so it wouldn't be obvious to the mathematicians out there.
They certainly don't look like they follow a simple rule.
In fact, to us,
they look extremely irregular, even random,
yet they can be generated by a very basic formula.
What other information is out there
that we think is incredibly complex,
but in fact, follows a simple rule?
Maybe predicting the weather is a piece of cake,
and we just haven't figured it out.
Maybe the theory of everything
that is the ultimate end goal of physics,
is staring us right in the face, and we just can't see it.
Solomonoff wanted a step-by-step set of instructions,
where we could plug in any set of data
and it'd spit out the general rule the data follows,
or tell us if there isn't one
and we should stop wasting out time looking.
A clear step-by-step set of instructions
is called an algorithm.
It sounds crazy,
but so crazy it just might work.
The first problem was,
what's the best way to figure stuff out?
Scientific phenomenon all seems so different.
How could one algorithm possibly solve all problems?
Well, although the ways we understand the world
are very different,
there are some things they have in common.
Usually we observe the world, record data,
and try to figure out a law that describes it.
This process is known as the scientific method.
Sometimes there are many hypothesis to explain the data,
but it's a general rule that the simpler the explanation,
the more likely it is to be the right one.
This is summed up in Occam's Razor,
the simplest explanation is usually the best one.
It's called Occam's Razor
because it shaves away unnecessary assumptions.
Solomonoff created a general theory of inductive reasoning
based on these ideas.
There was a problem though.
It's not always obvious what the most elegant
or simple solution is,
these are highly subjective words.
Solomonoff needed a way to objectively measure
the complexity of different hypotheses.
It's here in our story that we're joined
by two other characters,
Gregory Chaitin and Andrey Kolmogorov.
One American, one Russian,
both extraordinary mathematicians.
So the problem was,
how do we compare the complexity of different things?
What's more complex, a Mozart piece or a Hemingway novel,
a sea slug, or Fermat's Last theorem?
It may not seem like it,
but there is something
that all of these things have in common.
In fact, something that everything in the universe
has in common,
it's all made up of information.
Information can be thought of
as the resolution of uncertainty.
The most fundamental unit of information is the bit,
usually represented by a 1 or a 0.
How in the world can all of these things
be made up of 1s and 0s?
Well, think about this,
everything your computer or phone does
is represented and understood in terms of bits.
Every single program ran on the computer is,
at the most fundamental level,
just a series of 1s and 0s.
In principle, all of your sensory input
and the laws of the universe
can be represented by a long sequence of 1s and 0s.
These are called strings.
So now, rather than dealing with vastly different entities,
we can convert everything into strings.
When things are in the same language,
it becomes possible to measure and compare them.
Now we just need a way of deciding
which sequence of 1s and 0s is simpler
and which is more complex.
So how do we do that?
Well, let me ask you,
of these two strings, which do you think is simpler
and which do you think is more complex?
A good place to start, might be asking,
which is easier to describe?
The first string is just the digits 10 repeated 25 times.
We can program a computer to print it
by giving it the instructions or algorithm,
print 10 times 25, stop.
Of course, the exact phrasing
will depend on the programming language,
but you get the idea.
So some strings can be described in ways shorter
than writing out the whole string.
Just like some numbers can be described in ways shorter
than saying every single digit.
But how about this string?
There doesn't seem to be an obvious way
to tell the computer to print it
other than literally saying,
print, then naming every single digit, stop.
Now let's remember what these 1s and 0s represent.
They're the basic unit of information,
and information is the resolution of uncertainty.
So the more information needed to describe something,
the more uncertainty it had to begin with, right?
The less bits it needs,
the less uncertainty it had to begin with.
I think it's pretty intuitive to say
that the less uncertainty something has,
the simpler it is, don't you?
This is what our team thought too,
and they defined the measure of complexity of an object
to be the number of bits needed to describe it.
In other words, the longer the string,
the more complex it is.
Compacting strings into shorter strings
is called data compression.
But we don't want just any shorter string,
we want the shortest string.
The expression isn't,
any simpler explanation is usually the best one.
It's, the simplest explanation is usually the best one.
The shortest possible string used to describe an object
is called the Kolmogorov complexity of that object.
So here we see that Solomonoff's goal
of an algorithm for truth,
is the same thing as programming a computer
to tell us the Kolmogorov complexity of any string.
Before we go on, I just wanted to pause for a sec
to take a moment to appreciate the enormity
of what's been done here.
We've basically boiled all of the scientific method
down to the art of data compression.
We've linked philosophy,
mathematics, computation, information, complexity,
randomness, reasoning, and physics,
all in one theory,
incredible.
The idea of an algorithm for truth
suddenly doesn't seem so crazy,
but finding the shortest string is not an obvious task.
Just like with numbers,
there are many ways to describe a string.
Is print 10 times 25, stop
really the most compact way to describe this string?
If it is, how do we know?
And if it's not, how do we find out what is?
Let's consider a program, FindShortestString.
We give the program a set of data,
encoded as a string of course,
and it carries out the following steps.
It goes through every possible string,
starting from the shortest, 0,
then 1, then 00, 01, and so on.
It then interprets each string as a program
in some programming language.
Remember that a program is just a sequence of 1s and 0s,
so some of these strings will inevitably be programs.
If the string cannot be interpreted as a program,
FindShortestString moves on.
If it can be interpreted as a program,
FindShortestString runs it.
It then returns the output of the program as a string.
Next, it compares this output
against the original data string we used as input.
If it matches, FindShortestString stops,
if it doesn't match,
it moves on to the next string in the list.
This would be a pretty good candidate
for an algorithm for truth.
For example, let's pretend we don't know
what this sequence of numbers is,
and use it as input into FindShortestString.
So we want FindShortestString
to return to us the rule that generates this data.
So it starts going through every possible string,
interpreting them as programs and returning the output.
At some point it will encounter this string
which represents the formula for pi.
FindShortestString will interpret it
and run it as a program,
and its output will be the digits of pi encoded as a string.
So of course, when we compare it to our input string,
it will match,
and FindShortestString will terminate
having found the string which best describes the input data.
Because we're starting from the shortest string
and going through an increasing order,
it will be the shorter string that describes the input data.
We've computed the Kolmogorov complexity,
we'd have our algorithm for truth.
Hallelujah.
But wait, there are still loads of unsolved problems.
Scientists are still employed all over the world.
Maybe in our excitement, we've overlooked something.
All programs and made of a finite number of bits.
So let's say, FindShortestString is made of 100 bits.
Now consider another program,
Berry's paradox made of 40 bits.
We give Berry's paradox a number m as input,
and it must return the first string
that cannot be described in less than m bits.
So say we give it the number 150,
the task of the Berry's paradox program
is to find the first string
which can't be described in less than 150 bits.
This is pretty easy
if we use the help of FindShortestString.
Berry's paradox goes through all strings in order
and feeds them to FindShortestString.
The first time FindShortestString returns
a string larger than 150 bits long,
means the input that was given to FindShortestString
is the first string that cannot be described
in less than 150 bits.
Berry's paradox returns that string.
But wait, there's a slight problem,
have you spotted it?
We just described the first string
that can't be described in fewer than 150 bits
using only 140 bits.
This is a contradiction.
If the program FindShortestString was computable,
it would produce countless contradictions,
just like this one.
If we were to actually run this program,
it would loop forever, never giving us an answer.
It doesn't matter how big the programs are,
billions, even trillions of bits,
there will always be a string of longer length.
And so there will always be room for the contradiction.
Kolmogorov complexity is uncomputable.
Solomonoff's algorithm for truth is impossible.
It's not that we haven't found it yet,
or that we're not clever enough,
it's proven to be impossible.
This may have been a blow to Solomonoff
who worked his entire life on this idea.
But if old Solomonoff could go back in time,
and tell young Solomonoff
not to bother with a fruitless endeavor,
I don't think he would have.
This search led to the field
of algorithmic information theory,
the study of information, computation,
complexity, and randomness.
Wherever there are patterns to be studied,
algorithmic information theory can be applied.
What I find most fascinating
are the philosophical implications.
This result proves an intrinsic limit on human knowledge.
It also shows so beautifully
that where philosophy can ask the questions,
mathematics can answer.
I'm stoked to have been able to share this story with you,
and I hope it's given you a new appreciation
for the power of mathematics.
Algorithms have come a long way in the past few years.
You'd think that with all the advances in technology,
your internet security and privacy would be a given,
but it's not.
By default your internet service provider
can see every single site that you visit,
even in incognito mode,
or when you clear your browsing history.
They are legally allowed to sell all your data
to advertisers and companies for profit.
But you can protect yourself with ExpressVPN.
ExpressVPN reroutes your connection
through secure encrypted service.
So your ISP can't see what websites you're visiting.
It can also reroute it to a server
in any country of your choice,
making Jira restrictions a thing of the past.
My favorite thing about using ExpressVPN
is all the extra shows and movies I can watch on Netflix
that aren't available in Australia, like "Inception".
I just changed my location to Germany,
and boom, I can watch "Inception",
or I can change it to Hong Kong
and watch my favorite childhood anime, "Naruto".
If you're based in the U.S.,
you can change your location to Australia
and watch "Rick and Morty".
Find out how you can get three months free
by clicking the link in the description box below,
or go to expressvpn.com/upandatom.
Thank you to ExpressVPN for sponsoring this episode,
and I will see you in the next one, bye.
(upbeat music)