Turing 2018/5: Settling Hilbert’s Entscheidungsproblem, and the Halting Problem

1
00:00:01,020 --> 00:00:10,680
Right. Today is our last lecture on Turing's 1936 paper, so we'll be coming to the culmination of that.

2
00:00:10,680 --> 00:00:14,820
There's quite a lot of technical stuff in this lecture. You've got the handouts.

3
00:00:14,820 --> 00:00:18,300
I'm not going to be going through all of it in great detail.

4
00:00:18,300 --> 00:00:25,260
But the idea of having it on the slides and on the handouts is I hope to make a bit more accessible.

5
00:00:25,260 --> 00:00:32,550
Some stuff that really is quite difficult. It points to the key issues, the key passages,

6
00:00:32,550 --> 00:00:41,340
and I hope you will find it helpful when reading Pezzullo's book and Turing's paper to look at these slides at the same time.

7
00:00:41,340 --> 00:00:48,840
So some of today's stuff I'll be going through quite quickly, some of it lingering a bit more.

8
00:00:48,840 --> 00:00:54,810
Okay, so Turing has shown that the computable numbers are innumerable.

9
00:00:54,810 --> 00:01:01,110
We saw that last time. But there's a bit of a puzzle here that he remarks on.

10
00:01:01,110 --> 00:01:06,510
Remember cantors diagonal argument from our very first lecture?

11
00:01:06,510 --> 00:01:13,350
Now, it might seem that a similar kind of argument can be launched against the claim that the

12
00:01:13,350 --> 00:01:18,690
computable numbers are innumerable because if the computable numbers are innumerable,

13
00:01:18,690 --> 00:01:25,020
we should be able to form a list of them. Or at least it should be possible in theory to put them all in a list.

14
00:01:25,020 --> 00:01:33,690
Of course, what we're concerned about is binary fractions, endless sequences of zeros and ones.

15
00:01:33,690 --> 00:01:44,580
So let's imagine that we have those all in a list. Every single computable number occurs somewhere in that list because they are innumerable.

16
00:01:44,580 --> 00:01:52,740
But now suppose we do a cantor and take the digits down the long diagonal and switch them.

17
00:01:52,740 --> 00:01:59,610
So whenever there's a zero in one of these digits, we change it to a one whenever there's a one.

18
00:01:59,610 --> 00:02:08,400
We change it to a zero. It looks like that is going to give us some well-defined number,

19
00:02:08,400 --> 00:02:17,250
but that number is not going to be in the list because it will differ in the ninth place from the ninth item in the list.

20
00:02:17,250 --> 00:02:24,840
So doesn't this refute the claim that the computable numbers are innumerable?

21
00:02:24,840 --> 00:02:33,120
Well, no, not exactly. It looks like it might, but it's only going to refute that claim if in fact,

22
00:02:33,120 --> 00:02:41,020
that number is itself computable and we haven't shown that it is computable.

23
00:02:41,020 --> 00:02:46,810
How can it fail to be computable? We're going through the integers one after another.

24
00:02:46,810 --> 00:02:49,900
I mean, imagine that we just go through, you know,

25
00:02:49,900 --> 00:02:59,560
zero one two three four five six and whenever we hit a number that could be the description number of a Turing machine,

26
00:02:59,560 --> 00:03:05,590
we use that to construct, construct the standard description and then we simulate that machine.

27
00:03:05,590 --> 00:03:10,420
We know from the universal machine that it's possible to do that.

28
00:03:10,420 --> 00:03:18,460
So why don't we just do that repeatedly mimic in turn, the first, second, third, fourth, fifth machine and so forth?

29
00:03:18,460 --> 00:03:24,130
Find out what the institute is, swap it and then move on to the next one.

30
00:03:24,130 --> 00:03:30,820
Why won't that give away of computing this diagonal number beta?

31
00:03:30,820 --> 00:03:36,070
Well, the answer is that it's not enough.

32
00:03:36,070 --> 00:03:39,910
When we are generating these machines,

33
00:03:39,910 --> 00:03:48,580
we're going through looking at internet every integer that can be the number of a Turing machine, and then we're running it.

34
00:03:48,580 --> 00:03:52,990
It's not enough just to know that it is the number of a Turing machine.

35
00:03:52,990 --> 00:03:59,770
We've got to know that it's the number of a circle free Turing machine because only circle free Turing machines,

36
00:03:59,770 --> 00:04:03,670
that's the one ones that carry on generating zeros and ones.

37
00:04:03,670 --> 00:04:09,130
Infinitely only those generate computable numbers.

38
00:04:09,130 --> 00:04:13,510
So the construction must fail at that point. All right.

39
00:04:13,510 --> 00:04:19,780
I'm Turing has argued, after all, that all computable numbers are innumerable. That looks like a very strong argument.

40
00:04:19,780 --> 00:04:24,730
We have an argument here that seems to refute that.

41
00:04:24,730 --> 00:04:30,700
Well, if the argument earlier was correct, this attempt must fail.

42
00:04:30,700 --> 00:04:40,960
And here is where it must fail that if you are trying to compute that number beta the diagonal number,

43
00:04:40,960 --> 00:04:47,380
it must be that as you try to construct these Turing machines that generate those numbers,

44
00:04:47,380 --> 00:05:00,510
in turn all these computable numbers, you cannot identify whether the number is actually the number of a Circle three machine.

45
00:05:00,510 --> 00:05:06,120
So Turing concludes that the cannot be any general process for finding out whether a given

46
00:05:06,120 --> 00:05:11,670
number is the description number of a circle free machine in a finite number of steps.

47
00:05:11,670 --> 00:05:23,380
So there's no computable way of working out whether a Turing machine in general is circle free.

48
00:05:23,380 --> 00:05:27,550
Now, cheering remarks that the reader might find this a little bit odd.

49
00:05:27,550 --> 00:05:41,140
The argument seems a little bit contrived. So he backs it up with an explanation of exactly where he thinks the attempt would fail.

50
00:05:41,140 --> 00:05:51,730
So imagine that you have some machine, some Turing machine, which is attempting to construct this no beta.

51
00:05:51,730 --> 00:05:58,570
Well, that machine itself must have some description. No, let's suppose its end.

52
00:05:58,570 --> 00:06:03,250
And that machine, in order to create the digit of this number,

53
00:06:03,250 --> 00:06:11,710
beta is going to have to first discover what is the ninth digit of machine with description.

54
00:06:11,710 --> 00:06:16,960
No end. And then it's got to flip it so we can see actually,

55
00:06:16,960 --> 00:06:24,760
we get a contradiction because what it's trying to do is find its own entry digit and then output the inverse of that.

56
00:06:24,760 --> 00:06:30,820
In fact, it's going to get into a loop, isn't it, because it will be trying to find its own digit?

