WEBVTT
Kind: captions
Language: en

1
00:00:00.130 --> 00:00:02.540
Are there problems that
computers can’t solve?

2
00:00:02.540 --> 00:00:06.680
Even if you work with the cleverest programmers,
even if you have infinite time and energy

3
00:00:06.680 --> 00:00:10.660
and more computing power than could possibly
ever exist in the universe,

4
00:00:10.660 --> 00:00:16.850
are there some things that it will always
be impossible for a computer to work out?

5
00:00:16.850 --> 00:00:18.730
The short answer is: yes!

6
00:00:18.730 --> 00:00:23.039
The long answer would be an entire
lecture series in introductory computer science.

7
00:00:23.039 --> 00:00:27.230
The fairly short answer that I hope I haven’t
simplified too much…

8
00:00:27.230 --> 00:00:30.130
is the rest of this video.

9
00:00:30.130 --> 00:00:36.960
One of the great things about old computers
like these BBC Micros was that the operating system,

10
00:00:36.960 --> 00:00:38.500
the first thing you got when
you switched them on,

11
00:00:38.500 --> 00:00:40.870
was also somewhere that
you could just write code.

12
00:00:40.870 --> 00:00:44.400
So if you were a shop assistant
selling these in the 80s,

13
00:00:44.400 --> 00:00:47.440
you would have to watch out when
the kids weren’t in school,

14
00:00:47.440 --> 00:00:49.350
because while you were distracted,

15
00:00:49.350 --> 00:00:54.820
some nerd could slip in and quietly type in
something like this.

16
00:00:54.820 --> 00:00:59.210
And suddenly your display model was endlessly
typing out something rude

17
00:00:59.210 --> 00:01:03.050
until you hit the ‘break’ key or
turned the computer off and on again.

18
00:01:03.050 --> 00:01:06.770
That is a really simple example of a program
that will never halt.

19
00:01:06.770 --> 00:01:09.869
And it is deliberately written that way.

20
00:01:09.869 --> 00:01:12.200
But programs that never halt
can also be written accidentally:

21
00:01:12.200 --> 00:01:16.170
we’ve all had that moment where
something we’re working on freezes,

22
00:01:16.170 --> 00:01:18.219
stuck in an endless loop doing...
something?

23
00:01:18.219 --> 00:01:24.439
And you have that horrible moment of trying
to remember whether you saved recently or not.

24
00:01:24.439 --> 00:01:28.049
It would be brilliant to be able to analyse code,
any code, and say definitively:

25
00:01:28.049 --> 00:01:30.389
"yes", eventually it’ll halt or

26
00:01:30.389 --> 00:01:35.010
"no", there’s a point in there where it’ll
keep looping forever, if this happens.

27
00:01:35.010 --> 00:01:37.969
Which sounds like a simple problem.
It’s actually impossible.

28
00:01:37.969 --> 00:01:39.479
Literally, mathematically, impossible.

29
00:01:39.479 --> 00:01:44.520
And how we found that out comes from before
electronic computers were even invented.

30
00:01:44.520 --> 00:01:45.649
In the early twentieth century,

31
00:01:45.649 --> 00:01:49.270
a mathematician named David Hilbert posed
a series of problems

32
00:01:49.270 --> 00:01:52.909
that he thought mathematics
should be able to answer.

33
00:01:52.909 --> 00:01:55.659
One of them came to be known as the…

34
00:01:55.659 --> 00:01:57.399
…the, uh…

35
00:01:57.399 --> 00:01:59.063
the “Decision Problem.”

36
00:01:59.063 --> 00:02:00.124
Which is, in short:

37
00:02:00.124 --> 00:02:02.478
"Can we determine if any
given statement”,

38
00:02:02.478 --> 00:02:05.480
meaning absolutely any logical statement or
problem in the universe,

39
00:02:05.480 --> 00:02:08.080
“is provable or non-provable?”

40
00:02:08.099 --> 00:02:12.420
Given enough time, could we find an answer
to everything?

41
00:02:12.420 --> 00:02:15.580
Hilbert was optimistic that
the answer would be yes.

42
00:02:15.580 --> 00:02:18.580
Other mathematicians proved him wrong.

43
00:02:18.580 --> 00:02:20.480
One of those mathematicians was Alan Turing.

44
00:02:20.480 --> 00:02:26.280
And to explain his proof, we first need to
look at the tool that he used to make it.

45
00:02:26.280 --> 00:02:29.660
Turing was looking at the mechanisation of
logic and computation.

46
00:02:29.660 --> 00:02:34.340
A “computer”, at this point, wasn’t
an electronic thing, it was a job description,

47
00:02:34.340 --> 00:02:40.910
people who sat in rooms doing specific calculations
over and over and over, they were called computers.

48
00:02:40.910 --> 00:02:42.720
Because they computed.

