are there problems that computers cannot
solve even if you work with the
cleverest programmers even if you have
infinite time and energy and more
computing power than could possibly ever
exist in the universe are there some
things that it will always be impossible
for a computer to work out the short
answer is yes the long answer would be
an entire lecture series in introductory
computer science the barely short answer
that I hope I haven't simplified too
much is the rest of this video one of
the great things about old computers
like these BBC micros was that the
operating system the first thing you got
when you switched them on was also
somewhere that you could just write code
so if you were a shop assistant selling
these in the 80s you would have to watch
out when the kids weren't in school
because while you were distracted some
nerd could slip in and quietly type in
something like this and suddenly your
display model was endlessly typing out
something rude until he hit the brake
key or turn the computer off and on
again that is a really simple example of
a program that will never halt and it is
deliberately written that way but
programs that never halt can also be
written accidentally we've all had that
moment where something we're working on
freezers stuck in an endless loop doing
something and you have that horrible
moment of trying to remember whether you
saved recently or not it will be
brilliant to be able to analyze code any
code and say definitively yes eventually
it'll halt or no though there's a point
in there or it'll keep looping forever
if this happens which sounds like a
simple problem it's actually impossible
literally mathematically impossible how
we found that out comes from before
electronic computers were even invented
in the early 20th century a
mathematician named David Hilbert posed
a series of problems that he thought
mathematics should be able to answer one
of them came to be known as the the
decision problem which is in short can
we determine if any given statement
meaning absolutely any logical statement
or problem in the universe is provable
or not given enough time could we find
an answer
everything Hilbert was optimistic that
the answer would be yes the
mathematicians proved him wrong one of
those mathematicians was Alan Turing and
to explain his proof we first need to
look at the tool that he used to make it
Turing was looking at the mechanization
of logic and computation a computer at
this point wasn't an electronic thing it
was a job description of people who sat
in rooms doing specific calculations
over and over and over they were called
computers because they computed Turing
was fascinated by the idea of automating
that process the dream was if everything
could be encoded into numbers and if we
had mechanical methods for working with
those numbers then maybe anything could
be solved he came up with a hypothetical
calculating machine which ended up being
named at him a Turing machine will be
made off at first a tape and this tape
would be thanks to this existing in
magical hypothetical philosophy land
infinitely long and divided into cells
in modern terms that's computer memory
next a read/write head which can move
left or right over that tape reading
what's there or change it then it has a
state register and a table of
instructions which in modern terms are
the code there's a lot of complicated
stuff I'm glossing over there about how
this all works but in short it's some
code the Machine follows that code which
might include instructions like move
left move right change what's on this
bit of tape read what's on this bit of
tape and which instructions are used can
depend on what those bits of tape say
eventually the Turing machine reaches
the end of its instructions that it
halts or it enters an endless loop it
was basically the minimum possible
computer but it turns out it's also
every computer any program you write in
any programming language can be
converted into something that can run on
a Turing machine so using that machine
Turing restated the decision problem can
we determine if any given program will
halt or not halt
same question phrase differently well
the machine find a solution through a
statement or will it keep running
forever remember the big question that
we're trying to answer is is there any
question that a computer
cannot solve so Joran proposed a series
of steps and yes I know computer
scientists watching this is a deliberate
simplification I know there are lots of
subtle things I'm skipping over but
Turing proposed a series of steps first
imagine that we come up with a Turing
machine a program that can look at some
code and figure out if that program will
halt at this point we don't need to know
how that machine actually does it let's
just assume that it works somehow let's
call this machine this this program
halts halts takes the code for a program
as its input and outputs one of two
answers yes that program halts or no it
loops forever so far so good right so
we're gonna bolt another machine another
program on the end of halts and
depending on the output from halts it
will do one of two things
if halts outputs yes knowing that the
program you fail in eventually will stop
then that machine goes into an infinite
loop maybe just print something ruled
over and over whatever and if halts
outputs and know if halts works out the
code we fed in would loop forever
then this new machine just holds okay so
if halts reads the code and says that'll
halt then the new machine loops if halts
of the program will loop the new machine
halts we will put a box around both of
those and call this whole new machine
opposite because it does the opposite of
whatever code you feed it with all that
setup here's where Turing Springs the
trap he proposes that we take this new
combined program our opposite we take
its code and we feed its own code into
itself what will it do well let's step
through the logic if it thinks the
answer is this code will halt then it
will loop but then the answer is it'll
loop some of them hold the Danakil halt
so it'll loop but then it'll it vanishes
in a puff of logic to be clear that's
not a loop in itself that's a paradox
that's a logical mathematical
impossibility and that is Turing's
answer to the decision problem if you
ever have a program that can determine
for certain whether any particular
program will halt or loop you can easily
tweaked a little letting contradict
itself and call
paradox and that's impossible so a
program to do that can not exist which
means there's definitely an exception
but there's definitely at least one
thing that computers cannot ever solve
even given infinite time and power the
answer through the decision problem the
answer to the question can we determine
if every program will halt or not halt
is no now there are obviously a lot of
programs where you can easily tell at a
glance if they halt or not this code
will loop forever that code will exit
and halt the decision problem isn't
about whether you can tell if some
programs will halt or loop that's easy
it's about every program it's about the
fundamental fact that there are
definitely some things that computers
cannot ever possibly solve which came to
blow to those mathematicians like David
Hilbert who believed that pure
mathematics have the ability to solve
anything
computers seemed like amazing machines
that could calculate any problem thrown
at them
if given enough time but even before the
first digital computer existed Alan
Turing had worked out that they do still
have limits
you