57
00:06:30,820 --> 00:06:40,880
It will go through all that process in order to find its own digit. It has first to find its own digit and we will get into an infinite loop.

58
00:06:40,880 --> 00:06:48,820
Now, although this isn't strictly Turing, I want to just pop in another diagonal argument here, which is somewhat reminiscent of this.

59
00:06:48,820 --> 00:06:57,040
It's also reminiscent of cantors and girdles, and that is the proof of the halting problem.

60
00:06:57,040 --> 00:07:01,030
Now, it's not quite the same as what Turing is shown, but it's very similar.

61
00:07:01,030 --> 00:07:06,430
Turing is has shown that no Turing machine can be devised,

62
00:07:06,430 --> 00:07:16,540
which is capable of telling whether some other Turing machine in general will or won't be circle free.

63
00:07:16,540 --> 00:07:22,000
Whether it will or will not continue printing zeros and ones forever.

64
00:07:22,000 --> 00:07:28,270
What we're now going to show is that the halting problem is unsolvable and this is something you might well have come across.

65
00:07:28,270 --> 00:07:36,760
It is striking how easy it is to show this, and you will see that the reasoning is somewhat reminiscent of of Turing's.

66
00:07:36,760 --> 00:07:44,350
Okay, so here's the Turing the halting problem x here we can forget about Turing machines for the moment.

67
00:07:44,350 --> 00:07:49,570
Just imagine that you have a general all purpose, standard programming language,

68
00:07:49,570 --> 00:07:59,480
and imagine that we have the text of a programme in that language p and that programme takes input from a text file.

69
00:07:59,480 --> 00:08:05,290
T So we've got two files. One of them is the text of a programme in the standard programming language.

70
00:08:05,290 --> 00:08:11,890
One of them is the text of the input into that programme.

71
00:08:11,890 --> 00:08:18,220
So to solve the halting problem, what we want is a testing procedure, let's call it H.

72
00:08:18,220 --> 00:08:26,560
Which will examine the text of the programme and the text of the input, and it will then reliably work out the answer to this question.

73
00:08:26,560 --> 00:08:35,950
Will programme P when run with input t eventually halt or, on the other hand, will never terminate.

74
00:08:35,950 --> 00:08:41,410
And Turing's argument, or very similar argument implies that h is impossible.

75
00:08:41,410 --> 00:08:49,750
Notice there's a little irony here in that when what Turing thinks of as a satisfactory Turing machine is one that actually goes on forever,

76
00:08:49,750 --> 00:08:54,310
whereas generally with programmes, a satisfactory programme is one that terminates.

77
00:08:54,310 --> 00:09:03,130
So there's a slight difference there, but it's the same kind of principle. OK, so let's suppose we have here programmed h.

78
00:09:03,130 --> 00:09:08,680
This is our hypothetical programme, which is going to solve the halting problem.

79
00:09:08,680 --> 00:09:20,170
So it takes two inputs the text of a programme, the text of the input, and then it decides whether or not the programme p would halt given that input.

80
00:09:20,170 --> 00:09:24,880
If so, it prints. Yes, yes. Meaning it will halt.

81
00:09:24,880 --> 00:09:29,710
If not, it prints. No, no, meaning it won't halt.

82
00:09:29,710 --> 00:09:39,400
So it goes up the Green Line. If if it will halt the Red Line, if it won't.

83
00:09:39,400 --> 00:09:45,820
Now what we're going to do is modify that programme. Let's suppose that Programme H is a possible programme.

84
00:09:45,820 --> 00:09:54,730
We're going to modify it both at the input and at the output, the input instead of putting the text on the programme in a separate inputs.

85
00:09:54,730 --> 00:10:01,270
We're going to put the text of the programme p in as both inputs, and you might think that's very odd.

86
00:10:01,270 --> 00:10:09,100
How often do you have a programme which takes its own text as input, but not often?

87
00:10:09,100 --> 00:10:13,960
But what we're doing here is showing a case that gives rise to a contradiction.

88
00:10:13,960 --> 00:10:19,090
So no reason in principle why we shouldn't do that. And you can see this is very straightforward.

89
00:10:19,090 --> 00:10:27,310
All it involves is duplicating file p and then putting that into the input where T would have gone back.

90
00:10:27,310 --> 00:10:34,180
We're modifying the outputs. Well, one of the outputs, the one that goes up the Green Line.

91
00:10:34,180 --> 00:10:39,160
In other words, when the H makes the decision, the thing will hold.

92
00:10:39,160 --> 00:10:46,150
We're changing it so that instead of printing, it repeatedly prints yes, until zero equals one.

93
00:10:46,150 --> 00:10:50,140
In other words, until [INAUDIBLE] freezes over, it just goes on printing.

94
00:10:50,140 --> 00:10:57,730
Yes Yes. Yes Yes. Yes Yes. Yes. Yes, yes. Forever. OK.

95
00:10:57,730 --> 00:11:04,840
So both of those modifications are straightforward modifications. If Programme H is possible, then the modified programme is possible.

96
00:11:04,840 --> 00:11:13,870
Let's call it keep his our modified programme. Now you've probably guessed what we're going to do is ask what happens when we

97
00:11:13,870 --> 00:11:22,450
feed programme Q as input into itself again may seem a strange thing to do.

98
00:11:22,450 --> 00:11:32,490
But the point of doing it is to show that H is impossible because if we feed Programme Q into itself.

99
00:11:32,490 --> 00:11:40,560
Then, H, this hypothetical programme that decides whether a programme will halt, we've given input,

100
00:11:40,560 --> 00:11:49,110
what that will do is decide where the Programme Q will halt given itself as input, if it will halt given itself as input.

101
00:11:49,110 --> 00:11:54,570
We go up the green. Oh, but that never holds.

102
00:11:54,570 --> 00:12:04,580
So that's a contradiction. Only in that case, it must decide that it doesn't hold open in that case, it prints no insults.

103
00:12:04,580 --> 00:12:08,660
So either way, we get a contradiction. If it halts, it doesn't help.

104
00:12:08,660 --> 00:12:13,820
If it doesn't call, it halts. So therefore, Programme H is impossible.

105
00:12:13,820 --> 00:12:18,020
You cannot have a programme that in general solves the whole thing problem.

106
00:12:18,020 --> 00:12:24,560
And you can see it's a similar kind of reasoning in many ways to Turing's, but a very, very powerful result.

107
00:12:24,560 --> 00:12:32,830
Reach just in three or four slides. It's quite astonishing that that that can be done.

108
00:12:32,830 --> 00:12:40,240
OK, so one point about putting that argument here is if you had any suspicion that

109
00:12:40,240 --> 00:12:45,670
Turing's argument was dubious because it's kind of circular nature here,

110
00:12:45,670 --> 00:12:49,750
we've got an example of a similar style of argument,

