- Hi everyone, Jade here.
Today's video is an origin story
about the entire field of computer science.
Now, when I say computer science,
I mean literally everything to do with computers.
Laptops, desktops, smartphones, iPods, GPSs,
quantum computers, literally every physical manifestation
of a computer you can think of.
But I also mean the theoretical side too.
So the study of algorithms, computability,
and complexity theory, all the kinds of things
that a theoretical computer scientist would study.
Now, the reason I want to tell this story
is because it's incredible.
So not only was computer science accidentally created,
but it was created from trying
to answer a very abstract question
about the foundations of mathematics.
This story highlights an incredible turn of events,
a brilliant thinker,
and the interconnectedness of two fields.
The story starts
with an extraordinary man named David Hilbert.
He lived at a very exciting time
in the history of mathematics.
See, back in the 1900s, it had come to light
that no one was really sure what they were studying
when they were studying mathematics.
When we study biology,
we're studying living things that exist in the real world.
When we study physics, we're studying real world phenomena,
which we can verify by our experiment.
But math?
Was it the study of real-world objects or abstract entities?
Did it exist in our minds
or in some other realm of existence?
The ancient Greek philosopher, Plato,
thought that mathematical objects, shapes, numbers,
and the relationships between them,
belong to their own ideal world separate from ours.
He called it the world of forms.
But Hilbert wasn't a fan.
He was a modern day man,
and the Platonist view was too mystical
and airy-fairy for his liking.
An idealized world of forms?
Please.
Hilbert was interested in down to earth matters,
what could and couldn't be proven.
Another prevailing view put forward
by the German philosopher Immanuel Kant,
was that math was a mental construct
based on our intuitions.
But Hilbert had a problem with this too.
After all, intuitions could often lead us astray.
The fact that the word paradox exists
in the English language is evidence of that.
These differing viewpoints greatly irritated Hilbert.
It's not uncommon to have multiple
viewpoints in other disciplines.
Literature, for example, is praised
for being able to have multiple
interpretations of the same thing.
Even physical laws are revised and changed over time.
But math, oh no, this just wouldn't do.
Math was regarded as different from the other disciplines.
The epitome of certainty.
The fact that two plus two equals four
would never be revised and changed.
And it just wasn't good enough that different mathematicians
had different interpretations about what it meant.
Aside from the prestige of math being called into question,
these differing opinions had practical problems, too.
Those who agreed with Ken's intuitionism
didn't believe that the idea of infinity
fit within mathematics.
Those who thought that logic was the foundation of math
ran into logical paradoxes and inconsistencies
that limited what they could and couldn't do
in comparison with the other schools of thoughts.
You couldn't have different mathematicians
playing by different rules.
This was just unacceptable,
and Hilbert was going to do something about it.
He proposed a crazily ambitious program,
to axiomatize all of mathematics.
This sentence requires some explaining.
See, Hilbert thought that if we treat math
as nothing more than a formal system,
there could be no more disagreements
about what was and wasn't allowed.
So what is a formal system?
Well, it's an alphabet or a set of meaningless symbols
which can be manipulated according to a fixed set of rules.
Chess is a formal system.
The alphabet are the pieces which are manipulated
according to a fixed set of rules.
It's important to note that the pieces and the rules
don't have any meaning outside of the game.
Hilbert thought that this
was how we should view mathematics.
Something similar had been done by Euclid
on a much smaller scale some 2,000 years earlier.
By putting forward five self-evident axioms
and the rules of how to build upon them,
the whole system of Euclidean geometry was born.
Equipped with these axioms,
we don't need to know whether a triangle
lives in the world of forms or in our heads
to know that its angles always add to 180 degrees.
So in this way, Euclidean geometry
can be seen as a formal system.
Hilbert wanted to do something similar,
to find the foundational axioms for formal systems,
for which all of mathematics could be built upon.
This would eliminate any disagreements
about what was and wasn't allowed.
This was a monumental task.
And to start, Hilbert thought about the three main things
you would want in a foundational system of mathematics,
consistency, completeness, and decidability.
Consistency means that no contradictions
can be proven within the system.
For example, you can't prove that two plus two equals four,
and that two plus two doesn't equal four.
Inconsistencies would render the entire system useless.
Completeness means that a proof was required,
that all true mathematical statements
which existed in the system
could be proven within the system.
And finally, decidability.
This was the idea that there should exist
an effective procedure for deciding the truth
or falsity of any mathematical statement.
For example, if given the statement P plus Q equals Z,
there should be some effective procedure for deciding
whether this statement is true within the system.
This is where our hero of the story comes along.
Alan Turing.
You may know him from such films as "The Imitation Game,"
or the biggest award in computer science
called the Turing Award.
At the young age of 22, Turing got intensely interested
in this last question, decidability.
Did there exist an effective procedure
for deciding the truth or falsity
of any mathematical statement?
But Turing saw a slight problem with the question.
What exactly was an effective procedure?
Today, an effective procedure
is considered to be an algorithm.
Some step-by-step set of instructions that you can follow
without using any real thought or intuition.
But this was back in the '30s,
and the idea of an algorithm
was still vague and ill-defined.
We're used to the concept now
because they're fundamental to how computers work.
But computers didn't exist back then,
or at least not as we know them today.
The word computer referred to people, usually women,
who were given a list of instructions
and carried out tedious computations by hand.
This job required little thought
and definitely no mathematical intuition.
Throughout his life, Turing was fascinated
with the relationship between humans and machines.
He's famous for coming up with the idea of the Turing test,
a test for determining whether a machine
is capable of thinking like a human.
This was no exception.
As the term effective procedure
was too vague to do anything rigorous with,
he decided to define it himself.
He based his definition on a human computer.
He decided that anything a human computer could do
by mindlessly following a list of instructions
using no genius or insight whatsoever
was an effective procedure.
He thought about the basic components
of what a human computer does when they're computing.
One, they read instructions.
Two, they read and write symbols on a piece of paper
according to the instructions.
Three, they occasionally erase symbols
and replace them with new symbols.
And four, when they're finished
with the computation, they stop.
That was about it.
And here is where the truly revolutionary part comes in
that would transform the world for years to come.
Turing recognized that every step
of what a human computer did
could be replicated by a very simple theoretical machine.
In place of the human could be a scanning head,
which could read one symbol at a time,
erase one symbol at a time, and write one symbol at a time.
The piece of paper could be replaced
by an infinitely long piece of tape
which contained one symbol per square.
But how does the machine know what to do?
When a human writes a set of instructions,
something is going on in their mind,
which tells them what to do next.
Turing thought of these as states of mind.
And so similarly for his machines,
devise the idea of internal states,
which tell the machine what to do.
This idea is best understood
using visual diagrams and an example.
Say we want the machine to perform the very simple task
of recognizing when there are an even number
of zeros and ones in the tape.
This is easy for a human
who has mastered the art of counting,
but it's not so straightforward for a machine.
A simple way for our machine to tackle this problem
is to pair a zero with a one,
and then cross off the pair with an X.
It keeps doing this until it can't anymore.
If it crosses off all the symbols in the tape,
we'll know there was an even amount.
If it doesn't, we'll know that there wasn't.
Now, how do we program our machine to carry out this task?
Well, we build it with an internal state table
that looks like this.
I know this looks complicated, but it's not too bad.
Let's read it together.
Take this tape with these symbols.
We want the machine to tell us
whether there is an even number of ones and zeros.
The machine starts in the start state.
The start state tells the machine,
if I find a zero, I will replace it with an X,
move to the right, and into state B.
If I find a one, I will replace it with an X,
move to the right, and into state C.
If I find an X, I'll leave it alone,
and stay in the start state.
If I don't find any ones or zeros
and only encounter blank squares,
they must have all been paired up,
so I move to the accept state.
So at the moment, our scanning head is in the start state.
It reads a zero, replaces it with an X,
moves one square to the right, and into state B.
Now, the machine has just seen a zero
and needs to find a one to pair it with.
So state B says, if I see a zero or an X,
I'll leave them alone,
and move right one square, and stay in state B.
If I see a one, I replace it with an X,
and move to state D.
So our scanning head reads a zero,
moves one square to the right, and stays in state B.
Now it reads a one, replaces it with an X,
and moves one square to the left, and into state D.
State D is only entered when a zero, one pair
has been crossed out by Xs.
So the machine needs to reset for the next count.
It says, I keep move the scanning head to the left,
ignoring everything.
If I see a one, I leave it as a one.
If I see a zero, I leave it as a zero.
And if I see an X, I leave it as an X.
I keep moving until I reach a blank square,
which indicates I've reached
the beginning of the list of symbols.
I then move one square to the right
and go back to the start state to repeat the whole process.
After another round of this, the machine only encounters Xs.
So it keeps moving right and remains in the start state.
When it reaches a blank, it moves into the accept state,
and we know that this list of symbols
does have an even number of ones and zeros.
So that's how one of these machines would work.
But here, Turing had another incredible insight.
See, at the moment, you would need
to build different machines to do different tasks.
A machine to calculate square roots
would need to be built with a different
internal state table than a machine to do addition.
But Turing realized that any internal state table
could be encoded into a list of ones and zeros.
In this way, we could feed the instructions
as well as the problem into a new machine.
And that machine could perform that set of instructions.
Today, we know this as a programmable computer.
We have computers which we can program
to do different things after they've been built.
That idea originated right here in Turing's paper.
He dreamed up a theoretical machine
that could perform the same task
as any other of his machines.
And that was pretty freaking incredible.
Even though this theoretical machine is incredibly simple,
it can, in principle,
do everything that a human computer can do.
This abstract machine, now called a Turing machine,
was Turing's definition of an effective procedure.
An effective procedure was anything
that could be computed by a Turing machine
in a finite amount of time.
So with that out of the way,
he could go on to answer Hilbert's question.
Did there exist an effective procedure
for deciding the truth or falsity
of any mathematical statement?
Or, as framed by Turing,
did there exist a Turing machine for deciding
the truth or falsity of any mathematical statement?
The way that Turing answered this
is beyond the scope of this video.
I did make an entire separate video about it
called the Halting Problem,
which you can check out after this,
but I will tell you that Hilbert's program
ended in complete failure
and Turing contributed to it by proving
that there was not an effective procedure for deciding
whether any mathematical statement was true or false.
This alone is an amazing achievement.
But Turing's little machines took on a life of their own.
By making a definition of computation that was rigorous,
people were able to study the nature of computation
and its limitations like never before.
This birth the entire field of computer science,
which is the study of what computers can and can't do,
the complexity of algorithms,
and the overall nature of computation.
Furthermore, by coming up with an intuitive,
easy-to-understand model,
people were able to turn the abstract and vague notion
of computation into a physical machine
that could replicate the process.
Turing machines are the blueprint
of the modern day computer.
Anything from your desktop to your smartphone
to the computers on the International Space Station
are based on Turing's model.
Anything that any of these machines can do
can in principle be done by a Turing machine.
It might just take a bit longer.
Now it's worth noting that other
models of computation do exist.
Alonzo Church, who would later
become Turing's doctoral advisor,
actually came up with his own model
just weeks before Turing, called the Lambda calculus.
Turing found out about this
just before publishing his own paper
and wrote a quick appendix which showed
that Church's lambda calculus
and his own model were in fact equivalent,
meaning that anything that can be computed
by the lambda calculus can also be computed
by a Turing machine and vice versa.
However, because of their concreteness,
simplicity, and precision,
Turing machines were the model that caught on,
and captivated the imaginations
of the mathematics community.
Even though they were conceived nearly 90 years ago,
there is currently no working model of computation
more powerful than Turing's.
This is embodied in the Church-Turing thesis,
which states that anything that can be computed
can, in principle, be done so by a Turing machine.
If a Turing machine can't compute it, it's not computable.
That's not to say that this might not someday change.
There's a growing field of study called hyper-computation
which studies theoretical models of computation
more powerful than Turing machines.
The trouble is making them physically realizable.
Another model of computation that's been getting
a lot of hype recently are quantum computers,
which if they work,
will definitely bring something new to the table.
But so far, Turing's simple model
which he dreamed up at age 22,
kind of as a by-product to answer
a totally different question,
is still the most widespread model of computation to date.
This video was an origin story
about one of the most fascinating
and relevant fields of study,
but there's so much more to computers
and algorithm that's worth exploring.
If you'd like to get a real handle
on the fundamentals of computer science,
hearing about it in a video probably isn't enough,
but there is good news.
You can learn about it the same way I did,
through interactive courses on Brilliant.
In this computer science fundamentals course,
you can learn how to write programs,
search for solutions using the computational method
of brute force and make your own algorithms.
There are so many cool algorithms out there
for solving different problems,
and you'll get to explore and create the same ones
taught in a computer science degree.
By getting your hands dirty,
solving problems, and making mistakes,
you'll get a real intuition for the power of algorithms.
I can say from my own experience that this course is perfect
for those wanting to get started in computer science.
Brilliant has a whole bunch of other courses, too.
Not just in computer science, but physics and math as well.
It's worth checking out if you're a curious mind
who loves to learn and be challenged,
which as you clicked on this video, I'm guessing you are.
If you'd like to check it out and support the channel,
go to brilliant.org/UpAndAtom.
It's free to sign up,
but the first 200 people that go to that link
will get 20% off the annual Brilliant premium subscription.
That's a subscription I've been using.
The link is also available in the description.
As always, a huge thank you
to all of my wonderful patrons on Patreon.
These videos would not be possible without you,
and your dedication to science inspires me.
Thank you for watching
and I'll see you in the next episode.
Bye.