This episode is supported by SkillShare. There are some problems computers just
can't solve. Computer, what is the meaning of life?
Will I ever stopped being a disappointment to my family? Who do you
think would win between a platypus and a wombat? But today I wanted to talk about
one problem in particular called the halting problem. It's a really cool piece
of computer science and I think the most interesting thing about it was actually
the way it was answered, but before we get into that let's talk about how it
came about. See in 1928 the mathematician David Hilbert (who even has his own space
named after him) challenged the mathematics community with three
questions especially close to his heart. Number one: is mathematics complete? Can
we prove everything that's true? Number two: is mathematics consistent?
Does it give us non contradictory answers? And number three: is mathematics
decidable? Meaning for every mathematical problem is there some kind of
step-by-step method we can take that will tell us whether a statement is true
or not? Hilbert was an optimist and thought all
questions would be answered with a resounding yes!
As he famously put it, "In mathematics there is no ignorabimus", roughly
translating to, "there is no 'we cannot know'". It was Hilbert's third question which
got a young mathematician Alan Turing thinking about another seemingly
different problem. He wondered, "Can we write a program to
tell us whether any other program will halt or run forever?". This is now known as
the halting problem and to understand it properly we first need to talk about
programs and inputs. A program is just a sequence of instructions written in a
language that a computer can understand, for example for the question "given two
values x and y, does x evenly divide y?" we can write a program that takes y and
divides it by x. If the remainder is 0 the program returns a "yes" if the
remainder is anything else it returns a "no". But the question does x evenly divide
y doesn't make any sense unless we give it some values for x and y. These are
called the inputs and programs will behave differently given different
inputs. Some more complicated programs can even have other programs as inputs,
and some can even have themselves as inputs! Now that we've gotten that out of
the way we're ready to talk about the halting problem. So first let me tell you
why this is such a big deal. There's a famous question in mathematics
called the Goldbach Conjecture and it goes: can every even number greater than
2 be written as the sum of two primes? Although every even number we've ever
encountered is the sum of two primes we haven't come up with a way to prove it.
We've kind of just brute forced it. That's why even though it's probably
true it's still considered a conjecture. But what if we wrote a computer program
that went through all the even numbers and ran an algorithm that checked all
the different ways to write this number as two positive whole numbers, x plus y?
When it finds two primes it moves on to the next even number. If it fails to find
a prime value for x and y it stops and prints out this message. If this program
ever stopped we know that it had found an even number that wasn't the sum of
two primes so the Goldbach conjecture would be
proven wrong! But how long do we let it run before we decide it's been enough? A
year? A million? The age of the universe? If we could write a program that could
tell us whether this program ever halted we could solve the Goldbach Conjecture
and many others like it. That's why the halting problem is so important. Can we
find a program that can predict whether any other program and its input will
halt or run forever? Turing answered this in a really
interesting way. He first imagined that such a program does exist. Let's call it
Hal. Hal claims he is capable of saying whether any other program in its input
will halt or run forever, but what if we built another program, Barrie, who does
the opposite of what Hal predicts. So if Hal outputs "halts", Barrie runs forever,
and if Hal outputs "runs forever", Barrie halts. Seems simple enough.
So let's see what happens when Barrie is given a random program, Randy, as input.
Barrie does the opposite of Hal so he first needs to know what Hal would say
about Randy. Does he halt to run forever? So he runs Hal with program and input
Randy. If Hal returns "Randy halts", then Barrie runs forever, and his Hal returns
"Randy runs forever", Barrie halts. So far so good. Now the genius thing that Turing
did was ask Barrie to use itself as input. So just like before he needs to
look at what Hal would say so he can do the opposite. He runs Hal with program
and input Barrie and if Hal returns "Barrie halts", then Barrie will run forever, and if
Hal returns "Barrie runs forever" he'll halt! If Barrie halts Barrie runs
forever and if Barrie runs forever Barrie halts. What?! We've reached an impossible
contradiction! Barrie can't both run and halt forever, so Hal can't exist! It was by
this way of contradiction that Turing proved that the halting problem is
impossible. We can't write a program that will tell us whether any other program
will halt. In the same paper Turing also managed to answer Hilbert's third
question, that no, mathematic is undecidable. There are some problems that
we simply can't solve. The philosophical implications of this are pretty
interesting. The human brain has often been compared to a computer and actually
when Turing wrote his paper he didn't even have machines in mind. He was
thinking of the people that carry out computations with pen and paper. If the
human mind is just a complicated program that means there are problems we
fundamentally can't solve. Not because of limitations of technology and time, but
because the halting problem says so. This video focused mainly on the theory of
computation but if you'd like to complement that with the more practical
side of things SkillShare.com has loads of classes to teach you programming. You
can learn a variety of different programming languages like Python, Java
and C++. Even if you've never programmed before and you have no idea what any of
those words meant SkillShare is very beginner friendly giving step-by-step
instructions from installation to more advanced aspects
of coding like data visualization and GPU programming. But if programming is
not really your thing Skillshare still has plenty of classes for you to explore
like this one on how to make french macaroons. Skillshare is offering a
promotion to my viewers where you can get the first two months totally free.
Just sign up using this link on screen and in the description. Just quickly
before you go one of my viewers from the University of Aahrus Denmark has created
this game where you can try and solve the same kind of problems as quantum
computers. I know it sounds hard but it's really fun and the data will help
scientists study the differences between the way we solve problems compared to
the way a quantum computer would. It's a good cause and all you have to do is
play a game. Links are in the description. Thanks for sticking with me to the end
here guys I really appreciate it. I hope you enjoyed the video and I'll see you
next week. Bye!