111
00:12:49,750 --> 00:12:58,300
which is so straightforward that I hope you will find it very plausible to see that argument just is decisive,

112
00:12:58,300 --> 00:13:05,290
that there's no funny business going on. It's a relatively straightforward argument.

113
00:13:05,290 --> 00:13:12,850
OK, so Turing has shown that no Turing machine can provide a reliable circle free test.

114
00:13:12,850 --> 00:13:19,040
He now goes on to prove a lemma, which will be very important later on.

115
00:13:19,040 --> 00:13:27,710
We can show further there can be no machine e, which, when supplied with the standard description of an arbitrary machine,

116
00:13:27,710 --> 00:13:32,780
M will determine whether M ever prints a given symbol.

117
00:13:32,780 --> 00:13:39,800
Zero say. OK, so this theme is going to crop up quite a lot.

118
00:13:39,800 --> 00:13:51,380
Take a particular Turing machine or the description of the Turing machine and ask Will that machine ever output a zero on its type?

119
00:13:51,380 --> 00:14:05,660
And we're going to suppose that there is a programme that can determine that reliably, and we're going to show a contradiction from that.

120
00:14:05,660 --> 00:14:12,360
OK, so suppose we have zero testing machine e and it's going to be applied to some arbitrary machine.

121
00:14:12,360 --> 00:14:20,270
And so we've got some Turing Machine M and we're putting that description on our tape.

122
00:14:20,270 --> 00:14:34,540
And what is supposed to do is determine in a finite number of stages whether M will or won't ever print a zero.

123
00:14:34,540 --> 00:14:42,970
Well, you can probably see that it's not too difficult to modify Machine Am to produce other machines M1 into IN3,

124
00:14:42,970 --> 00:14:50,530
et cetera, et cetera, which are just like M, except that they print out fewer zeros.

125
00:14:50,530 --> 00:15:01,870
So one of the first of them, M1, just prints one less zero and two prints, two fewer zeros and three prints, three fewer and so on.

126
00:15:01,870 --> 00:15:04,270
It's easy to see how to do this because what you do,

127
00:15:04,270 --> 00:15:14,530
you simply imagine a machine that precedes in exactly the same way as M and then when the first zero comes out or would come out instead of printing,

128
00:15:14,530 --> 00:15:23,890
if it goes to some other state and then goes back processing again, keeping a note of the fact that that's one down.

129
00:15:23,890 --> 00:15:28,330
And then next time it comes across as zero, it just prints it out normally so.

130
00:15:28,330 --> 00:15:42,020
So that will end up printing one less zero. And likewise, by having extra states, you could produce a machine and two that prints two fewer and so on.

131
00:15:42,020 --> 00:15:58,160
OK, so now what we're going to do is create a Machine G fromI, which operates by mechanically testing and M1, M2 and so on, and outputting a zero.

132
00:15:58,160 --> 00:16:06,170
Each time, if and only if, E! Would decide that the tested machine would never generate a zero.

133
00:16:06,170 --> 00:16:14,900
OK, now that's all a bit confusing, I think, but it's much easier to understand if we look at an example.

134
00:16:14,900 --> 00:16:21,620
OK, so here is our machine m and let's suppose M just for the sake of the argument.

135
00:16:21,620 --> 00:16:26,510
Suppose M outputs exactly four zeros when run.

136
00:16:26,510 --> 00:16:36,890
OK. In total, machine M1 therefore will avoid printing the first zero, but then we'll print the rest.

137
00:16:36,890 --> 00:16:44,740
So it will end up printing three zeros machine and two will avoid printing the first two zeros.

138
00:16:44,740 --> 00:16:50,900
I'll just put a five year instead of sort of arbitrary output,

139
00:16:50,900 --> 00:16:59,990
and then it will print two zeros and three will print for three days and then one zero and four will print no zeros at all.

140
00:16:59,990 --> 00:17:07,130
And five will print no zeros at all. OK, now our machine.

141
00:17:07,130 --> 00:17:21,470
G What it will do if if the machine is testing does print is zero, then it will output nothing at all.

142
00:17:21,470 --> 00:17:27,210
Whereas if our machine does not print zero, it will output a zero.

143
00:17:27,210 --> 00:17:33,830
It's not OK. So here we've got the case of a machine and that outputs four zeros.

144
00:17:33,830 --> 00:17:38,390
We've got the adapted versions M1 end to end three and four and five.

145
00:17:38,390 --> 00:17:46,430
We can see how many zeros those output and then G outputs a zero.

146
00:17:46,430 --> 00:17:54,350
If and only if the machine is testing at that point does not output zero.

147
00:17:54,350 --> 00:17:59,780
Now imagine and one and two and three and four and five and six and seven and all the others.

148
00:17:59,780 --> 00:18:04,460
Do you agree? All the others after M5 are going to output zero.

149
00:18:04,460 --> 00:18:11,660
Yeah, we we're going to get a zero from G. Every single time from now on.

150
00:18:11,660 --> 00:18:18,740
So we will end up with an infinite number of zeros. How could that fail?

151
00:18:18,740 --> 00:18:24,200
How could we not get an infinite number of zeros from machines?

152
00:18:24,200 --> 00:18:29,270
Well, only if and itself printed an infinite number of zeros.

153
00:18:29,270 --> 00:18:33,620
If any prints an infinite number of zeros, then in one and two and three,

154
00:18:33,620 --> 00:18:41,840
will all of them carry on printing an infinite number of zeros, in which case G will never output a zero?

155
00:18:41,840 --> 00:18:49,790
OK, so we now have a test, whether or not any prints zero,

156
00:18:49,790 --> 00:18:59,690
infinitely often what Turing's done is devise a clever way whereby he can transform the test of whether a

157
00:18:59,690 --> 00:19:12,030
machine ever prints zero and he's made from it a test of whether a machine print zero infinitely often.

158
00:19:12,030 --> 00:19:22,680
So if the machine exists, it follows that we can create a general process to determine whether any machine in print zero infinitely often.

159
00:19:22,680 --> 00:19:29,100
And clearly you can do exactly the same process for one.

160
00:19:29,100 --> 00:19:31,680
So this is quite clever.

161
00:19:31,680 --> 00:19:42,570
If we have a test for whether a machine will print zero infinitely often and we have a test for whether a machine will print one,

162
00:19:42,570 --> 00:19:51,240
infinitely often we can combine those together because if the answer to both of those is no,

163
00:19:51,240 --> 00:19:58,290
then it means we've only got a finite number of zeros and a finite number of ones, in which case we have a circular machine.

164
00:19:58,290 --> 00:20:03,360
We have a machine which is not going to carry on printing digits infinitely.

165
00:20:03,360 --> 00:20:17,310
So if machines were possible, then it would be possible to produce a reliable test for whether a machine is circular or not,