49
00:02:42.720 --> 00:02:45.690
Turing was fascinated by the idea of automating
that process.

50
00:02:45.690 --> 00:02:48.450
The dream was if everything could be encoded
into numbers

51
00:02:48.450 --> 00:02:51.840
and if we had mechanical methods for working
with those numbers,

52
00:02:51.840 --> 00:02:54.490
then, maybe, anything could be solved.

53
00:02:54.490 --> 00:02:57.430
He came up with a hypothetical
calculating machine,

54
00:02:57.430 --> 00:02:59.050
which ended up being named after him.

55
00:02:59.050 --> 00:03:02.000
A Turing Machine would be made of, first:

56
00:03:02.000 --> 00:03:03.050
a tape.

57
00:03:03.050 --> 00:03:07.940
This tape would be, thanks to this existing
in magical hypothetical philosophy land,

58
00:03:07.940 --> 00:03:10.460
infinitely long, and divided into cells.

59
00:03:10.460 --> 00:03:13.100
In modern terms, that’s computer memory.

60
00:03:13.100 --> 00:03:17.030
Next, a read-write head, which can move
left or right over that tape,

61
00:03:17.030 --> 00:03:20.050
reading what’s there or changing it.

62
00:03:20.050 --> 00:03:23.280
Then it has a state register and
a table of instructions,

63
00:03:23.280 --> 00:03:26.320
which in modern terms are the code.

64
00:03:26.320 --> 00:03:28.310
There’s a lot of complicated stuff that
I’m glossing over there

65
00:03:28.310 --> 00:03:32.200
about how it all works, but in short:
it’s some code.

66
00:03:32.200 --> 00:03:33.770
The machine follows that code,

67
00:03:33.770 --> 00:03:36.680
which might include instructions like
“move left”, “move right”,

68
00:03:36.680 --> 00:03:39.210
“change what’s on this bit of the tape”,
or “read what’s on this bit of the tape”,

69
00:03:39.210 --> 00:03:43.190
and which instructions are used can depend
on what those bits of tape say.

70
00:03:43.190 --> 00:03:47.410
Eventually, the Turing machine reaches the
end of its instructions and it halts.

71
00:03:47.410 --> 00:03:49.230
Or it enters an endless loop.

72
00:03:49.230 --> 00:03:53.350
It was, basically, the minimum possible computer.

73
00:03:53.350 --> 00:03:56.650
But it turns out it’s also every computer.

74
00:03:56.650 --> 00:03:58.620
Any program that you write
in any programming language

75
00:03:58.620 --> 00:04:02.960
can be converted into something that can run
on a Turing machine.

76
00:04:02.960 --> 00:04:06.270
So using that machine, Turing restated the
Decision Problem:

77
00:04:06.270 --> 00:04:11.360
"Can we determine if any given program will
halt or not halt?"

78
00:04:11.360 --> 00:04:13.270
Same question, phrased differently.

79
00:04:13.270 --> 00:04:16.090
Will the machine find a solution,
prove a statement,

80
00:04:16.090 --> 00:04:17.900
or will it keep running forever?

81
00:04:17.900 --> 00:04:20.840
Remember, the big question that
we’re trying to answer is:

82
00:04:20.840 --> 00:04:24.980
is there any question that
a computer cannot solve?

83
00:04:24.980 --> 00:04:27.560
So, Turing proposed a series of steps.

84
00:04:27.560 --> 00:04:29.680
And yes, I know, computer scientists watching,

85
00:04:29.680 --> 00:04:31.690
this is a deliberate simplification,

86
00:04:31.690 --> 00:04:34.430
I know there are lots of subtle things
I’m skipping over.

87
00:04:34.430 --> 00:04:37.220
But: Turing proposed a series of steps.

88
00:04:37.220 --> 00:04:40.290
First: imagine that we come up with
a Turing machine, a program,

89
00:04:40.290 --> 00:04:42.860
that can look at some code,

90
00:04:42.860 --> 00:04:45.580
and figure out if that program will halt.

91
00:04:45.580 --> 00:04:49.990
At this point we don't need to know how
that machine actually does it,

92
00:04:49.990 --> 00:04:52.590
let’s just assume that it works somehow.

93
00:04:52.590 --> 00:04:55.740
Let's call this machine, this program, "Halts".

94
00:04:55.740 --> 00:04:58.740
"Halts" takes the code for a program as its
input,

95
00:04:58.740 --> 00:05:00.550
and outputs one of two answers:

96
00:05:00.550 --> 00:05:02.760
“Yes”, that program halts.

97
00:05:02.760 --> 00:05:05.180
Or “No”, it loops forever.

98
00:05:05.180 --> 00:05:06.520
So far, so good, right?

99
00:05:06.520 --> 00:05:10.110
So, we’re going to bolt another machine,
another program, on the end of “Halts”.

