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.