166
00:20:17,310 --> 00:20:24,510
and cheering has already shown that that's not possible. So therefore, Machine E isn't possible either.

167
00:20:24,510 --> 00:20:29,130
OK, that's a little bit mind bending. It's this is not at all easy.

168
00:20:29,130 --> 00:20:33,750
So, you know, if you find this a bit confusing, don't worry.

169
00:20:33,750 --> 00:20:45,840
I mean, remember, Turing has shown that there is no machine that can reliably test whether a Turing machine is circular or not.

170
00:20:45,840 --> 00:20:54,420
He's supposed that there's a machine that can test for whether a machine ever prints is zero.

171
00:20:54,420 --> 00:20:56,460
That's machine e.

172
00:20:56,460 --> 00:21:07,050
And then he's shown that if Machine E were possible, this other Machine G would be possible, which would actually provide a test for circularity.

173
00:21:07,050 --> 00:21:17,590
Therefore, Machine E isn't possible. OK, so this important memories proved you cannot have a Turing machine,

174
00:21:17,590 --> 00:21:25,150
which is able to test another Turing machine for whether or not it will ever print a zero.

175
00:21:25,150 --> 00:21:38,660
That's going to be crucial for yielding the final result of Turing's paper regarding the incidents problem.

176
00:21:38,660 --> 00:21:39,230
OK.

177
00:21:39,230 --> 00:21:50,330
Section nine sharing wants to show that the computable numbers that he's defined include all numbers, which would naturally be regarded as computable.

178
00:21:50,330 --> 00:21:58,910
This is generally known as the church sharing thesis. The church during a thesis basically is the thesis that Turing machine compute ability,

179
00:21:58,910 --> 00:22:05,300
or a couple of other equivalent notions that will come across do successfully

180
00:22:05,300 --> 00:22:14,500
characterise what we think of as computable the intuitive notion of computer ability.

181
00:22:14,500 --> 00:22:23,980
He proposes three types of argument for this claim, and the third one is in section 10 will come to that very briefly later.

182
00:22:23,980 --> 00:22:29,290
The first type of argument we've already looked at in the third lecture,

183
00:22:29,290 --> 00:22:37,270
we saw Turing's argument that a Turing machine is a generalisation of human calculation.

184
00:22:37,270 --> 00:22:46,450
Anything that can be calculated in a human way, Turing has argued, can be done by the Turing machine.

185
00:22:46,450 --> 00:22:55,450
The second argument, I think, is certainly the most influential cheering argues essentially that Turing machine computer ability,

186
00:22:55,450 --> 00:23:01,420
the kind of compute ability that he's defined, coincides with other important notions.

187
00:23:01,420 --> 00:23:11,400
And one of them is to do with what is calculable using the Hilbert functional calculus that first order predicate logic.

188
00:23:11,400 --> 00:23:22,410
And we will see some of that later. But first of all, cheering sketches how a cheering machine can be defined to generate,

189
00:23:22,410 --> 00:23:28,900
in turn, all provable formulae of a system of axioms expressed in predicate logic.

190
00:23:28,900 --> 00:23:38,220
This is what's commonly called the British Museum algorithm. He basically says, Look, suppose you've got a system of logic defined by certain axioms.

191
00:23:38,220 --> 00:23:45,780
Imagine producing a Turing machine, which in turn goes through all the possible formulae,

192
00:23:45,780 --> 00:23:50,580
generating all the possible proofs one after another, after another after another.

193
00:23:50,580 --> 00:24:01,050
This is, in theory, possible. I'm not going to go through the detail of that, but do look at it in Pezzullo's book.

194
00:24:01,050 --> 00:24:08,940
So cheering is argued in effect that anything computable through predicate logic can be computed by Turing machine.

195
00:24:08,940 --> 00:24:16,380
That the numbers definable in terms of predicate logic by the use of axioms include all the Turing machine computable numbers.

196
00:24:16,380 --> 00:24:30,650
So he sketched a proof that these two ways of defining compute ability, at least in their application to numbers, come out to the same thing.

197
00:24:30,650 --> 00:24:50,170
OK. Now, unfortunately, Turing's magnificent paper that we've been studying, he sent it off in 1936, but it turned out that six weeks earlier,

198
00:24:50,170 --> 00:24:59,410
Alonzo Church had published or sent for publication a paper a note on the children's problem,

199
00:24:59,410 --> 00:25:05,440
which also showed that the children's problem was unsolvable.

200
00:25:05,440 --> 00:25:11,500
So poor old Turing, he put all this work into showing that Hilbert dream couldn't be realised,

201
00:25:11,500 --> 00:25:21,340
and then he found that somebody else had got there first. Now, Church had done it using his lambda calculus, which many of you will know about.

202
00:25:21,340 --> 00:25:24,730
But Turing, of course, has done it in a completely different way.

203
00:25:24,730 --> 00:25:31,780
And fortunately, it was considered sufficiently novel and significant that it was worth publishing,

204
00:25:31,780 --> 00:25:37,960
despite the fact that its key results had already been scooped.

205
00:25:37,960 --> 00:25:48,160
But what the editors did was asked Turing to add an appendix in which he showed that lambda defined ability as church,

206
00:25:48,160 --> 00:25:53,380
a device and his own during machine compute ability were coincident.

207
00:25:53,380 --> 00:26:00,730
And again, you can look at the book to see the detail of that.

208
00:26:00,730 --> 00:26:07,570
He published another paper, Computer Bility in LAMDA Define Ability, which started like this.

209
00:26:07,570 --> 00:26:15,370
Several definitions have been given to express an exact meaning corresponding to the intuitive idea of effective calcul ability,

210
00:26:15,370 --> 00:26:21,820
as applied, for instance, to functions of positive integers. The purpose of the present paper is 1937.

211
00:26:21,820 --> 00:26:29,110
Paper is to show that the computable functions introduced by the author are identical with the lambda definable

212
00:26:29,110 --> 00:26:36,190
functions of church and the general recursive functions due to her brand and girdle and developed by cleaning.

213
00:26:36,190 --> 00:26:43,690
It is shown below that every lambda definable function is computable and that every computable function is general recursive.

214
00:26:43,690 --> 00:26:54,620
So this filled the last piece in that jigsaw. It showed that these three different notions actually completely coincide.

215
00:26:54,620 --> 00:26:59,960
Now, many people thought that that's pretty strong evidence to the church during thesis.

216
00:26:59,960 --> 00:27:08,600
Suppose you're trying to prove that the informal notion what what Turing calls the intuitive idea of effective calcul ability.

217
00:27:08,600 --> 00:27:15,620
You're trying to show that there is a particular way of pinning that down.

218
00:27:15,620 --> 00:27:27,560
Well, you try various ways you come up with or people come up with three different plausible ways, and it turns out they're exactly coincident.

