1 00:00:00,720 --> 00:00:08,190 OK, today we start on Turing's famous paper of 1936, very justly famous. 2 00:00:08,190 --> 00:00:17,520 The paper, which invented the Turing machine and showed that the shadings problem was unsolvable. 3 00:00:17,520 --> 00:00:23,280 We're going to be going through it with the help of Petzold book the annotated Turing, 4 00:00:23,280 --> 00:00:30,180 and I'll be referring to that quite a lot as we go now, as we saw last time. 5 00:00:30,180 --> 00:00:39,660 If you want to tackle the incidence problem, the decision problem, then you have to have some notion of effective computer ability. 6 00:00:39,660 --> 00:00:54,150 The idea is that there what cheering wants to show is that there is no effective procedure for deciding any proposition of predicate logic. 7 00:00:54,150 --> 00:01:03,210 And in order to get a handle on that, he has to be able to define what counts as an effective procedure. 8 00:01:03,210 --> 00:01:13,350 So what cheering does is he characterises effective computer ability in terms of the behaviour of an extremely simple kind of machine. 9 00:01:13,350 --> 00:01:19,590 And the claim is that this machine can execute either directly or indirectly 10 00:01:19,590 --> 00:01:24,660 all possible methods of mechanical information processing mechanical there. 11 00:01:24,660 --> 00:01:31,530 As I explained last time, means that you can specify exactly what each step should involve. 12 00:01:31,530 --> 00:01:36,150 No intuition, no strokes of genius. Nothing like that. 13 00:01:36,150 --> 00:01:44,010 Just following a rule, the machine is, of course, universally known as the Turing machine. 14 00:01:44,010 --> 00:01:49,770 So let's have a quick outline of the 1936 paper. 15 00:01:49,770 --> 00:01:57,060 So first of all, he defines the concept of a computable number, and he focuses on binary fractions. 16 00:01:57,060 --> 00:02:02,580 He sometimes calls these decimals. Unfortunately, we're going to call them by animals. 17 00:02:02,580 --> 00:02:11,640 OK, so the concept is a straightforward one. It's just like with with decimal fractions after the binomial point is, 18 00:02:11,640 --> 00:02:21,330 I'll call it the the next digit represents the number of halves, the next the number of quarters, eighths sixteenths and so on. 19 00:02:21,330 --> 00:02:27,330 So it's a very similar concept, except we're using binary rather than decimal. 20 00:02:27,330 --> 00:02:31,530 And what I'm hearing is going to show is that these numbers, 21 00:02:31,530 --> 00:02:38,640 these by minimal numbers between zero and one are more extensive than the algebraic numbers, 22 00:02:38,640 --> 00:02:44,550 and therefore there are more of them than there are algebraic numbers hints that are more of them than the raw, rational numbers. 23 00:02:44,550 --> 00:02:52,980 Or at least there are more in the sense that there are computable numbers, which are not algebraic. 24 00:02:52,980 --> 00:03:01,530 There are computable numbers which are not rational, though actually he's going to show that they are nevertheless innumerable. 25 00:03:01,530 --> 00:03:11,400 So in another sense, there are exactly the same number of binomial computable numbers as there are algebraic numbers. 26 00:03:11,400 --> 00:03:17,580 OK. And he's going to show that there are innumerable by showing that the machines that generate them are innumerable. 27 00:03:17,580 --> 00:03:29,370 OK. So he's got this simple machine. He's going to use those machines effectively to define the computable numbers. 28 00:03:29,370 --> 00:03:33,870 And then he's going to show that because the machines themselves are innumerable. 29 00:03:33,870 --> 00:03:39,750 It follows that the numbers are innumerable. OK. 30 00:03:39,750 --> 00:03:46,680 So in part one, section one of the paper, that's page 68 in Petzold book. 31 00:03:46,680 --> 00:03:55,290 So when you see page numbers, they're always referring to Petzold book, which of course, contains the the whole article by Turing. 32 00:03:55,290 --> 00:04:04,920 He explains the structure of the Turing machine. But first of all, we're going to talk about the justification of the Turing machine. 33 00:04:04,920 --> 00:04:16,350 So here's a quote from Turing. We have said that the computable numbers are those whose decimals by animals please are calculable by finite means. 34 00:04:16,350 --> 00:04:21,960 The justification lies in the fact that the human memory is necessarily limited. 35 00:04:21,960 --> 00:04:28,320 And here he refers to forward to section nine of the paper. Now I'm actually going to go to section nine now, 36 00:04:28,320 --> 00:04:34,980 so we're going to look at the justification for the Turing machine before we get into the technical details. 37 00:04:34,980 --> 00:04:39,630 And he's going to argue that his kind of machine, the Turing machine, 38 00:04:39,630 --> 00:04:46,920 really is capable of calculating anything that a human can calculate mechanically. 39 00:04:46,920 --> 00:04:57,930 That is OK. Computing is normally done by writing certain symbols on paper, we may suppose this paper is divided into squares. 40 00:04:57,930 --> 00:05:04,290 I assume then, that the. Tation is carried out on a tape divided into squares. 41 00:05:04,290 --> 00:05:09,300 I shall also suppose that the number of symbols which may be printed is finite. 42 00:05:09,300 --> 00:05:20,850 OK. This all makes sense, right? He's saying if we do a calculation, if a human does a calculation, we typically do it with working on paper. 43 00:05:20,850 --> 00:05:23,580 And he's claiming that without loss of generality, 44 00:05:23,580 --> 00:05:31,770 we can think of the paper is divided into squares and we can then think of those squares actually as laid out in a tape, a one dimensional tape. 45 00:05:31,770 --> 00:05:35,370 Now you might at this point object, you might say, but wait a minute, 46 00:05:35,370 --> 00:05:43,620 might there not be some calculations which you can carry out if you use two dimensional working space, but that you couldn't do on a tape? 47 00:05:43,620 --> 00:05:47,700 Well, put that to one side, actually, it's going to turn out. 48 00:05:47,700 --> 00:05:54,040 No, but we're not going to argue that here. 49 00:05:54,040 --> 00:06:05,890 The behaviour of the computer at any moment and notice that when Turing talks about a computer in 1936, he means a person doing a calculation. 50 00:06:05,890 --> 00:06:12,400 OK? A person employed to calculate things so the behaviour of the computers. 51 00:06:12,400 --> 00:06:20,500 Any moment is determined by the symbols which he is observing and his state of mind at that moment. 52 00:06:20,500 --> 00:06:28,660 We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at any one moment. 53 00:06:28,660 --> 00:06:34,300 We will also suppose that the number of states of mind which need be taken into account is finite. 54 00:06:34,300 --> 00:06:42,220 If we admitted an infinity of states of mind, some of them will be arbitrarily close and will be confused. 55 00:06:42,220 --> 00:06:56,200 OK, but that all makes reasonable sense. Imagine yourself calculating and at any point what you do will depend on where you are in the calculation. 56 00:06:56,200 --> 00:07:01,420 And that maps into a state of mind, you know, the state in which your mind is at that point. 57 00:07:01,420 --> 00:07:07,810 Bearing in mind what's happened before and also the symbols that you're looking at now. 58 00:07:07,810 --> 00:07:12,790 So you may be in the process of performing an addition. That's your state of mind. 59 00:07:12,790 --> 00:07:18,850 You're remembering where you are in the sum and then you look at a symbol and you act accordingly. 60 00:07:18,850 --> 00:07:23,440 And what you're saying is it's reasonable to suppose that you've only got a 61 00:07:23,440 --> 00:07:28,540 finite possible number of states of mind because if you had infinitely many, 62 00:07:28,540 --> 00:07:34,300 then some of those would be so close together that they could be confused. They'd be arbitrarily close. 63 00:07:34,300 --> 00:07:41,470 Okay, so all seems fairly plausible. It's this isn't a, you know, absolutely knockdown demonstrative argument, 64 00:07:41,470 --> 00:07:49,570 but it's a persuasive case that his machine is going to be able to do all the things that a human could do. 65 00:07:49,570 --> 00:07:53,380 At least, you know, it's a very strong preliminary case. 66 00:07:53,380 --> 00:08:00,100 It's not. It doesn't rule out that problems might be raised later. 67 00:08:00,100 --> 00:08:04,300 Okay. So the repertoire of operations that the computer can perform, 68 00:08:04,300 --> 00:08:13,470 that is the person performing the calculation or later the Turing machine is going to be precisely specified in terms of simple operations. 69 00:08:13,470 --> 00:08:19,600 So let us imagine the operations performed by the computer to be split up into simple operations. 70 00:08:19,600 --> 00:08:28,180 Every such operation consists of some change of the physical system consisting of the computer and his tape. 71 00:08:28,180 --> 00:08:34,030 We may suppose that in a simple operation, not more than one symbol is altered. 72 00:08:34,030 --> 00:08:42,370 We may, without loss of generality, assume that the squares whose symbols are changed are always observed squares. 73 00:08:42,370 --> 00:08:47,800 Okay, so you've got the computer. The person is doing the calculation on the tape. 74 00:08:47,800 --> 00:08:57,580 At any point, they're only able to observe a limited part of the tape and the that they are able to alter what's written on the tape. 75 00:08:57,580 --> 00:09:04,960 Only within the part that they're observing now during is saying that this is without loss of generality. 76 00:09:04,960 --> 00:09:13,600 Again, that's a little bit of a promissory note. He's not proved that, but it will in fact turn out to be the case. 77 00:09:13,600 --> 00:09:20,330 Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. 78 00:09:20,330 --> 00:09:28,210 In other words, changing the squares that you observe. The new observed squares must be immediately recognisable by the computer. 79 00:09:28,210 --> 00:09:33,250 It is reasonable to suppose that they can only be squares whose distance from the closest of 80 00:09:33,250 --> 00:09:38,800 the immediately preceding previously observed squares does not exceed a certain fixed amount, 81 00:09:38,800 --> 00:09:46,900 say L squares. And it may be that some of these changes necessarily involve a change of state of mind. 82 00:09:46,900 --> 00:09:53,830 Okay, so the computer has a long tape on which all the calculations are being carried out. 83 00:09:53,830 --> 00:09:58,960 He's able to change the squares that he observes, but only by a limited amount each time. 84 00:09:58,960 --> 00:10:05,050 So if you want to get from this part of the tape to this part, you may have to move by a number of stages. 85 00:10:05,050 --> 00:10:12,400 And as you are moving your obviously your your state of mind will change because your state of mind will 86 00:10:12,400 --> 00:10:17,530 have to record the fact that you are in the process of moving from one part of the tape to another. 87 00:10:17,530 --> 00:10:26,070 So the state of mind is crucial because that keeps track of what you were doing at each point. 88 00:10:26,070 --> 00:10:33,730 OK. The most general single operation must therefore be taken to be one of the following. 89 00:10:33,730 --> 00:10:39,330 A possible change of symbol. Together with a possible change of state of mind. 90 00:10:39,330 --> 00:10:46,050 The possible change of observed squares together with a possible change of state of mind. 91 00:10:46,050 --> 00:10:50,280 And then the actual operation that's performed. 92 00:10:50,280 --> 00:10:57,850 I mean, you know what changes of symbol? What changes of observed squares, what possible changes of mind? 93 00:10:57,850 --> 00:11:10,740 How are those to be specified? Well, sharing is going to say they depend purely on the current state of mind of the computer and the observed symbol. 94 00:11:10,740 --> 00:11:15,900 OK. So at any point in the calculation, 95 00:11:15,900 --> 00:11:25,890 all that determines the next thing to happen is the state of mind of the computer and the symbol on the observed square or squares. 96 00:11:25,890 --> 00:11:34,570 That's it. And the possible changes that can result from that of just these. 97 00:11:34,570 --> 00:11:42,810 OK, this is all quite abstract. It becomes easier to to see when we actually look at a Turing machine in operation. 98 00:11:42,810 --> 00:11:53,580 We may now construct a machine to do the work of this computer to each state of mind of the computer corresponds an M configuration of the machine. 99 00:11:53,580 --> 00:11:57,750 Okay, so I'm going to call end configuration a state. 100 00:11:57,750 --> 00:12:04,620 All right. And we'll see that the word configuration crops up quite a lot in Turing's paper, and he uses in different ways. 101 00:12:04,620 --> 00:12:11,220 So I'm generally going to talk about the state of the machine as what Turing calls the M configuration. 102 00:12:11,220 --> 00:12:17,040 The machine scans B squares corresponding to the B squares observed by the computer. 103 00:12:17,040 --> 00:12:23,280 In any move, the machine can change a symbol on a scanned square or can change any one of the scan squares 104 00:12:23,280 --> 00:12:28,350 to another square distant not more than L squares from one of the other scan squares. 105 00:12:28,350 --> 00:12:39,100 The move, which is done in the succeeding configuration, are determined by the scan symbol and the M configuration the state. 106 00:12:39,100 --> 00:12:51,580 Now, Turing is then going to say and he doesn't prove it, but he's right that you can actually simplify this model, 107 00:12:51,580 --> 00:13:01,150 you can actually insist that only one square is scanned at any time and that a movement up and down the tape has to be done. 108 00:13:01,150 --> 00:13:10,690 One cell at a time. So that's the kinds of machines that we're going to deal with and the kind of machines that 109 00:13:10,690 --> 00:13:17,110 he introduces early in the paper are actually a subset of the machines that he's just argued, 110 00:13:17,110 --> 00:13:23,380 give a generalisation of the mechanical possibilities of computation by a human computer. 111 00:13:23,380 --> 00:13:29,170 So basically, what we've got is is an argument. I won't call it a proof because I don't think it is a proof in section nine. 112 00:13:29,170 --> 00:13:36,490 But it's a plausible argument to say that any kind of calculation that can be mechanically specified 113 00:13:36,490 --> 00:13:43,600 in such a way that a human could carry it out can also be carried out by a Turing machine. 114 00:13:43,600 --> 00:13:47,140 OK, so what does the Turing machine comprise? 115 00:13:47,140 --> 00:13:55,990 You've got a potentially infinite type, and it's divided into numbered squares and you can write symbols on the squares. 116 00:13:55,990 --> 00:14:01,180 You can rub them out, you can erase them, or you can write new symbols on top. 117 00:14:01,180 --> 00:14:07,660 OK? You can only have one symbol on a square at any point and then you've got a read write head. 118 00:14:07,660 --> 00:14:12,220 I mean, most of you are too young, probably to remember tape recorders, 119 00:14:12,220 --> 00:14:22,990 but the the idea of a read write head is that when you write to the tape that happens purely on the square 120 00:14:22,990 --> 00:14:30,820 with that head is seated and the head moves up and down the tape reading as it goes and writing as he goes. 121 00:14:30,820 --> 00:14:39,310 And the only reading and writing can be done through that head at its current position so that can scan the symbols, 122 00:14:39,310 --> 00:14:42,640 and it can also write them or erase them. 123 00:14:42,640 --> 00:14:49,450 Then you've got the state, as I say, Turing calls it name configuration, which takes any of a specified finite range of values. 124 00:14:49,450 --> 00:14:57,270 And that's the active memory of the machine, and the computation always starts from the first initial state. 125 00:14:57,270 --> 00:15:04,870 And then you get instructions in the form of a machine table which tell it what to do in each possible circumstance. 126 00:15:04,870 --> 00:15:11,320 OK, so we're now going to see a Turing machine in action. 127 00:15:11,320 --> 00:15:23,890 Here we've got an example Turing machine. This is from Page 87 of Petzold book, and it's one that Turing himself put in the paper. 128 00:15:23,890 --> 00:15:29,260 And if this works, we're going to see it in action. Here we are. 129 00:15:29,260 --> 00:15:33,190 So this is this is the turtle system, which some of you may know. 130 00:15:33,190 --> 00:15:37,330 It's a system designed to teach programming. And in it, 131 00:15:37,330 --> 00:15:49,600 I've written a Turing Machine simulator and we've got a menu there with with five Turing machines corresponding to those in Pezzullo's book. 132 00:15:49,600 --> 00:15:54,740 OK, so here we've got the Turing machine. 133 00:15:54,740 --> 00:16:01,360 You can see it. It's working away and down. 134 00:16:01,360 --> 00:16:07,360 Here we've got the machine table. OK, so the end this is I'm copying Turing's layout here. 135 00:16:07,360 --> 00:16:18,460 We've got the end config. In other words, the state and I've numbered them for generality, but we've also got Turing's letters there and then. 136 00:16:18,460 --> 00:16:29,440 For example, if you're in state three and then if a zero is read from the tape, then these are the actions that you perform. 137 00:16:29,440 --> 00:16:36,940 You move, right? You prints an X and then you move rock again and you stay in state for it. 138 00:16:36,940 --> 00:16:43,300 If, on the other hand, you're in state three and you encounter a one on the tape, then you move, right? 139 00:16:43,300 --> 00:16:48,050 You print X right again, so you're doing exactly the same and you stay in the state. 140 00:16:48,050 --> 00:16:53,410 Three. So in fact, the the actions are exactly the same for a zero or a one. 141 00:16:53,410 --> 00:16:57,550 But if you encounter a blank, then instead. 142 00:16:57,550 --> 00:17:02,950 In other words, no symbol you move, right? You print Z. 143 00:17:02,950 --> 00:17:11,320 You move right again, right? Again, you print it hour and you go into a state force and you can see in state for the behaviours difference. 144 00:17:11,320 --> 00:17:15,790 And we've got not we've got the axe symbol there. 145 00:17:15,790 --> 00:17:20,350 That's the nearest you can get on a computer keyboard to the show-offs symbol, 146 00:17:20,350 --> 00:17:30,730 which is an upside down E. You'll see that coming in Turing's text, so I'm generally going to use in an act in these sorts of things. 147 00:17:30,730 --> 00:17:35,320 You've got the possibility of specifying a blank. None. 148 00:17:35,320 --> 00:17:36,540 And you've also got the possible. 149 00:17:36,540 --> 00:17:47,090 But as you've a kind of wild card, any, so if you're in state too and you encounter the Show-Off, you move right and you go Interstate three. 150 00:17:47,090 --> 00:17:52,130 If you encounter anything else, you move left in the same state, too. 151 00:17:52,130 --> 00:17:59,750 OK, so we can see what state two does. I mean, incident, you notice that the schwa symbol is right at the left of the table, 152 00:17:59,750 --> 00:18:03,890 and that switch cheering puts it is a sort of marker of the left of the tape. 153 00:18:03,890 --> 00:18:10,190 So you can see that if you're in state two and you're anywhere else in the tape, you're just going to go left left, 154 00:18:10,190 --> 00:18:18,260 left, left, left left until you encounter the schwa and then you will go right and go Interstate three. 155 00:18:18,260 --> 00:18:22,700 So that gives a simple example of how you can go through a tape, right? 156 00:18:22,700 --> 00:18:28,120 That's that's taking quite a long time, isn't it, actually? How can I do this? 157 00:18:28,120 --> 00:18:33,980 Let's see. And we know it's outputting at the bottom of the screen. 158 00:18:33,980 --> 00:18:40,590 You can see it's outputting all the. Hmm. 159 00:18:40,590 --> 00:18:54,660 Stephanie. And this is actually generating a number, which is probably a a transcendental number. 160 00:18:54,660 --> 00:18:56,580 It's certainly irrational. 161 00:18:56,580 --> 00:19:05,700 It's a number that goes zero one zero one one zero one one one zero one one one one more ones each time, and you can see it as a result. 162 00:19:05,700 --> 00:19:10,530 It's never recurring. OK, we'll come back to that. 163 00:19:10,530 --> 00:19:19,760 I'm going to escape from that now. 164 00:19:19,760 --> 00:19:26,600 So that should give you the idea of a Turing machine. Now another use of the word configuration. 165 00:19:26,600 --> 00:19:36,320 So here I am, going to stick with Turing's terminology. So when we talk about the configuration of a Turing machine, this is what we're going to mean. 166 00:19:36,320 --> 00:19:43,760 So at any point, the machine can scan only one square on the tape, which is, we'll call it the current square or the scan square. 167 00:19:43,760 --> 00:19:52,460 And as it moves left and right on the tape, one square at a time, the machine just scans that symbol, the symbol on the current square. 168 00:19:52,460 --> 00:19:58,910 And as we've seen, it can only take that into account in its behaviour in determining its next action. 169 00:19:58,910 --> 00:20:04,970 The only thing that matters? Well, the only things that matter of the state. 170 00:20:04,970 --> 00:20:11,450 What? What your ankles, the M configuration, the state of mind and the symbol on the current square. 171 00:20:11,450 --> 00:20:18,950 And this combination the M configuration and the scan symbol of a current configuration of the machine. 172 00:20:18,950 --> 00:20:27,680 So configuration is shorthand for those two things combined the state and the symbol. 173 00:20:27,680 --> 00:20:34,760 At each stage, depending on the configuration, the machine can either erase the symbol or write a new one can move. 174 00:20:34,760 --> 00:20:40,100 The scanning had one place left or right on the tape and can change to a new state. 175 00:20:40,100 --> 00:20:54,950 Those are the only things that it can do. Now, initially, as we saw in the machine just now again, if we go back to that machine number three, 176 00:20:54,950 --> 00:21:01,100 this one you can see in the table that sharing is allowing multiple actions here. 177 00:21:01,100 --> 00:21:06,380 Right? I mean, here in particular, we got the shaft move right print of schwa move, right? 178 00:21:06,380 --> 00:21:13,940 Zero right. Right print. Zero net flat. But a lot of actions taking place there later in the paper. 179 00:21:13,940 --> 00:21:20,030 CHEERING it is only going to allow a single type of each action at each step. 180 00:21:20,030 --> 00:21:29,300 That's going to prove to be very important in his argument because it gives a way of regimented all the possible types of Turing machine. 181 00:21:29,300 --> 00:21:34,310 And during the paper, you'll see that he sometimes goes one way, sometimes the other. 182 00:21:34,310 --> 00:21:40,190 In general, when he's explaining Turing machines and their power early on, he allows multiple actions. 183 00:21:40,190 --> 00:21:46,050 But then when he's doing his proof, he wants to restrict them. 184 00:21:46,050 --> 00:21:53,430 So it's as well to be aware of that. OK, section two of the paper, we get some definitions. 185 00:21:53,430 --> 00:22:00,270 Turing is going to focus on automatic machines, though he mentions choice machines in passing. 186 00:22:00,270 --> 00:22:04,290 Any machine is going to have a limited range of symbols that it can read and write, 187 00:22:04,290 --> 00:22:08,880 and Turing is going to distinguish between what he calls figures digits, 188 00:22:08,880 --> 00:22:17,430 zero and one and other symbols, which he calls symbols of the second kind, which basically can be any letter of a schwa or whatever. 189 00:22:17,430 --> 00:22:27,720 OK. And the crucial point here is remember that Turing is interested in computable numbers, in particular computer bull by animals. 190 00:22:27,720 --> 00:22:38,130 So he is interested in fractional binary numbers, which consist after the binomial point of a sequence of zeros and ones. 191 00:22:38,130 --> 00:22:45,090 So zero and one, especially when they get printed on a tape in general, they are not going to be erased. 192 00:22:45,090 --> 00:22:47,250 They are going to be there for good. 193 00:22:47,250 --> 00:22:55,950 And Turing is going to build up these by animal numbers by adding one after another, figure zeros or ones again and again. 194 00:22:55,950 --> 00:23:07,620 Meanwhile, the other symbols are going to be used for working. So he explains that his machines will write figures only on alternate squares, 195 00:23:07,620 --> 00:23:15,180 so the figures that is the digits zero in one will only be written on what he calls squares and the intermediate squares. 196 00:23:15,180 --> 00:23:22,140 The alternate squares are going to be used for working. He calls them E squares, probably erasable. 197 00:23:22,140 --> 00:23:25,380 So we then get a clarification here. 198 00:23:25,380 --> 00:23:30,810 If a symbol beta is on an f square s and a simple symbol, 199 00:23:30,810 --> 00:23:41,400 Alpha is on the square next on the right of s then s and beta will be said to be marked with alpha. 200 00:23:41,400 --> 00:23:47,670 The process of printing this alpha will be called marking beta four s with an alpha. 201 00:23:47,670 --> 00:23:54,270 So that's it. That's a quote from the end of Section three. Okay, so we'll see an example of that in a moment. 202 00:23:54,270 --> 00:24:00,790 If you find that little bit confusing, it'll become very clear. 203 00:24:00,790 --> 00:24:07,900 So an automatic machine, as Turing is going to consider them, starts from an absolutely blank tape in its initial state. 204 00:24:07,900 --> 00:24:14,560 If you come across Turing machine programmes and things on the web, you'll often find that they don't start with a blank tape. 205 00:24:14,560 --> 00:24:18,520 You can define, for example, a cheering machine that will multiply two numbers. 206 00:24:18,520 --> 00:24:22,810 And you may need to start out with those numbers written on the tape. 207 00:24:22,810 --> 00:24:32,630 So if you multiply, if you want to multiply three times four, for example, you'll start off with one one one zero one one one one zero. 208 00:24:32,630 --> 00:24:38,080 You've got three and four on the tape effectively. And then you set the machine going and it multiplies them. 209 00:24:38,080 --> 00:24:43,750 Okay? Turing's machines aren't like that. He starts from an absolutely blank tape, 210 00:24:43,750 --> 00:24:52,690 and the machine is going to generate everything that comes onto the tape without any initial input from the tape itself. 211 00:24:52,690 --> 00:25:01,030 OK. And the machines he's interested in are going to generate a sequence of digits, a sequence of figures, zeros and ones. 212 00:25:01,030 --> 00:25:05,800 And that sequence is called the sequence computed by the machine. 213 00:25:05,800 --> 00:25:13,540 The real number, whose expression as a binary decimal sic there is saying, Look, that's the way Turing says it. 214 00:25:13,540 --> 00:25:22,540 It's not the way I would say it. I would say whose expression is a binomial is obtained by perfect facing this sequence by a decimal point. 215 00:25:22,540 --> 00:25:28,690 A binary point, please, is called the number computed by the machine and insurance machines. 216 00:25:28,690 --> 00:25:35,890 The binary digits of this number are supposed to be printed left to right on successive f squares and never erased. 217 00:25:35,890 --> 00:25:41,080 So let's just take a look at part of the tape while this is going on. 218 00:25:41,080 --> 00:25:50,590 OK, you've got the schwa symbols on the left and upside down in, say, I'm representing those by and by an at symbol when, when the programme runs. 219 00:25:50,590 --> 00:25:56,470 These are figures written on f squares. Alternate squares, notice the zeros and ones. 220 00:25:56,470 --> 00:26:05,470 You only write zeros and ones on those squares, and then in between those squares you've you're allowed to write other symbols like X. 221 00:26:05,470 --> 00:26:10,810 And we say that the one here is marked with that X. 222 00:26:10,810 --> 00:26:23,530 OK. So you can see how a symbol written on one of the erasable squares marks the adjacent square to the left? 223 00:26:23,530 --> 00:26:34,330 OK. So in this case, the computed number that's being shown so far is zero zero one zero one one zero. 224 00:26:34,330 --> 00:26:44,380 Now, the machines that Turing is interested in are machines that go on writing digits forever. 225 00:26:44,380 --> 00:26:55,780 OK. And this can be a little bit confusing. A Turing machine that carries on writing out binary digits forever in this way is called circle free. 226 00:26:55,780 --> 00:27:08,650 These define computable numbers. OK, bear in mind, we're interested in in by animals non terminating by by animals, you might say. 227 00:27:08,650 --> 00:27:15,460 Well, what about those that terminate? Well, if they terminate, then it's just zero zero zero zero zero zero on forever. 228 00:27:15,460 --> 00:27:22,690 That's fine. OK. So what we think of as a non terminating by animal is in sorry, 229 00:27:22,690 --> 00:27:33,520 the terminating by animal is in fact the same as a non terminating by animal that just has zeros at the end forever. 230 00:27:33,520 --> 00:27:39,310 And Turing is going to call a number that defined such a circle machine free machine a satisfactory number. 231 00:27:39,310 --> 00:27:46,840 So the satisfactory Turing machines, the one that Turing is happy with all the ones that go on printing forever. 232 00:27:46,840 --> 00:27:53,710 He calls these circle free and one that stops writing out binary digits. 233 00:27:53,710 --> 00:27:56,950 He calls circular. Now this seems a little unnatural to us. 234 00:27:56,950 --> 00:28:04,930 All right. We think of a a circular programme, if you like, as precisely as one that goes on forever, that gets into a loop. 235 00:28:04,930 --> 00:28:14,980 So you need to put that thought out of your mind. Right? And a circular Turing machine is one that gets into a loop. 236 00:28:14,980 --> 00:28:27,170 This is not printing figures. That stops printing zeros and ones, where is a certain free one is one that carries on printing zeros and ones. 237 00:28:27,170 --> 00:28:31,190 So the name of the game is to produce an infinite volume. Okay. 238 00:28:31,190 --> 00:28:38,990 During is interested in the number that is generated by a machine, and those numbers go on forever. 239 00:28:38,990 --> 00:28:42,740 Of course, in practise, you'd never be able to display a tape with that. 240 00:28:42,740 --> 00:28:49,990 But the point is that the number is defined by the machine. OK. 241 00:28:49,990 --> 00:28:57,340 We're now going to get another use of the word configuration, this time the complete configuration at any stage of the motion of the machine. 242 00:28:57,340 --> 00:28:59,080 The number of the scanned square. 243 00:28:59,080 --> 00:29:08,080 The complete sequence of all symbols on the tape and the M configuration, the state will be said to define describe the complete configuration. 244 00:29:08,080 --> 00:29:19,180 At that stage, the changes of the machine and take between successive complete configurations will be called the moves of the machine. 245 00:29:19,180 --> 00:29:26,830 OK, so suppose you are computing something following the instructions of the Turing machine. 246 00:29:26,830 --> 00:29:31,270 OK, put yourself in the position of the Turing machine. 247 00:29:31,270 --> 00:29:38,290 So you have this tape, you're carrying out the operations in exactly the way prescribed. 248 00:29:38,290 --> 00:29:47,530 And then the dinner bell rings. Or you've got to go to a lecture and you've got to put everything away. 249 00:29:47,530 --> 00:29:57,280 You want to come back to your calculation and you want to be able to continue your calculation from exactly the point that you stopped it. 250 00:29:57,280 --> 00:30:03,280 What information do you need to record in order to be able to continue in the same way? 251 00:30:03,280 --> 00:30:09,160 Well, you need to record the complete configuration, right? You need to record everything on the tape. 252 00:30:09,160 --> 00:30:14,710 You need to record where you are on the tape and you need to record your current state. 253 00:30:14,710 --> 00:30:23,230 Yeah. And as long as you do that and you start again, you know, using the same machine table, everything will go fine. 254 00:30:23,230 --> 00:30:31,930 You can interrupt as much as you like as long as you always record the complete configuration and then when you come back, restore it. 255 00:30:31,930 --> 00:30:40,730 Okay. So you can think of the complete configuration as showing the the state of the entire calculation at any point. 256 00:30:40,730 --> 00:30:49,330 OK, that's a lot of setting up. Let's now look at some examples of machines. 257 00:30:49,330 --> 00:31:01,820 That is the binomial number for one third. OK, let's let's look at some machines that generate that. 258 00:31:01,820 --> 00:31:05,270 Here's one you can see it's just printing out. 259 00:31:05,270 --> 00:31:10,760 Zero one zero one zero one. And so on forever. 260 00:31:10,760 --> 00:31:16,910 How does it do it when it starts in state one, it encounters no symbol on the tape. 261 00:31:16,910 --> 00:31:25,010 Of course, it's a completely blank tape to start with. It prints the zero and moves right interstate to. 262 00:31:25,010 --> 00:31:32,860 In state, too, of course, it encounters the blank again. It moves right and goes, Interstate three doesn't print anything. 263 00:31:32,860 --> 00:31:36,640 But that means we've now had to move to the right in state. 264 00:31:36,640 --> 00:31:42,250 Three. It proves one and moves right and goes Interstate four. 265 00:31:42,250 --> 00:31:47,080 And then in state four, it moves right. Doesn't print anything and goes into state one. 266 00:31:47,080 --> 00:31:51,640 And we're back where we started. OK, very simple machine. 267 00:31:51,640 --> 00:31:56,200 You can see it is generating the by animal for one third. 268 00:31:56,200 --> 00:31:58,600 So one third is therefore a computable number. 269 00:31:58,600 --> 00:32:08,690 You can specify a machine which will generate the infinite sequence of digits that make up the Baynham over one third. 270 00:32:08,690 --> 00:32:17,470 OK. Let's look at another machine that generates the same thing. 271 00:32:17,470 --> 00:32:29,710 So notice here we've got multiple operations. We've actually only got a single state here in that state if it encounters no symbol at all. 272 00:32:29,710 --> 00:32:39,580 Blank, it prints a zero. Stays in the same state, of course, there is only one state if it encounters a zero. 273 00:32:39,580 --> 00:32:44,080 It's just sprinted to zero, hasn't it? So second time around, it doesn't count for zero. 274 00:32:44,080 --> 00:32:50,530 It moves right to spaces and free zone. And again, it stays in the same state. 275 00:32:50,530 --> 00:32:58,600 If you can count as a one, it moves right to places and prints zero and again stays in the same state. 276 00:32:58,600 --> 00:33:03,460 And from then on, he just alternates between these two that are right. 277 00:33:03,460 --> 00:33:14,500 So if you want to print the binding for a third and you don't mind cheating by having more than one operation for a given configuration, 278 00:33:14,500 --> 00:33:18,510 you can do that. All right. Okay, so. 279 00:33:18,510 --> 00:33:23,200 So that's why we've got two different machines here that print that by animal. 280 00:33:23,200 --> 00:33:32,230 One of them is in the sort of strict form of the Turing machine, where you've only got one Operation PC configuration. 281 00:33:32,230 --> 00:33:41,800 One of them is in the abbreviated form. So that simply says what I'm asking you, 282 00:33:41,800 --> 00:33:50,410 and you can nicely illustrator Turing machines by these kinds of arrow diagrams you can see we've got that's the first state second, 283 00:33:50,410 --> 00:34:00,280 third and fourth, and Turing gives them these letters. He uses a gothic font for these letters, which can sometimes be quite difficult to read. 284 00:34:00,280 --> 00:34:05,440 I'm going to use this this font when I'm reproducing those. 285 00:34:05,440 --> 00:34:11,620 But he chooses letters which have a sort of mnemonic quality like beginning. 286 00:34:11,620 --> 00:34:18,610 So here you can see in the first state it prints are zero means right, then that puts it in the second state. 287 00:34:18,610 --> 00:34:26,350 It then moves right again, beats one and moves right, moves right again and so on. 288 00:34:26,350 --> 00:34:35,470 OK. And this shows a simplified table where we're allowing multiple operations with a single configuration, 289 00:34:35,470 --> 00:34:42,320 so that's the table for the simplified cheering machine we've just seen. 290 00:34:42,320 --> 00:34:49,550 OK. Then we get the more complex example that we've actually already seen. 291 00:34:49,550 --> 00:35:02,270 It's a number in which we get zero occurring and then between each pair of zeros, we get an ever increasing sequence of ones. 292 00:35:02,270 --> 00:35:06,830 It's a nice example because it shows straight away. 293 00:35:06,830 --> 00:35:10,100 Here is a number that clearly is irrational. 294 00:35:10,100 --> 00:35:20,310 We saw that any rational number, any number that can be written is a fraction of integers has to be a recurring decimal or binomial. 295 00:35:20,310 --> 00:35:27,110 And this never occurs. You can see that straight away. OK, yeah. 296 00:35:27,110 --> 00:35:35,150 I mentioned just in passing that on Turing's tapes, he always puts two schwa characters at the very left. 297 00:35:35,150 --> 00:35:43,850 And when you get two blanks, always indicates that you're at the the other end. 298 00:35:43,850 --> 00:35:49,060 OK, so if we look at. 299 00:35:49,060 --> 00:35:58,990 This, for example, the way Turing is going to work, set these out in the main part of the paper, he always got to Schwab characters at that end. 300 00:35:58,990 --> 00:36:06,800 And whenever you encounter two spaces together, that is going to be an indicator that you're at the right hand end of the tape. 301 00:36:06,800 --> 00:36:15,340 Okay, so he's going to make sure that you never get two blanks in a row in general, except then. 302 00:36:15,340 --> 00:36:24,580 OK, so here we've got the the one that's generating that transcend number two shows here. 303 00:36:24,580 --> 00:36:34,780 There's the table and it's going about its business. I'm not going to explain in detail how that works, but take a look at the paper. 304 00:36:34,780 --> 00:36:49,210 It's pages and you'll see, OK? Right now, touring illustrates the working of that machine with a sequence of complete configurations. 305 00:36:49,210 --> 00:36:52,300 This is going to turn out to be very important. 306 00:36:52,300 --> 00:37:01,180 We saw that a complete configuration is the kind of record that you'd keep if you interrupted your work and then wanted to come back later. 307 00:37:01,180 --> 00:37:08,950 It tells you everything about the current state of your calculation and what cheering he's going to do then, 308 00:37:08,950 --> 00:37:14,020 is actually end up listing these as a record of the calculation. 309 00:37:14,020 --> 00:37:23,200 So if you take a look at this format here, what you've got is between the colons. 310 00:37:23,200 --> 00:37:27,670 You've got a sequence of complete configurations and the what the complete 311 00:37:27,670 --> 00:37:35,170 configuration shows is the current state at each point and what is on the tape. 312 00:37:35,170 --> 00:37:44,860 So here what we've got is schwa schwa zero and the state name that is showing where on the tape we currently are. 313 00:37:44,860 --> 00:37:53,380 Sorry about schwa Chuck Schwab zero, space zero and the the oh, that is showing that we're in state. 314 00:37:53,380 --> 00:38:05,470 So at that point, then here we've got Schwab one zero, space zero and now we're in state queue at that point. 315 00:38:05,470 --> 00:38:08,980 Okay. This format is flanked this. 316 00:38:08,980 --> 00:38:15,430 See, this is we're going to come back and look at that later. And I mentioned the two pages in Petzold. 317 00:38:15,430 --> 00:38:27,790 If you go and look at Page 92 and then look at Page 144, you'll see that this format is referred to later in the paper and becomes very important. 318 00:38:27,790 --> 00:38:40,030 OK, now to familiarise yourself with how Turing machines work, go and see Chapter six of Petzold and read that through some of it's quite tricky, 319 00:38:40,030 --> 00:38:45,340 but by the time you've got through it, you will understand pretty well how they work. 320 00:38:45,340 --> 00:38:55,010 Petzold gives a couple of examples which I'm going to show you here, and this is the binary counting one. 321 00:38:55,010 --> 00:39:07,600 So what this is doing is generating binary numbers in sequence. It's not like Turing machines, it's printing the digits on adjacent squares. 322 00:39:07,600 --> 00:39:12,730 And you might notice that the take is moving backwards rather than forwards. OK, 323 00:39:12,730 --> 00:39:22,300 so it's not meant to illustrate exactly Turing convention machines that is machines that conform to the conventions that Turing uses in this paper. 324 00:39:22,300 --> 00:39:32,680 But what it's doing is it's giving a nice example of how you can do more interesting things with Turing machines. 325 00:39:32,680 --> 00:39:38,830 And what I really like, I have to say, I think it's really clever. 326 00:39:38,830 --> 00:39:47,440 So this is a Turing machine for calculating the square root of two in binomial. 327 00:39:47,440 --> 00:40:00,040 Now it's going to take a long time. So what I'm going to do if this will work is click the good. 328 00:40:00,040 --> 00:40:08,950 I had this running two million steps this morning and generated, I think it was 34 by animal digits of the square to two. 329 00:40:08,950 --> 00:40:13,280 And I checked it and it was right. 330 00:40:13,280 --> 00:40:21,040 Well, you know, when I multiplied by it, by itself, I got lots of ones indicating that it's getting very, very close. 331 00:40:21,040 --> 00:40:28,070 You know, it's square is very close to to to. 332 00:40:28,070 --> 00:40:37,070 Very clever. I mean, there's a lot at stake. That's not the whole table. But I can confirm the petzold is right. 333 00:40:37,070 --> 00:40:42,410 His machine actually works. And one of the nice things that we can do, that cheering, of course, 334 00:40:42,410 --> 00:40:51,200 couldn't do is actually run simulations of the various machines and check that they do work. 335 00:40:51,200 --> 00:40:58,130 That it turned out that there were various misprints in Turing's paper which are mentioned in Petzold, 336 00:40:58,130 --> 00:41:04,220 but there are no misprints in Petzold specification of this machine. 337 00:41:04,220 --> 00:41:17,840 OK. Now, before finishing this lecture, I want to introduce you to something which is, 338 00:41:17,840 --> 00:41:23,000 I suspect, one of the most difficult things to understand about Turing's paper. 339 00:41:23,000 --> 00:41:32,420 So when you go on to Section four and you look at the abbreviated tables there, you might initially find them extremely puzzling. 340 00:41:32,420 --> 00:41:38,840 So I'm going to take you through an example, and I hope having gone through that example, 341 00:41:38,840 --> 00:41:42,380 it will help you to understand all the others that are introduced there as well. 342 00:41:42,380 --> 00:41:51,830 Okay. So Section four, it's it's a very important part of the paper, but quite difficult when you come to it first time. 343 00:41:51,830 --> 00:42:00,830 So he uses what he calls skeleton tables to define Turing machines or to define part of the activity of Turing machines. 344 00:42:00,830 --> 00:42:04,040 And these make use of M functions, as he calls them, 345 00:42:04,040 --> 00:42:12,980 which enable many different end configurations that is status to be defined that have very similar behaviour, but with slight differences. 346 00:42:12,980 --> 00:42:20,510 So, for example, we might want our machine to do more or less the same thing, but on different symbols, 347 00:42:20,510 --> 00:42:26,540 sometimes on zero, sometimes on one, sometimes on alpha, sometimes on beta and so on. 348 00:42:26,540 --> 00:42:37,100 And so in order to do that, what we want is to equip our Turing machine with a number of states which fall into a common pattern. 349 00:42:37,100 --> 00:42:41,150 So we might have to say three states which we use to handle alpha. 350 00:42:41,150 --> 00:42:50,210 Another three states very similarly defined, but with beta instead of alpha and so on. 351 00:42:50,210 --> 00:42:54,410 So let's take a look at the M function fine. 352 00:42:54,410 --> 00:43:02,570 So this is the first one that's introduced. OK. So when you when you see these things right, that's quite puzzling. 353 00:43:02,570 --> 00:43:10,220 You think what on earth is going on here? I thought M configs were meant to be simple things like letters or maybe numbers. 354 00:43:10,220 --> 00:43:14,660 But now we've got some complicated function as an m config. 355 00:43:14,660 --> 00:43:17,360 How does that work? 356 00:43:17,360 --> 00:43:29,660 OK, here's the most important thing when you see something like this, remember that in any particular case, those are just ordinary states. 357 00:43:29,660 --> 00:43:35,240 What this is doing is describing the state in a in functional terms. 358 00:43:35,240 --> 00:43:43,880 So that might be state 314, 315 316. 359 00:43:43,880 --> 00:43:47,570 But suppose we want to remember, we want to keep a note for ourselves. 360 00:43:47,570 --> 00:44:01,430 What is it exactly that state 314 does? Oh, that's the state that searches for an alpha. 361 00:44:01,430 --> 00:44:09,460 And if Alpha is found, it goes into State C. 362 00:44:09,460 --> 00:44:17,400 And if an alpha is not found, it goes into State B, OK, that's what state 314 does. 363 00:44:17,400 --> 00:44:24,910 Oh, how does it do it? Well, it does it by using state 315 and 316, what do they do? 364 00:44:24,910 --> 00:44:31,960 Oh, don't worry about what they do, but they're just defined like that with C and B substituting accordingly. 365 00:44:31,960 --> 00:44:41,440 Got that! So what we've got here is a pattern which we can use to add three new states into our Turing machine. 366 00:44:41,440 --> 00:44:48,220 And if we define them like this with C and B and Alpha appropriately substituted, 367 00:44:48,220 --> 00:44:54,970 then that gives us a means within our Turing machine of performing that find operation to repeat, 368 00:44:54,970 --> 00:45:03,610 find an alpha on the tape if it is found going to state C if it isn't found going to state B. 369 00:45:03,610 --> 00:45:09,170 In fact, it searches for the left most alpha symbol, as you see at the bottom. 370 00:45:09,170 --> 00:45:17,260 Okay, so let's see how that works then. Rather than using the table, it's much easier with a diagram. 371 00:45:17,260 --> 00:45:21,610 So I've said this could be state 314 353Nm 16. 372 00:45:21,610 --> 00:45:26,320 It doesn't matter, right? 373 00:45:26,320 --> 00:45:38,350 But let's suppose that we got three states that have been defined according to that skeleton table for some particular values of Alpha B and C. 374 00:45:38,350 --> 00:45:45,250 Okay, so we go into this state, remember that's just a state, right? I know it's got a complicated functional label there. 375 00:45:45,250 --> 00:45:56,950 That doesn't mean it's a complex thing. It's just a state state 314. If in that state it can count as anything other than a schwa, then it goes left. 376 00:45:56,950 --> 00:46:00,820 Just the machine moves left and stays in the same state. 377 00:46:00,820 --> 00:46:05,590 So it goes left, left, left, left, left, left, left left until it encounters a schwa. 378 00:46:05,590 --> 00:46:09,910 When it encounters Ishwar, it goes left and goes into this other state. 379 00:46:09,910 --> 00:46:20,620 315 state 315 has been defined in such a way that if an alpha is found, it goes into State C. 380 00:46:20,620 --> 00:46:30,660 Remember State C in some other state that we've already got, that's the state we want to move into when we find the leftmost alpha. 381 00:46:30,660 --> 00:46:38,560 And if you didn't cancel blank, it goes into this state, which states a 360. 382 00:46:38,560 --> 00:46:49,890 If it encounters anything else, it moves right. OK, so apart from this complication about encountering a blank when the machine is in this state, 383 00:46:49,890 --> 00:46:52,010 it goes right, right, right, right, right, right, right. 384 00:46:52,010 --> 00:47:01,770 Until it encounters an alpha and when it encounters an alpha, it goes into State C at that point said, OK, let's now deal with this thing. 385 00:47:01,770 --> 00:47:13,470 What's this all about? Well, remember that we might go right the way through the tape, right to the end without ever finding an alpha. 386 00:47:13,470 --> 00:47:20,430 How do we know that we're at the right hand end of the tape? Answer two blanks in a row. 387 00:47:20,430 --> 00:47:28,260 How do we test for two blanks in the row? Well, if we find one blank, none, we go into this intermediate state. 388 00:47:28,260 --> 00:47:36,510 And then if we find another blank, OK, we know we're at the right hand into the tape going to state B if we find anything else. 389 00:47:36,510 --> 00:47:42,930 If we've only had one blank, not two in a row, go back to that state. So all right, everyone. 390 00:47:42,930 --> 00:47:45,000 Happy. Good. 391 00:47:45,000 --> 00:47:55,320 So this is I say, this is extremely confusing when you first look at it because you naturally think that this means the thing is very complicated. 392 00:47:55,320 --> 00:48:04,110 It's not. That's just a label that is saying this is the state which has the function of searching for the leftmost alpha on the tape. 393 00:48:04,110 --> 00:48:07,170 If it finds it, it goes into State C at that point. 394 00:48:07,170 --> 00:48:16,890 If it doesn't find having gone right right to the far right it goes into state B and C B, an alpha can be anything you like, right? 395 00:48:16,890 --> 00:48:28,500 OK. So again, note that these are just functional labels for the three states whose behaviour specified here these 19 states 314, 396 00:48:28,500 --> 00:48:34,980 315 316 say of the relevant machine. But the point is that when the first of them is entered, 397 00:48:34,980 --> 00:48:40,830 the machine will either find the leftmost alpha on the tape and Interstate C on the square or fail to 398 00:48:40,830 --> 00:48:45,870 find an alpha and then to state the on the square to the right of the 32 blanks at the right handed. 399 00:48:45,870 --> 00:48:55,080 Okay, so that specifies exactly what's going on now when you go through that chapter, having understood this one, 400 00:48:55,080 --> 00:49:00,300 I hope you will find that the other skeleton tables are pretty straightforward as well. 401 00:49:00,300 --> 00:49:05,640 You do not need to understand absolutely every detail of how these work. 402 00:49:05,640 --> 00:49:12,990 But it is very, very important that you go and look at them and get a feel for the various operations that are being defined there 403 00:49:12,990 --> 00:49:19,770 and at least go in detail through enough of them to give you confidence that you could understand the rest. 404 00:49:19,770 --> 00:49:25,350 OK. And on that note, I'll finish today and we'll look more at this next time. 405 00:49:25,350 --> 00:49:31,588 Thank you.