100
00:05:10.110 --> 00:05:13.230
And depending on the output from “Halts”,
it’ll do one of two things.

101
00:05:13.230 --> 00:05:18.047
If “Halts” outputs ‘yes’, knowing that
the program you've fed in will eventually stop,

102
00:05:18.047 --> 00:05:19.840
then that machine
goes into an infinite loop.

103
00:05:19.840 --> 00:05:22.840
Maybe it just prints something rude over
and over.

104
00:05:22.880 --> 00:05:24.130
And if Halts outputs a 'no',

105
00:05:24.130 --> 00:05:27.670
if Halts works out the code we’ve fed in
would loop forever,

106
00:05:27.670 --> 00:05:29.590
then this new machine just halts.

107
00:05:29.590 --> 00:05:33.400
Okay? So if Halts reads the code
and says “that’ll halt”,

108
00:05:33.400 --> 00:05:35.070
then the new machine loops.

109
00:05:35.070 --> 00:05:37.990
If Halts says a program will loop,
the new machine halts.

110
00:05:37.990 --> 00:05:42.940
We'll put a box around both of those and call
this whole new machine "Opposite".

111
00:05:42.940 --> 00:05:46.350
Because it does the opposite of
whatever code you feed in.

112
00:05:46.350 --> 00:05:50.080
With all that set up, here’s where Turing
springs the trap.

113
00:05:50.080 --> 00:05:55.740
He proposes that we take this new combined
program, Opposite, we take its code,

114
00:05:55.740 --> 00:05:58.460
and we feed its own code into itself.

115
00:05:58.460 --> 00:06:00.380
What will it do?

116
00:06:00.380 --> 00:06:02.590
Let's step through the logic.

117
00:06:02.590 --> 00:06:06.169
If it thinks the answer is: this code will halt,
then it will loop.

118
00:06:06.169 --> 00:06:08.600
But then the answer is: it’ll loop. So it’ll halt.

119
00:06:08.600 --> 00:06:10.000
But then it’ll halt. So it’ll loop.

120
00:06:10.000 --> 00:06:13.100
But then, it’ll… daaagh.
And it vanishes in a puff of logic.

121
00:06:13.100 --> 00:06:16.040
To be clear, that’s not a loop in itself.

122
00:06:16.040 --> 00:06:20.090
That’s a paradox.
That’s a logical, mathematical impossibility.

123
00:06:20.090 --> 00:06:22.490
And that is Turing’s answer
to the Decision Problem.

124
00:06:22.490 --> 00:06:26.200
If you ever have a program that can determine,
for certain,

125
00:06:26.200 --> 00:06:28.780
whether any particular program
will halt or loop,

126
00:06:28.780 --> 00:06:31.930
you can easily tweak it a little,
let it contradict itself,

127
00:06:31.930 --> 00:06:34.260
and cause that paradox.
And that’s impossible.

128
00:06:34.260 --> 00:06:38.610
So, a program to do that can not exist.

129
00:06:38.610 --> 00:06:41.050
Which means there is definitely an exception,

130
00:06:41.050 --> 00:06:44.770
there is definitely at least one thing
that computers cannot ever solve,

131
00:06:44.770 --> 00:06:46.560
even given infinite time and power.

132
00:06:46.560 --> 00:06:49.389
The answer to the decision problem,
the answer to the question

133
00:06:49.389 --> 00:06:54.479
“Can we determine if every program will
halt or not halt?” is: no.

134
00:06:54.479 --> 00:06:56.310
Now, there are obviously a lot of programs

135
00:06:56.310 --> 00:06:59.360
where you can easily tell at a glance if they’ll
halt or not.

136
00:06:59.360 --> 00:07:00.780
This code will loop forever.

137
00:07:00.780 --> 00:07:03.170
This code will exit and halt.

138
00:07:03.170 --> 00:07:04.930
The Decision Problem isn’t about whether
you can tell

139
00:07:04.930 --> 00:07:08.540
if some programs will halt or loop.
That's easy.

140
00:07:08.540 --> 00:07:09.620
It’s about every program.

141
00:07:09.620 --> 00:07:14.030
It’s about the fundamental fact that there
are definitely some things

142
00:07:14.030 --> 00:07:17.680
that computers cannot ever possibly solve.

143
00:07:17.680 --> 00:07:20.010
Which came as a blow to those mathematicians
like David Hilbert

144
00:07:20.010 --> 00:07:25.320
who believed that pure mathematics
had the ability to solve anything.

145
00:07:25.320 --> 00:07:30.290
Computers seemed like amazing machines that
could calculate any problem thrown at them,

146
00:07:30.290 --> 00:07:31.720
if given enough time.

147
00:07:31.720 --> 00:07:34.750
But even before the first
digital computer existed,

148
00:07:34.750 --> 00:07:38.440
Alan Turing had worked out that they do still
have limits.