219
00:27:27,560 --> 00:27:36,860
That seems to give strong some strong evidence or at least significant evidence that whatever other attempt we may come up with.

220
00:27:36,860 --> 00:27:45,470
At best, it will yield something that's equivalent. There's something a little philosophically odd.

221
00:27:45,470 --> 00:27:55,970
It may seem about the whole idea of pinning down precisely an intuitive notion if you have an intuitive notion like effective calcul ability.

222
00:27:55,970 --> 00:28:02,180
How can that possibly line up precisely with a formal notion?

223
00:28:02,180 --> 00:28:07,670
But it is certainly striking that all attempts to do this have come to the same thing.

224
00:28:07,670 --> 00:28:17,870
And one can argue that really, the formal process applications turn out to be what we should mean when we talk about effective calcul ability.

225
00:28:17,870 --> 00:28:27,110
We might start off with some intuitive notion, but actually it may be that the only way of really making that precise in an acceptable

226
00:28:27,110 --> 00:28:35,450
way is going to lead in the same direction as Turing Church Girl and so forth.

227
00:28:35,450 --> 00:28:42,560
OK. We're not going to talk more about the church during theses, though it's obviously a very important legacy.

228
00:28:42,560 --> 00:28:49,880
Section 10. I'm just going to summarise during gives examples of large classes of numbers which are computable.

229
00:28:49,880 --> 00:28:58,040
All sorts of results. I mean, all the things that you would naturally think of as computable turn out to be so.

230
00:28:58,040 --> 00:29:09,910
And again, this is given by Turing as an argument for supporting his notion of Turing complete ability.

231
00:29:09,910 --> 00:29:17,980
OK, then finally, we come to the application to the end problem, the denouement of the whole paper.

232
00:29:17,980 --> 00:29:23,500
This is what it's been building towards. Some of this, as I've said before, is very technical.

233
00:29:23,500 --> 00:29:26,050
Some of it, I'm just going to skate over relatively quickly.

234
00:29:26,050 --> 00:29:39,250
I'm not going to go into all the gory detail here, but I hope you will find that the general ideas are comprehensible.

235
00:29:39,250 --> 00:29:48,100
OK, so Turing is going to show that the shadings problem that is Gilbert's decision problem is unsolvable,

236
00:29:48,100 --> 00:29:53,110
and he's going to show that for any machine in,

237
00:29:53,110 --> 00:30:03,520
it is possible to construct a formula of predicate logic that is equivalent to the statement that M at some point prints a zero.

238
00:30:03,520 --> 00:30:11,080
OK, so we've seen the significance of this churning has already shown that you cannot produce a Turing machine,

239
00:30:11,080 --> 00:30:22,090
which is able to determine if some other Turing machine, you know, machine description, whether or not a zero will eventually be printed by it.

240
00:30:22,090 --> 00:30:31,930
What he's now going to do is to show how using predicate logic, we can provide a description of a machine.

241
00:30:31,930 --> 00:30:43,480
And also, we can produce a predicate logic formula, which is equivalent to the statement that a zero will be printed by that machine.

242
00:30:43,480 --> 00:30:49,210
Now, if in fact, Turing's right that it's not possible to produce a Turing machine which is

243
00:30:49,210 --> 00:30:54,490
able to determine whether some arbitrary machine will or will not print zero,

244
00:30:54,490 --> 00:30:59,800
it immediately follows that that formula of predicate logic cannot be decided.

245
00:30:59,800 --> 00:31:05,530
The formula that is equivalent to saying there's an arbitrary machine will print to zero.

246
00:31:05,530 --> 00:31:11,350
So that's how the argument is going to go. I propose, he says,

247
00:31:11,350 --> 00:31:16,870
to show that there can be no general process for determining whether a given formula you of the functional

248
00:31:16,870 --> 00:31:23,590
calculus K that is Hilbert is restricted for functional calculus predicate logic without identity.

249
00:31:23,590 --> 00:31:31,270
By the way, the mean general process for determining whether a given formula you predicate logic is provable,

250
00:31:31,270 --> 00:31:35,170
i.e. there can be no machine which supplied with any one.

251
00:31:35,170 --> 00:31:42,610
View of these formulae will eventually say whether you is provable, this is different from girdles result.

252
00:31:42,610 --> 00:31:54,580
We've already seen that. In the second lecture, Turing explained to OK during remarks that the proof appears somewhat lengthy,

253
00:31:54,580 --> 00:32:00,970
but the underlying ideas are quite straightforward. You might, if you were to read the paper by itself,

254
00:32:00,970 --> 00:32:05,890
think that actually it wasn't lengthy enough and that a great deal more explanation would be useful.

255
00:32:05,890 --> 00:32:08,590
Pezzullo's book, of course, provides that explanation,

256
00:32:08,590 --> 00:32:17,490
and I hope you'll find that these lectures will succeed in identifying the points that might otherwise cause difficulty.

257
00:32:17,490 --> 00:32:25,980
OK, so what I'm hearing is going to do is characterise a Turing machine using certain predicates,

258
00:32:25,980 --> 00:32:36,180
so these are three of them I K and R I X Y says in the complete configuration X, the Square Y is scanned.

259
00:32:36,180 --> 00:32:39,720
So that's the current square in the complete configuration.

260
00:32:39,720 --> 00:32:50,110
X the end configuration state is QM, so K, QM X and X is a number telling you what cycle the machine is through.

261
00:32:50,110 --> 00:32:57,000
Zero one two three four. How many cycles has it gone through? So which config complete configuration are we on?

262
00:32:57,000 --> 00:33:08,340
QM is one of the states, and this is asserting that on that cycle, it has this particular state.

263
00:33:08,340 --> 00:33:13,500
Are in the complete configuration x of them, the symbol on the square.

264
00:33:13,500 --> 00:33:25,130
Why is SL so you've got a whole range of these predicates, one for each state, one for each symbol.

265
00:33:25,130 --> 00:33:30,980
Oh, by the way, I'm calling those scanners state symbol, I've put them in a different order from Turing and Petzold.

266
00:33:30,980 --> 00:33:35,510
I've put them in alphabetical order here, and I'm going to keep the same order in the various formulae.

267
00:33:35,510 --> 00:33:39,380
If you look at my slides and you see they're different from the ones in the book.

268
00:33:39,380 --> 00:33:46,880
That's why I'll just call it scan state symbol. You've got those formulae, OK?

269
00:33:46,880 --> 00:33:57,770
Those predicates enable us to specify any complete configuration of a Turing machine in terms of the step number, the cycle of that configuration.

270
00:33:57,770 --> 00:34:08,300
OK, now the Turing machine rules the quintuplets. You know, the ones that say, if you're in this state and you're scanning that particular symbol,

271
00:34:08,300 --> 00:34:12,320
then do this move right, move left, stay the stay in the same place.

272
00:34:12,320 --> 00:34:25,310
Print one thing, one symbol or another and move to a different state, etc. Those quintuplets need now to be represented.

273
00:34:25,310 --> 00:34:34,730
Turing is also going to need predicates that handle numbers, in particular, expressing that one number is the immediate successor of another.

274
00:34:34,730 --> 00:34:41,060
So if X Y will mean essentially that Y equals X plus one.

275
00:34:41,060 --> 00:34:59,350
And he will see that cropping up quite a lot. OK, so let's take a particular example, suppose our machine includes this quintuple q i sj k el que el.

276
00:34:59,350 --> 00:35:06,700
So that's saying if square if in cycle X of this machine.

277
00:35:06,700 --> 00:35:14,020
Square Y is scanned in state Q AI and while containing symbol SJ.

278
00:35:14,020 --> 00:35:22,390
So remember that's that the trigger configuration. You've got a particular state and a particular symbol.

279
00:35:22,390 --> 00:35:28,720
Then this quintuple basically specifies a rule that should be applied,

280
00:35:28,720 --> 00:35:36,490
which is that in the next cycle, let's call that ex prime square y will change to symbol ESC.

281
00:35:36,490 --> 00:35:47,090
Okay. The third element of the quintuple. The machine will move left, and let's say that that moves it to square.

282
00:35:47,090 --> 00:35:57,710
Why prime? And Square, why?

283
00:35:57,710 --> 00:36:05,270
Sorry. And it should move also into state que el. So that's the the last element of the quintuple.

284
00:36:05,270 --> 00:36:17,180
Okay, so this is moving left. So although x prime equals x +1 because we're moving from cycle X to cycle x prime, so we're moving on a step.

285
00:36:17,180 --> 00:36:20,660
So x prime is x +1 y prime.

286
00:36:20,660 --> 00:36:25,160
That's the new square to which we're moving is y minus one because we're moving left.

287
00:36:25,160 --> 00:36:34,490
Not right. OK. And in cycle X, these things are true.

288
00:36:34,490 --> 00:36:53,570
Right? Set Square Y is staying with the machine is in state Q I on Cycle X and on Cycle X, where Y contains symbol S J.

289
00:36:53,570 --> 00:37:02,660
If the quintuple is applied on Cycle X Prime, now we're scanning Square y prime.

290
00:37:02,660 --> 00:37:15,200
We've moved into State Q and a square y now contains S.K.

291
00:37:15,200 --> 00:37:30,710
Okay, so notice that we're scanning Square Y Prime, but it's Square Y whose symbol has been changed to the square that we moved from.

292
00:37:30,710 --> 00:37:40,550
OK. We also need to express that all squares other than Y will contain the same symbol in the two cycles.

293
00:37:40,550 --> 00:37:44,390
All right, so there's only one square whose symbol changes. OK.

294
00:37:44,390 --> 00:37:51,200
So we get this formula during calls. This Inst followed by the quintuple.

295
00:37:51,200 --> 00:37:56,540
And notice that the formula will be different depending on whether we've got LR or N.

296
00:37:56,540 --> 00:38:09,980
This is the left moving formula. So let's just get through that for all y x sorry, x y x prime and y prime.

297
00:38:09,980 --> 00:38:25,500
If we are in the scan state symbol condition for cycle X, which we've seen and if.

298
00:38:25,500 --> 00:38:36,240
I'm sorry. That is the wrong way round. That should say X crime equals x plus one, I'm sorry.

299
00:38:36,240 --> 00:38:44,020
And y prime equals y y minus one. OK, thank you to the conditions we have before.

300
00:38:44,020 --> 00:39:00,420
Then we should have the scan status symbol, a condition that we saw before and for all Z and either Z is equal to Y.

301
00:39:00,420 --> 00:39:06,660
Notice what this means is that Z is one greater than y prime.

302
00:39:06,660 --> 00:39:10,470
And notice that Y is also one greater than y prime.

303
00:39:10,470 --> 00:39:17,010
So this effectively means that Z is equal to Y, which is the square we've moved from.

304
00:39:17,010 --> 00:39:29,790
So either Z is the square we've moved from, or Z contains exactly the same symbol in Cycle X prime as it contained in X.

305
00:39:29,790 --> 00:39:33,750
OK, so we've got one formula here for every single possible symbol.

306
00:39:33,750 --> 00:39:40,350
This is a zero, which is blank. This is S1, which is zero and so on.

307
00:39:40,350 --> 00:39:54,570
So this bit of the formula is saying this last bit that the only square that does not remain unchanged or might not remain unchanged is Square Y.

308
00:39:54,570 --> 00:40:01,830
Now you might think this is a little bit odd. Why does he not simply say here Z equals y y.

309
00:40:01,830 --> 00:40:06,930
Express it this way? Well, it's because we're using the predicate logic without identity.

310
00:40:06,930 --> 00:40:15,200
We haven't got the identity symbol to use. OK.

311
00:40:15,200 --> 00:40:25,360
Right. I'm sorry, I have made the same mistake again, haven't I?

312
00:40:25,360 --> 00:40:32,640
I do apologise that I should say again ex-prime equals X plus one.

313
00:40:32,640 --> 00:40:38,420
So this is the formula for moving right? The difference is I've highlighted.

314
00:40:38,420 --> 00:40:42,480
Whereas previously we have why prime equals one minus one. Now we've got way.

315
00:40:42,480 --> 00:40:52,650
Crime equals y +1 because when we're moving right, the square to which we're moving is one greater than the previous square.

316
00:40:52,650 --> 00:41:04,110
Okay. And oh, yes, and here notice that we've said correspondingly that Z is equal to y prime minus one.

317
00:41:04,110 --> 00:41:13,100
This is saying why crime is the successor of Z. So it implies that Z is y prime minus one, which makes Z equal to Y again.

318
00:41:13,100 --> 00:41:22,860
Right? So this part of the for in this part of the Formula Z has to be equal to Y, which is the square from which you've moved,

319
00:41:22,860 --> 00:41:37,110
because it's saying that that square need not have the same symbol in y prime in cycle x prime sorry as it did in Cycle X for completeness.

320
00:41:37,110 --> 00:41:47,780
Here is the formula for N where the head doesn't move at all and you might think here we don't need a y prime, after all.

321
00:41:47,780 --> 00:41:54,720
Are we on the same square all the time? So why do we need to bring in a y prime?

322
00:41:54,720 --> 00:42:00,300
Well, we need it because we haven't got the equality side, we haven't got identity.

323
00:42:00,300 --> 00:42:07,560
So in order to express Z equals Y, at this point, we again need to use the same trick that we did last time.

324
00:42:07,560 --> 00:42:14,580
We say Z is y prime minus one. So here we're making y prime equal to y plus one.

325
00:42:14,580 --> 00:42:22,470
But we're simply doing it in order to be able to express Z being equal to Y at that point.

326
00:42:22,470 --> 00:42:32,630
OK. That's quite tricky, but I hope you will find that with the prompting I'd given you of what's going on.

327
00:42:32,630 --> 00:42:39,950
You will be able to go and look at Turing's text and make sense of it, particularly in Petzold company.

328
00:42:39,950 --> 00:42:47,780
CHEERING, cheering. Make some mistakes. Here you can see how easy it is to make mistakes when you're doing this kind of thing.

329
00:42:47,780 --> 00:42:56,700
Petzold usefully corrects those. OK.

330
00:42:56,700 --> 00:43:12,440
So let's think about what we've now got. We've got going back in a little bit.

331
00:43:12,440 --> 00:43:26,950
Slow to go back. OK, we've got these predicates which enable us to express the complete configuration at any point which square is being scanned.

332
00:43:26,950 --> 00:43:37,450
What's on the tape? What's the state? We can do that. We've now got.

333
00:43:37,450 --> 00:43:50,950
These formulae, which enable us to express the quintuplets that constitute the machine table, the rules by which the Turing machine operates.

334
00:43:50,950 --> 00:44:07,000
Okay, so putting those together, we've now got the way, a way of expressing both the rules and the slates of any Turing machine.

335
00:44:07,000 --> 00:44:14,800
OK. Every quintuple in the given machine can be represented by one of the formula we've just seen.

336
00:44:14,800 --> 00:44:19,460
Put those all together that gives us something that Turing calls days of.

337
00:44:19,460 --> 00:44:28,180
And so days of em is the description of the machine in terms of all the quintuplets that it contains.

338
00:44:28,180 --> 00:44:32,320
In other words, it encompasses the machine table.

339
00:44:32,320 --> 00:44:43,240
OK, now what we're going to do is use that to create another formula, which represents the statement that will at some point print a zero on its type.

340
00:44:43,240 --> 00:44:51,130
So again, we're using this lemma. We know that it's not provable, that the Turing machine will or will not print to zero on its type.

341
00:44:51,130 --> 00:44:57,400
What we're now going to do is express that in predicate logic.

342
00:44:57,400 --> 00:45:04,150
There's a complication here, cheering needs to specify relevant properties of the number sequence.

343
00:45:04,150 --> 00:45:10,270
I'm using this is a bit of an excuse us Petzold does to talk about pianos axioms.

344
00:45:10,270 --> 00:45:15,220
These axioms specify the properties of the number. Series zero is the number.

345
00:45:15,220 --> 00:45:21,160
We're talking about natural numbers here, beginning with zero. Every number has a successor that is also a number.

346
00:45:21,160 --> 00:45:25,690
Zero is not the successor to any number two numbers that the successors to the

347
00:45:25,690 --> 00:45:31,210
same number are equal and the property that enables mathematical induction,

348
00:45:31,210 --> 00:45:35,920
which effectively means you've only got a single series starting from zero.

349
00:45:35,920 --> 00:45:39,400
Okay, so pempel Pianos Act seems very familiar, Petzel.

350
00:45:39,400 --> 00:45:47,290
This discusses them on Page 223, and I'd advise you to go and look at.

351
00:45:47,290 --> 00:45:54,760
Turing doesn't need all of these axioms, but he does need some basic properties of integers.

352
00:45:54,760 --> 00:46:05,380
He needs these because he's using integers in order to index the configurations of the machine.

353
00:46:05,380 --> 00:46:14,110
He expresses the properties in this formula, which seems to be intended to capture pretty much the same as piano.

354
00:46:14,110 --> 00:46:22,120
But actually, Turing gets it wrong. And in this case, I think Petzold gets it wrong as well.

355
00:46:22,120 --> 00:46:29,050
Looking at this yesterday, I'm afraid I just came to the conclusion Turing is wrong.

356
00:46:29,050 --> 00:46:36,400
His formula doesn't actually rule out a branching series. It may still be adequate for the purposes of his proof.

357
00:46:36,400 --> 00:46:49,700
But I invite you to go and check my belief here that this formula does not actually successfully capture what the piano axioms do.

358
00:46:49,700 --> 00:46:59,020
And anyway, let's leave that to one side. It's clear that one could substitute a formula that would have the desired effect.

359
00:46:59,020 --> 00:47:07,690
OK, now we come to the formula, which is going to be undecided.

360
00:47:07,690 --> 00:47:16,840
The one that says our machine. M. Fritz zero.

361
00:47:16,840 --> 00:47:33,820
Well, that last monstrosity that we saw the piano axiom formula or intended piano axiom formula that's just abbreviated as Q so Q features here.

362
00:47:33,820 --> 00:47:49,890
So what is this saying? Well, there is a, you know, that's a number zero.

363
00:47:49,890 --> 00:47:53,310
So that's the number, but there is a configuration,

364
00:47:53,310 --> 00:48:05,910
there is a number which is the number of a configuration such that within that configuration, every single square contains a blank.

365
00:48:05,910 --> 00:48:12,780
Right? That says square y en in configuration, you can take a blank.

366
00:48:12,780 --> 00:48:19,560
This is this is a universal quantified. It's saying every square in that configuration contains a blank.

367
00:48:19,560 --> 00:48:31,200
Yes. Zero. And in that configuration, the scanned square is square zero.

368
00:48:31,200 --> 00:48:35,160
And in that configuration, the initial state is sorry.

369
00:48:35,160 --> 00:48:47,820
This current state is state one. So what that's doing that is describing the initial situation in which you have a completely blank team.

370
00:48:47,820 --> 00:48:56,480
The machine is in its initial state and it's scanning square zero.

371
00:48:56,480 --> 00:49:05,120
And then you add to that the description of machine and all the quintuplets.

372
00:49:05,120 --> 00:49:12,170
And remember description of machine enemies, he's all in terms of the implications you can draw.

373
00:49:12,170 --> 00:49:19,970
So imagine that you've got that to start with and then you've got all the power to apply those quintuplets to draw more and more implications,

374
00:49:19,970 --> 00:49:27,560
which effectively correspond to future state of the machine feature complete configurations.

375
00:49:27,560 --> 00:49:37,490
And what this is saying is if there is such a you, if there is such an initial state in which that is true,

376
00:49:37,490 --> 00:49:55,160
then there is an s and there is a team such that in configuration s at Square T, a zero is printed because S1 is zero.

377
00:49:55,160 --> 00:50:04,090
So that's saying there is some configuration and some square such that a zero is on the table.

378
00:50:04,090 --> 00:50:17,170
So here we have been the of number sequence conditions there, the piano stuff, we've got a description of a blank tape there.

379
00:50:17,170 --> 00:50:19,540
We thought a description of the quintuplets,

380
00:50:19,540 --> 00:50:33,070
they're about given the machine and and and here this is expressing the implication that that lot will produce a zero.

381
00:50:33,070 --> 00:50:35,230
If that formula is decided, well,

382
00:50:35,230 --> 00:50:45,640
then it is possible to have a Turing machine that will tell you whether an arbitrary charity machine will print to zero or not.

383
00:50:45,640 --> 00:50:57,160
And we know that's not possible. OK, so we nearly there there's a couple of lemons that Turing sets out to prove, which basically connect.

384
00:50:57,160 --> 00:51:02,470
What we can see already is is going to be the case.

385
00:51:02,470 --> 00:51:14,150
He's just proving that the prove ability of that formula does indeed correspond with the appearance of a zero on the tape.

386
00:51:14,150 --> 00:51:23,840
So his first memories is if someone one that is the zero appears on the tape in some complete configuration of him, then un and is provable, right?

387
00:51:23,840 --> 00:51:29,690
That's that formula that U.N. of M lImita.

388
00:51:29,690 --> 00:51:40,010
If UNM is provable, then this one does indeed appear on the tape in some complete configuration of him.

389
00:51:40,010 --> 00:51:47,870
This is somewhere where it would be good to go and look at the book, but I hope this will help you follow what's happening there.

390
00:51:47,870 --> 00:51:50,060
It's it's relatively straightforward.

391
00:51:50,060 --> 00:51:57,000
There are, you know, technical niceties there, but essentially what Turing is doing is formulating sequence of formulae.

392
00:51:57,000 --> 00:52:06,380
CC0 CC one, CC two etc representing the sequence of complete configurations as M proceeds,

393
00:52:06,380 --> 00:52:11,950
he uses an earlier abbreviation standing for this, which is part of the UN formula.

394
00:52:11,950 --> 00:52:19,670
You may recognise that he uses FN to abbreviate the numeric successive relations,

395
00:52:19,670 --> 00:52:26,480
and then he shows by induction that all formulae of that form are provable.

396
00:52:26,480 --> 00:52:32,450
You get the base case on Pages two, seven, two to three and the induction step two seven three to five.

397
00:52:32,450 --> 00:52:42,770
Essentially, the idea is that he's got this formula, which represents the sequence of configurations and CC zero,

398
00:52:42,770 --> 00:52:54,200
therefore is just the initial configuration, and you can see that that is indeed going to follow pretty trivially from this.

399
00:52:54,200 --> 00:52:59,750
The bits inside the square brackets, because that is that specifying the initial configuration.

400
00:52:59,750 --> 00:53:04,970
So not surprisingly, that's pretty trivial. That's the base case.

401
00:53:04,970 --> 00:53:10,910
I mean, because the formula contains all these quintuplets.

402
00:53:10,910 --> 00:53:21,260
It's been fairly straightforward to get from one configuration to the next one because if the configuration can contains the appropriate,

403
00:53:21,260 --> 00:53:32,240
if the complete configuration contains the appropriate trigger on the scan square, there is the right symbol and it's in the right state.

404
00:53:32,240 --> 00:53:44,810
Then the quintuple is going to apply and DSM will contain the formula, which leads to the following complete configuration being adjusted accordingly.

405
00:53:44,810 --> 00:53:50,270
So you can see how a proof by induction would go effectively simulating if you like,

406
00:53:50,270 --> 00:53:58,940
or mimicking the application of the Turing machine to the take stage after stage.

407
00:53:58,940 --> 00:54:06,980
So Lemma one follows because assuming that zero does indeed appear on the take in configuration and say, then CCN,

408
00:54:06,980 --> 00:54:14,600
which includes all relevant are a con. They're the con. That say what symbol appears on the tape,

409
00:54:14,600 --> 00:54:21,650
at which point that must include our S1 and for some square y.

410
00:54:21,650 --> 00:54:31,250
All right. So suppose, suppose configuration end, you know, one million three hundred sixty five thousand four hundred twenty nine,

411
00:54:31,250 --> 00:54:39,650
whatever it is, suppose at that point a zero does indeed get printed on the tape.

412
00:54:39,650 --> 00:54:48,110
And then that configuration that that formula, which which specifies the configure the complete configuration,

413
00:54:48,110 --> 00:54:59,180
will include an element like that specifying the appropriate square in which where a zero occurs.

414
00:54:59,180 --> 00:55:08,360
So it will be a trivial implication from that formula that zero is printed.

415
00:55:08,360 --> 00:55:15,380
The second Lemma, if undermines provable in this one, appears in some complete configuration,

416
00:55:15,380 --> 00:55:22,250
that must be true simply by substitution of appropriate prop propositional functions.

417
00:55:22,250 --> 00:55:27,720
So finally, we are in a position to show that the shadings problem cannot be solved.

418
00:55:27,720 --> 00:55:32,720
OK, now some of the stuff we've been through here is, as you see, very, very technical.

419
00:55:32,720 --> 00:55:35,210
Do not worry if you don't understand all of it,

420
00:55:35,210 --> 00:55:42,140
it's worth going and looking at the paper and pencils description to make sure that you've got the gist of it.

421
00:55:42,140 --> 00:55:44,750
But really, the most important thing is just to have the gist.

422
00:55:44,750 --> 00:55:52,520
Turing has shown how the properties of Turing machines can be encoded in predicate formulae.

423
00:55:52,520 --> 00:55:56,420
He's shown that a certain thing cannot be done with Turing machines,

424
00:55:56,420 --> 00:56:04,730
namely providing a reliable test for whether a zero is printed on a tape ever by some arbitrary jury machine.

425
00:56:04,730 --> 00:56:14,540
And he's provided a formula in predicate logic, which expresses that proposition that it is or is not printed.

426
00:56:14,540 --> 00:56:20,270
And he's then concluded, therefore, that that formula is not decided.

427
00:56:20,270 --> 00:56:24,830
So to sum up, the lemmer of Section eight proved that no machine can be constructed,

428
00:56:24,830 --> 00:56:31,010
which will reliably determine whether any specified machine will ever print zero.

429
00:56:31,010 --> 00:56:38,120
But since that behaviour, printing a zero or not can be captured by a predicate logic formula, you can.

430
00:56:38,120 --> 00:56:45,710
Then it follows that no machine can be constructed, which will reliably determine whether or not that formula is provable.

431
00:56:45,710 --> 00:56:55,580
Hence, the incidence problem to devise a mathematical procedure to determine whether or not any predicate logic formula is provable has no solution.

432
00:56:55,580 --> 00:57:06,290
And that is where we finish with Turing's 1936 paper on next time to the 1950 paper, which is much easier going.

433
00:57:06,290 --> 00:57:11,630
But I hope you've found the 1936 one of great interest.

434
00:57:11,630 --> 00:57:16,334
It does repay a lot of study. Thank you.