Turing 2018/4: Enumerating the Computable Numbers, and the Universal Turing Machine

1
00:00:01,140 --> 00:00:10,200
In the last lecture we saw both for the Turing machine is and we saw something of what a Turing convention machine is,

2
00:00:10,200 --> 00:00:18,930
a Turing convention machine is a Turing machine in which we follow the conventions that Turing does in his 1936 paper,

3
00:00:18,930 --> 00:00:29,190
like putting Schwab's at the left hand end of the tape and writing figures in double digits on alternate squares and that sort of thing.

4
00:00:29,190 --> 00:00:40,620
We also saw briefly at the end, a sort of subroutine that you can have within a Turing machine.

5
00:00:40,620 --> 00:00:49,050
And we saw how this provided a general recipe for adding functions to a Turing machine.

6
00:00:49,050 --> 00:00:52,020
Turing does it in the way of skeleton tables.

7
00:00:52,020 --> 00:01:06,690
We've got a diagram here just to remind you this is implementing a find function where you can choose two states here and C and B and a symbol alpha.

8
00:01:06,690 --> 00:01:14,220
And what this does is it searches for the leftmost alpha on the tape.

9
00:01:14,220 --> 00:01:18,630
If one is found, it goes into State C at that point.

10
00:01:18,630 --> 00:01:29,760
And if none is found and gets to the right hand end of the tape, the two spaces two empty squares which mark the right hand end of the tape.

11
00:01:29,760 --> 00:01:34,830
Then it ends up in State B. And remember the crucial point?

12
00:01:34,830 --> 00:01:41,010
I emphasised that you mustn't think of this state as some funny beast.

13
00:01:41,010 --> 00:01:46,500
This is just a label for it. OK? It is just a state like any other.

14
00:01:46,500 --> 00:01:49,830
But this is a functional description of it.

15
00:01:49,830 --> 00:01:58,500
It says this is the state whose role is to search for an alpha to go into State C if an alpha is found and to go into State B,

16
00:01:58,500 --> 00:02:02,760
if not, so it gives us a general recipe.

17
00:02:02,760 --> 00:02:07,170
We might end up adding lots and lots and lots of states like this.

18
00:02:07,170 --> 00:02:12,000
You know, we've got three new states here that we've introduced for this purpose here.

19
00:02:12,000 --> 00:02:18,750
We might do it for lots of different symbols and we might do it for lots of different pairs of states that we want it to go into,

20
00:02:18,750 --> 00:02:21,120
depending whether something is found or not.

21
00:02:21,120 --> 00:02:28,740
Every time we have another instance, we're going to have to introduce three new states into our Turing machine, but we can do that as much as we like.

22
00:02:28,740 --> 00:02:36,270
And this imposes a sort of order on it. It makes it comprehensible what's going on.

23
00:02:36,270 --> 00:02:42,990
So here is a summary of the function of this here.

24
00:02:42,990 --> 00:02:50,820
I've just reduced to a single state. I'm ignoring the other two states that are added to enable this to work.

25
00:02:50,820 --> 00:02:58,230
We can simplify and just think, well, this if we add a state like this, then if an al.4 exists,

26
00:02:58,230 --> 00:03:04,410
it's going to move to the square containing the less most alpha and Interstate S. And if no alpha exists,

27
00:03:04,410 --> 00:03:09,660
it will move to the square after the two blanks at the right and go into state B.

28
00:03:09,660 --> 00:03:20,820
Okay, so that's that's the way to think of it. The the other two states are just there in order to enable this functionality to be achieved.

29
00:03:20,820 --> 00:03:25,620
Okay, we're now going to see quite a lot of these Turing skeleton tables.

30
00:03:25,620 --> 00:03:29,790
I haven't given you all of them here. I've chosen a representative sample.

31
00:03:29,790 --> 00:03:35,940
If you read Petzold, you'll see all the others. And I do give a list of them later in the lecture.

32
00:03:35,940 --> 00:03:44,010
But once you've got the general idea, it should be relatively straightforward to see how these things would work.

33
00:03:44,010 --> 00:03:59,040
So here is erase once. So this is a this is a function which finds the leftmost alpha and then erases it.

34
00:03:59,040 --> 00:04:05,430
OK. How does it work? Well, you can see here that it's very simple.

35
00:04:05,430 --> 00:04:12,600
It doesn't take any account of the symbol that's there at the time.

36
00:04:12,600 --> 00:04:17,430
It doesn't do any special behaviour. It doesn't move left or right or print anything.

37
00:04:17,430 --> 00:04:27,960
All it does is go straight into this state. OK, so here we have to have another new state in our machine, which plays this functional role.

38
00:04:27,960 --> 00:04:35,790
So notice this is using the find function. So it is looking for the leftmost alpha.

39
00:04:35,790 --> 00:04:44,790
If it finds the leftmost alpha, then it goes into this state, which is this one here, which is about to be defined.

40
00:04:44,790 --> 00:04:54,030
Otherwise it goes into State V as before. So assuming it finds an alpha, it goes to the left most alpha and he raises it.

41
00:04:54,030 --> 00:05:00,330
In other words, it prints of blank on that square and then goes into State C so that I can.

42
00:05:00,330 --> 00:05:07,470
So Turing is using the find function here to define an erase function.

43
00:05:07,470 --> 00:05:14,550
And again, in order to implement this, you can see you, you need two new states.

44
00:05:14,550 --> 00:05:21,810
So for any, any time you want to include some kind of erase function like this,

45
00:05:21,810 --> 00:05:27,330
you need to add two states to your Turing machine and you give them this behaviour.

46
00:05:27,330 --> 00:05:33,030
And there you have it. Okay, so Turing defined two versions of this.

47
00:05:33,030 --> 00:05:42,180
This is a version that you can see has three arguments, and we'll see that there's another as well.

48
00:05:42,180 --> 00:05:48,330
That's the summary for you. Raise again.

49
00:05:48,330 --> 00:05:53,970
I mean, once once you get the hang of these, I think you'll find it will become straightforward.

50
00:05:53,970 --> 00:06:03,630
If you add two states, as I've just shown, then effectively whenever you go into this state, you don't need to worry about the other auxiliary state.

51
00:06:03,630 --> 00:06:08,430
You just know that given the way this is being defined, if it finds an alpha,

52
00:06:08,430 --> 00:06:13,080
it's going to move to the square of the leftmost alpha and erase it and move into State C.

53
00:06:13,080 --> 00:06:17,640
And if no Alfred exists, then it'll move to the square after the two blanks.

54
00:06:17,640 --> 00:06:24,900
Right? Okay, I'm going to be OK.

55
00:06:24,900 --> 00:06:33,360
So here is a another version of Erase, and this just has two arguments.

56
00:06:33,360 --> 00:06:39,990
So what this is going to do is erase all the alphas on the tape and then move into state.

57
00:06:39,990 --> 00:06:45,630
Be right this time. There's no choice. It's just going to remove all the alphas.

58
00:06:45,630 --> 00:06:52,530
It's not searching to see whether there is one. It's just getting rid of any that there may be.

59
00:06:52,530 --> 00:07:00,720
Again, it's this is completely insensitive to what's on the tape at the particular point where this arises.

60
00:07:00,720 --> 00:07:03,420
It doesn't have any printing or moving behaviour.

61
00:07:03,420 --> 00:07:15,150
It just goes into this state and you can see that that state is defined functionally as erasing the leftmost alpha.

62
00:07:15,150 --> 00:07:25,750
OK. You can go out there is found it goes into state B, and if an outside is found, then it goes into this state, which is this state.

63
00:07:25,750 --> 00:07:34,120
So it just repeats itself again and again and again and again, it's easier to understand, probably with an arrow diagram.

64
00:07:34,120 --> 00:07:39,400
You start off coming in this state. This just transitions immediately to this.

65
00:07:39,400 --> 00:07:45,700
If an alpha exists, it moves to the square of the leftmost alpha and erases it and goes back into this state.

66
00:07:45,700 --> 00:07:48,340
So it just follows around again.

67
00:07:48,340 --> 00:07:59,560
And if at any point, well, eventually no alpha will exist and then it will move to the square after two blanks at the right.

68
00:07:59,560 --> 00:08:07,780
Print at the end function, again, I'm I'm not going through all of these, but just choosing a representative sample.

69
00:08:07,780 --> 00:08:11,410
So here there's the skeleton table.

70
00:08:11,410 --> 00:08:15,790
Here's the corresponding diagram.

71
00:08:15,790 --> 00:08:28,120
So when you go into this state, it transitions immediately into this state that moves to the left most schwa of the two at the start of the tape.

72
00:08:28,120 --> 00:08:33,340
Remember, the tape always starts in the Turin convention machine with two shows at the very left.

73
00:08:33,340 --> 00:08:42,100
They get written right at the start. This is moving to the left most of those, and then it's moving into this state.

74
00:08:42,100 --> 00:08:48,760
And in this state, you can see that if it encounters anything other than a blank,

75
00:08:48,760 --> 00:08:58,120
then it's moving two steps to the right and it's keep staying in the the same state here.

76
00:08:58,120 --> 00:09:05,290
Eventually, it will encounter a blank, and when it does so, the prince of beats of that and goes into state C.

77
00:09:05,290 --> 00:09:12,260
So essentially it it's going right to the left. The left hand end of the tape to the schwa.

78
00:09:12,260 --> 00:09:17,230
And then it's going through two steps at a time until it encounters a blank square.

79
00:09:17,230 --> 00:09:22,360
And at that point, it's writing a beta and moving into state c.

80
00:09:22,360 --> 00:09:28,300
Whatever sees remember state when state B and C when you see these,

81
00:09:28,300 --> 00:09:35,630
these are variables you can choose whatever state you want for it to go into at that point.

82
00:09:35,630 --> 00:09:38,870
OK. These are very, very simple.

83
00:09:38,870 --> 00:09:47,600
We've got our all of sea and air of sea, and all these do is move left or right, come and go interstate sea absolutely trivial.

84
00:09:47,600 --> 00:09:56,060
OK, so we've just introduced a state whose only function is no matter what may be on the table at that point,

85
00:09:56,060 --> 00:10:03,140
move left, go interstate sea, whatever seas will move right and go interstate sea.

86
00:10:03,140 --> 00:10:13,130
And these get used in within these functions because essentially what they mean is that after something has been found,

87
00:10:13,130 --> 00:10:27,440
you can then move left or right. So you can specify you don't have to stay on the square itself, having found something the copy and function.

88
00:10:27,440 --> 00:10:32,480
OK, so again, this is using functions that have already been defined.

89
00:10:32,480 --> 00:10:39,650
You can see it's using find and it's using print at the end. So let's let's follow through what it does.

90
00:10:39,650 --> 00:10:46,540
So if we go into this state, we.

91
00:10:46,540 --> 00:10:54,580
Here we're finding if some alpha exists, we're finding it and we're moving to the square to the left of the leftmost alpha.

92
00:10:54,580 --> 00:11:04,180
Okay, so that is using. This function here, this is the one that does a fine and then moves left.

93
00:11:04,180 --> 00:11:06,810
Okay, so now we're using that.

94
00:11:06,810 --> 00:11:17,160
So if somehow four exists moved to the square to the left of the left, most alpha move left and then go into this state.

95
00:11:17,160 --> 00:11:22,410
And then if on that square there's a zero printer, zero at the end of the tape.

96
00:11:22,410 --> 00:11:26,340
If on that square there's a one printer, one at the end of the tape.

97
00:11:26,340 --> 00:11:33,090
And of course, you could have more symbolism as well. You hear I'm only dealing with the figures zero and one.

98
00:11:33,090 --> 00:11:36,750
But it might be that you'll have other things written on the tape that you want to copy at the end.

99
00:11:36,750 --> 00:11:45,390
So essentially, what this is doing, this is looking for the square that is marked with a particular symbol.

100
00:11:45,390 --> 00:11:51,570
So suppose you've got a figure square with a zero or one there, and it's marked with an X.

101
00:11:51,570 --> 00:11:57,210
What this is doing, it's looking for the X, then it's identifying the digit that's been marked with the X,

102
00:11:57,210 --> 00:12:06,750
and then it's copying it to the end of the tape. So you can see we're building up quite sophisticated behaviour.

103
00:12:06,750 --> 00:12:10,590
Is the comparing function, Turing's description of it here,

104
00:12:10,590 --> 00:12:17,730
the first symbol marked Alpha and the first mock beta are compared if there is neither alpha nor beta,

105
00:12:17,730 --> 00:12:26,850
then go to St. E. If there are both and the symbols are alike, go to St., see otherwise go to state A.

106
00:12:26,850 --> 00:12:31,080
And again, I see India all variables here.

107
00:12:31,080 --> 00:12:40,800
A word of warning when you're reading Turing's paper, he uses these gothic letters and it can be very confusing.

108
00:12:40,800 --> 00:12:45,360
The Gothic e looks ever so like the sea at this particular point.

109
00:12:45,360 --> 00:12:51,170
Just be warned.

110
00:12:51,170 --> 00:12:59,790
So here's a summary of the various tape manipulating subroutines that Turing's defined as the find this the erase the print at the end,

111
00:12:59,790 --> 00:13:04,550
we found that there's a couple of varieties of copy.

112
00:13:04,550 --> 00:13:14,280
There's a replace function where you can replace any given symbol by any other copy at the end,

113
00:13:14,280 --> 00:13:18,950
all the symbols marked with an alpha without erasing the Alphas.

114
00:13:18,950 --> 00:13:23,990
And then there's some comparison functions, as you see.

115
00:13:23,990 --> 00:13:32,840
Yeah, there's a function to find the lost alpha. And I've pointed out here that it's littered throughout Turing's paper.

116
00:13:32,840 --> 00:13:37,340
There are various unfortunate misprint.

117
00:13:37,340 --> 00:13:44,300
The great advantage of studying it through Petzold book is that Petzel points these out that I'm just drawing this to your attention.

118
00:13:44,300 --> 00:13:54,410
Be aware that it looks like Turing mixed up Q and G a couple of times, and this actually arises later as well.

119
00:13:54,410 --> 00:14:02,570
So be aware at Page 124, Petzold explains this it's worth bearing in mind.

120
00:14:02,570 --> 00:14:14,970
OK, so we've got here a whole library of subroutines, as it were now.

121
00:14:14,970 --> 00:14:21,570
I want very briefly to go back and look at a machine that we were seeing yesterday.

122
00:14:21,570 --> 00:14:31,290
This is Turing's machine that prints out this probably transcendental number.

123
00:14:31,290 --> 00:14:43,630
And you can see what's going on here as it goes backwards and forwards, you can see it's marking the various figures and then it's finding them out,

124
00:14:43,630 --> 00:14:50,010
some copying, but now it's going to the left goes to the right, marks the figures.

125
00:14:50,010 --> 00:14:59,040
Now it copies them and then it's going to add an extra one.

126
00:14:59,040 --> 00:15:07,330
We all know that goes back to the left again. You can see the way in which it's working, it's using the kinds of subroutines that Turing has defined.

127
00:15:07,330 --> 00:15:16,120
It's going back and forth up the tape, going to the left, looking for the next, whatever it may be, finding the symbol that's marked with that.

128
00:15:16,120 --> 00:15:21,430
Copying it to the end, et cetera, et cetera. You know, erasing the symbols.

129
00:15:21,430 --> 00:15:32,170
And so if you see this kind of thing in operation, it helps to understand why Turing has defined these functions as he has.

130
00:15:32,170 --> 00:15:42,400
Now we're going to find later in the lecture that this business of if you like, subroutines editing the tape become absolutely crucial.

131
00:15:42,400 --> 00:15:53,320
When Turing defines the universal Turing machine, he's deliberately selected functions, which will enable him to do that.

132
00:15:53,320 --> 00:15:59,840
So we'll see that before long. OK.

133
00:15:59,840 --> 00:16:04,700
Section five of the paper enumeration of computable sequences.

134
00:16:04,700 --> 00:16:12,380
So what Turing is now going to do is explain how any Turing machine can be put in a standard form.

135
00:16:12,380 --> 00:16:21,770
And ultimately what he's going to do is assigned to every possible Turing machine a number, a natural number.

136
00:16:21,770 --> 00:16:29,900
It's going to immediately follow that if there are if every single Turing machine has a unique natural number,

137
00:16:29,900 --> 00:16:37,910
then there cannot be more Turing machines than there are natural numbers. So all the possible Turing machines are going to be innumerable.

138
00:16:37,910 --> 00:16:41,360
You could, in principle, put them in a list, an infinite list of goals,

139
00:16:41,360 --> 00:16:49,100
but they are innumerable and that's going to have consequences for computable numbers because a computable number,

140
00:16:49,100 --> 00:16:54,350
remember, is a number that can be generated by a Turing machine.

141
00:16:54,350 --> 00:17:04,910
And if there's only an innumerable number of Turing machines in the zone and in Europe, innumerable number of of computable numbers.

142
00:17:04,910 --> 00:17:13,100
So there are going to be fewer computable numbers than there are real numbers.

143
00:17:13,100 --> 00:17:24,240
Okay, so in order to do this, we have to use the strict kind of Turing machine where you have only one kind of action per line.

144
00:17:24,240 --> 00:17:28,460
You only have one print, one move left or right.

145
00:17:28,460 --> 00:17:32,240
OK. All stay still.

146
00:17:32,240 --> 00:17:42,140
We're going to no all the states and we're going to no, all the symbols and each line of the table is then going to take a very simple form.

147
00:17:42,140 --> 00:17:50,010
OK. So. Every single line of the table,

148
00:17:50,010 --> 00:17:59,610
we have the state in which the initial state in which the machine is and that's going to be Q1 and Q2, Q3, Q4, whatever.

149
00:17:59,610 --> 00:18:05,550
So we're getting rid of the letters that Turing's being used using up to now we're just going to number them.

150
00:18:05,550 --> 00:18:13,950
We have a particular symbol on the tape at that point. Snort is the blank S1, S2 as three, as four or other symbols.

151
00:18:13,950 --> 00:18:21,000
So they all have to be numbered in sequence and each line of the table.

152
00:18:21,000 --> 00:18:30,030
What this will mean is if you're in state Q I and you read on the tape symbol SJ,

153
00:18:30,030 --> 00:18:36,550
then what you are to do is print onto the tape symbol s k, which could of course, be the same right.

154
00:18:36,550 --> 00:18:43,530
It might actually be leaving the symbol unchanged, move left and go into state Q.

155
00:18:43,530 --> 00:18:47,400
And so there are three different forms.

156
00:18:47,400 --> 00:18:51,360
This one's moving left. This one's moving right. This one's staying in the same place.

157
00:18:51,360 --> 00:19:03,270
No move. OK, so our Turing machine, then we've we've simplified it in a sense, made it more complex in another sense.

158
00:19:03,270 --> 00:19:16,350
I mean, if you if you have a Turing machine that let me just illustrate that again, if we go back to this.

159
00:19:16,350 --> 00:19:27,810
Rats, maybe if you remember that Turing machine, the one that prints out the animal for one third.

160
00:19:27,810 --> 00:19:36,060
This has false statements and the action in each state is very, very simple.

161
00:19:36,060 --> 00:19:47,560
Whereas. This machine does the same thing with a single state, but its actions are more complicated.

162
00:19:47,560 --> 00:19:52,150
It has to move moves right when it encounters a zero or a one.

163
00:19:52,150 --> 00:19:59,110
Remember? So there's a sense in which this table is simpler than the other one because it's only got one state as opposed to four.

164
00:19:59,110 --> 00:20:03,310
But there's a sense in which it's more complex because it's got more complex actions.

165
00:20:03,310 --> 00:20:07,450
Okay. So in order to apply what Turing is doing here,

166
00:20:07,450 --> 00:20:18,790
we have to go for this form where we've simply got a single print, a single move at most per line of the table.

167
00:20:18,790 --> 00:20:26,290
OK, so we have a line of text consisting of quintuplets separated by semicolons.

168
00:20:26,290 --> 00:20:36,220
We're going to take all these quintuplets. The quintuple is simply that that list of five things all the quintupling that

169
00:20:36,220 --> 00:20:39,670
make up the machine table and we're going to put semicolons between them.

170
00:20:39,670 --> 00:20:45,310
And then we have a line of text which gives a description of the machine.

171
00:20:45,310 --> 00:20:48,730
In this description, we shall replace QE by the letter D,

172
00:20:48,730 --> 00:20:56,740
followed by the letter a repeated eight times and SJ by Dat D, followed by C repeating j times.

173
00:20:56,740 --> 00:21:07,030
So just to spell it out. Q one, that's the first step it will become a Q two will become a s zero.

174
00:21:07,030 --> 00:21:17,380
That's the blank which becomes D x one becomes DC S2, becomes the DC C and so on.

175
00:21:17,380 --> 00:21:22,450
So we end up our Turing machine, which started as a nice, easy to read table,

176
00:21:22,450 --> 00:21:27,160
is being successively transformed so that we just end up with a line of text

177
00:21:27,160 --> 00:21:33,730
consisting of letters and semicolons and that describes what the machine does.

178
00:21:33,730 --> 00:21:36,910
And he calls that the standard description.

179
00:21:36,910 --> 00:21:45,280
Then we go on again and we replace the letters by digits, and that gives us the description number of the machine.

180
00:21:45,280 --> 00:21:54,100
So let's let's see an example here again, is that machine that we've just seen running machine one of S. three.

181
00:21:54,100 --> 00:21:59,500
Okay. There we are.

182
00:21:59,500 --> 00:22:07,120
That's the table when we rename the end configurations, this is quoted from cheering,

183
00:22:07,120 --> 00:22:11,440
its table becomes this so you can see we've now numbered the state.

184
00:22:11,440 --> 00:22:17,650
So instead of giving them all their own letter, we just called them Q1, Q2, Q3, Q4.

185
00:22:17,650 --> 00:22:24,310
In every case, we're looking at the blank symbol. So it's not here.

186
00:22:24,310 --> 00:22:34,250
We're printing in zero, but this one and moving right here, we're printing a one that's s two and moving right.

187
00:22:34,250 --> 00:22:41,470
And so you'll notice that there's a slight additional complication here.

188
00:22:41,470 --> 00:22:46,360
Where is this just says move right from St.

189
00:22:46,360 --> 00:22:52,750
This is saying move right and print a blank.

190
00:22:52,750 --> 00:22:57,010
It's reading a blank and printing a blank. So it's leaving the tape unchanged. Right?

191
00:22:57,010 --> 00:23:04,000
So if you move and you leave the tape unchanged, you have to print back the symbol that was that.

192
00:23:04,000 --> 00:23:05,980
But even if you don't move, you have to.

193
00:23:05,980 --> 00:23:14,540
You can see, actually, that's going to make the tables rather more complicated because we can no longer really use a wild card.

194
00:23:14,540 --> 00:23:24,850
Right? If you're reading, if there's a certain action that you're going to take, no matter what is on the table to do it in this way,

195
00:23:24,850 --> 00:23:31,090
you're going to have to print back onto the take that same symbol, which means you need to record it.

196
00:23:31,090 --> 00:23:35,440
So you're actually going to have to have a lot more states. But let's not worry about that.

197
00:23:35,440 --> 00:23:40,080
You can see how in principle it would work.

198
00:23:40,080 --> 00:23:46,590
We're still quoting cheering other tables could be obtained by adding irrelevant lines such as this last one.

199
00:23:46,590 --> 00:23:52,770
So here we've got the same machine table, but we've got an extra line here.

200
00:23:52,770 --> 00:24:06,240
And this extra line says that if you're in the first state and you read a zero print back to zero and move right now, actually that never happens.

201
00:24:06,240 --> 00:24:11,100
Never, ever happens. Because here we are.

202
00:24:11,100 --> 00:24:17,430
It's still churning away, isn't it? What happens is in the first state you print zero.

203
00:24:17,430 --> 00:24:24,420
It immediately moves, right? So you are never in the first state with a zero on the tape.

204
00:24:24,420 --> 00:24:27,870
All right. You only ever encountered blanks that moves right?

205
00:24:27,870 --> 00:24:32,650
And you see you come back into the first state from the fourth state just by moving right?

206
00:24:32,650 --> 00:24:37,320
So it's moving right all the time. I can actually.

207
00:24:37,320 --> 00:24:45,110
Stop it now. OK, so the upshot is here we've got a machine table,

208
00:24:45,110 --> 00:24:51,800
which in behaviour is absolutely identical to the one before because we've added a line to it which is completely irrelevant,

209
00:24:51,800 --> 00:25:03,530
which is never going to be reached. So cheering, as shown here, that many different machines can be entirely equivalent in behaviour,

210
00:25:03,530 --> 00:25:09,800
if you add an irrelevant line to a machine table, it's going to change the machine.

211
00:25:09,800 --> 00:25:14,510
It changes the description of the machine, changes the description number of the machine,

212
00:25:14,510 --> 00:25:19,850
but actually the number that's generated by the machine will be exactly the same.

213
00:25:19,850 --> 00:25:24,440
And of course, it's entirely possible to have the same number generated by a lot,

214
00:25:24,440 --> 00:25:31,280
by lots of machines that behave differently, not just with irrelevant lines, but in other ways.

215
00:25:31,280 --> 00:25:35,420
So it follows that you can have lots of different Turing machines,

216
00:25:35,420 --> 00:25:42,860
which all generate the same computable number, which all have the same output in terms of figures.

217
00:25:42,860 --> 00:25:48,560
So the mapping from satisfactory machines remember satisfactory machines of a circle, free machines,

218
00:25:48,560 --> 00:25:58,070
the machines that carry on generating digits forever, like the one we just saw the mapping from those to computable numbers is subjective.

219
00:25:58,070 --> 00:26:04,250
In other words, every computable number can be computed by one of these machines.

220
00:26:04,250 --> 00:26:15,000
At least at Turing is right that these machines correctly capture all possible computations, but it's not going to be an injected function.

221
00:26:15,000 --> 00:26:20,000
There will be lots and lots of different Turing machines that all mapped to the same computer bill.

222
00:26:20,000 --> 00:26:31,110
No. OK, so I'm quoting cheering again, our first standard form would be.

223
00:26:31,110 --> 00:26:37,620
So this is where he's taken the machine. He's divided up into lines, put those into Queen two falls.

224
00:26:37,620 --> 00:26:42,810
No, the states, no the symbols and separated the semicolon.

225
00:26:42,810 --> 00:26:48,060
So that's a single line that this is the standard description.

226
00:26:48,060 --> 00:26:57,840
And just to help you understand that I've put down here the key Q one has become a s north has become D as one has become DC.

227
00:26:57,840 --> 00:27:02,620
Q2 has become Kia. Q3 has become a and so.

228
00:27:02,620 --> 00:27:08,610
Okay, so you can see it pretty easily how you get from the table to that.

229
00:27:08,610 --> 00:27:17,640
And now what we're doing, we're simply doing that substitution into this and we end up with that.

230
00:27:17,640 --> 00:27:30,540
Then we replace the letters and indeed the semicolon by digits, and we get this, so that's all one single number.

231
00:27:30,540 --> 00:27:34,980
This might remind you a little bit of what we saw with girdle.

232
00:27:34,980 --> 00:27:42,960
We find some method of converting a formula or in this case, a Turing machine to a number.

233
00:27:42,960 --> 00:27:51,060
The numbers, we get a pretty humungous. I mean, these aren't actually as big as curdle numbers, but they're they're nevertheless pretty big.

234
00:27:51,060 --> 00:28:01,980
And the aim is to prove some theoretical result. This is the description number of the machine that has the extra state.

235
00:28:01,980 --> 00:28:13,770
And I've just shown in red the the extra digits that have been added at the end for that last quintuple.

236
00:28:13,770 --> 00:28:24,120
OK. To each computable sequence that corresponds at least one description, no whale, to no description, no.

237
00:28:24,120 --> 00:28:28,320
Does that correspond more than one computable sequence?

238
00:28:28,320 --> 00:28:37,770
OK, so a description number simply gives you a effectively a formula for generating a Turing machine.

239
00:28:37,770 --> 00:28:42,460
A Turing machine can generate, at most one computable No.

240
00:28:42,460 --> 00:28:47,580
Circle three. It will generate a computable number if it's not circle free.

241
00:28:47,580 --> 00:28:54,600
If it halts gets into a loop without outputting any more figures, then it will not generate the immutable number.

242
00:28:54,600 --> 00:29:00,930
But at most, it will generate one. The computable sequences is numbers are therefore innumerable.

243
00:29:00,930 --> 00:29:10,710
OK. You can put them in a list. You can list all the possible Turing machines in the order of these numbers,

244
00:29:10,710 --> 00:29:18,810
and you can thus produce a list of all the computable numbers by putting next to each description.

245
00:29:18,810 --> 00:29:29,670
Number the corresponding computable number of course, you can't in practise because they're only infinite, but infinitely more and more digits.

246
00:29:29,670 --> 00:29:37,200
You can't write them out. But we're doing this conceptually. OK, so it follows.

247
00:29:37,200 --> 00:29:47,880
I mean, this is this is quite a peculiar result if you think about it. We saw in the first lecture that the real numbers are not innumerable.

248
00:29:47,880 --> 00:29:57,210
They can't be put into a list. So there are far, far more real numbers than there are rational numbers, for example.

249
00:29:57,210 --> 00:30:11,450
That's a kind of slightly surprising result. I mean, to a very close approximation, all real numbers are irrational.

250
00:30:11,450 --> 00:30:22,900
It now follows that to a really close approximation, all real numbers are non computable.

251
00:30:22,900 --> 00:30:32,770
That means actually, if you have a non computable number, it's very hard to see how we could even refer to it.

252
00:30:32,770 --> 00:30:41,680
I mean, you clearly, clearly can't write it down. You can't even generate a formula to specify it.

253
00:30:41,680 --> 00:30:47,980
You can't. You can't. You certainly can't write a programme that is going to generate its digits.

254
00:30:47,980 --> 00:30:57,640
So we end up with this rather strange result that there are all these, those real numbers out there that we cannot get hold of any way at all.

255
00:30:57,640 --> 00:31:03,520
We can't refer to them, but we know by cantors proof that they're there.

256
00:31:03,520 --> 00:31:10,900
So you can see how this kind of result might stimulate quite a lot of interesting thinking in the philosophy of mathematics.

257
00:31:10,900 --> 00:31:17,240
We're not actually going to go there, but I I simply point that out as an interesting consequence of what Turing has done.

258
00:31:17,240 --> 00:31:24,520
I think it's it's a much more striking result than the result about there being more real than rational numbers.

259
00:31:24,520 --> 00:31:33,310
They're being more Reelz than computable numbers is is more dramatic because, of course, Pi and E and so on are computable.

260
00:31:33,310 --> 00:31:43,660
They're irrational, but they're computable. We now see that there are all these real numbers that aren't even computer that you can't

261
00:31:43,660 --> 00:31:52,660
even specify them by means of giving a computer programme that will generate digit by digit.

262
00:31:52,660 --> 00:31:56,920
OK, so that's that's quite momentous. Let's move on to section six.

263
00:31:56,920 --> 00:32:03,520
Another really momentous result the universal Turing machine.

264
00:32:03,520 --> 00:32:12,250
And here what Turing is going to do is to show how to design a single machine which can be used to compute any computable sequence.

265
00:32:12,250 --> 00:32:15,340
Now there's any compute of sequence of digits, any computable number.

266
00:32:15,340 --> 00:32:21,570
So up till now, we've had Turing machines, each of them generating at best one computable number.

267
00:32:21,570 --> 00:32:30,220
It's a circle circle. Three machine generates one computable number. Now he's talking about a single machine generating all computable numbers.

268
00:32:30,220 --> 00:32:36,490
How can that work? Well, of course it works now because he's going to he's not going to start with a blank tape.

269
00:32:36,490 --> 00:32:43,450
If you start with a blank tape, any given machine will generate a single computable number at best.

270
00:32:43,450 --> 00:32:53,320
What he's now going to do is show how you can create a Turing machine, which will read from its own tape from the left hand part of its own tape.

271
00:32:53,320 --> 00:33:02,620
It will read the instructions that it has to perform, and it will thus simulate the behaviour of any Turing machine you care to mention.

272
00:33:02,620 --> 00:33:06,370
Right. So we're going to end up with a universal machine, a Turing machine,

273
00:33:06,370 --> 00:33:12,850
which effectively runs from a specification of some other Turing machine and and

274
00:33:12,850 --> 00:33:20,020
generates exactly the same computer for number as that of a Turing machine would do.

275
00:33:20,020 --> 00:33:25,360
So if this machine you is supplied with a tape on the beginning of which is written,

276
00:33:25,360 --> 00:33:37,000
the standard description of some computing machine in the Turing machine, in other words, then you will compute the same sequence as in.

277
00:33:37,000 --> 00:33:41,050
OK, so Turing starts the discussion in a slightly odd way, but it's actually,

278
00:33:41,050 --> 00:33:47,200
I think, quite a good way of introducing the discussion and making the point.

279
00:33:47,200 --> 00:33:54,760
We can see at the end the denouement we we find we have actually done what we want to do.

280
00:33:54,760 --> 00:34:07,780
Let's first suppose that we have some particular machine in prime which will write down on the F squares, the successive complete configurations of N.

281
00:34:07,780 --> 00:34:15,430
So we're we're going to focus on one particular case we've got a machine m a Turing machine,

282
00:34:15,430 --> 00:34:21,130
and we're going to find out how we can create a machine m prime,

283
00:34:21,130 --> 00:34:31,600
which will generate exactly the same computable sequence by referring to the standard description of N.

284
00:34:31,600 --> 00:34:43,610
OK, so he's going to refer back now to machine to just to remind you that.

285
00:34:43,610 --> 00:34:54,170
This one, the one that generates the number in which you've got successively larger numbers of ones.

286
00:34:54,170 --> 00:35:00,440
Jason, followed by zero. It happened. She noticed a little bit odd.

287
00:35:00,440 --> 00:35:05,540
It doesn't matter. But I just want to point it out because it might. You might find it rather confusing.

288
00:35:05,540 --> 00:35:09,380
I mean, here we've got this machine, which has rather complicated behaviour.

289
00:35:09,380 --> 00:35:16,070
This is not a machine in the standard form that Turing later in the paper is requiring.

290
00:35:16,070 --> 00:35:21,050
We've seen that in order to produce the standard description of the machine,

291
00:35:21,050 --> 00:35:27,590
we have to reduce the machine to quintuplets where it's divided up into steps and actions,

292
00:35:27,590 --> 00:35:34,730
where we've got to at most one print, at most one right or left for each, each line of the table.

293
00:35:34,730 --> 00:35:42,410
So actually, to produce this same behaviour by a standard Turing machine that is the form that he's using later,

294
00:35:42,410 --> 00:35:50,150
we'd actually have to have a lot more state, which has to be a lot more complicated. So Turing's kind of cheating here.

295
00:35:50,150 --> 00:35:56,300
But that doesn't matter because what we're focussing on here is the behaviour of this machine,

296
00:35:56,300 --> 00:36:06,880
what it actually outputs, and we will see how that works.

297
00:36:06,880 --> 00:36:19,250
Okay, so I've just pointed out that oddity here. So we saw earlier this was on Slide 86.

298
00:36:19,250 --> 00:36:28,010
And it's in Petzold book page 92 that we saw how a sequence of complete configurations can be listed.

299
00:36:28,010 --> 00:36:38,060
Now remember, a complete configuration is what you see between the columns here.

300
00:36:38,060 --> 00:36:47,060
The complete configuration is it shows everything on the tape at that particular point in the calculation,

301
00:36:47,060 --> 00:36:54,020
and it also shows what state the machine is and where exactly it is on the tape at that point.

302
00:36:54,020 --> 00:36:59,930
Right? So remember the complete configuration I explained to you in the previous lecture?

303
00:36:59,930 --> 00:37:08,210
It's what you would need to write down if you wanted to stop doing the calculation and then come back to it later and pick up where you left off.

304
00:37:08,210 --> 00:37:13,130
You'd need to know exactly what was written on the tape at that point. You'd need to know which is the current square.

305
00:37:13,130 --> 00:37:22,940
And you'd need to know which state you're in. That's it. So we've got a complete configuration there, a complete configuration there and so on.

306
00:37:22,940 --> 00:37:32,150
So what Turing was illustrating here was how you could record the exact process of a calculation by listing the complete configurations.

307
00:37:32,150 --> 00:37:37,130
I mean, it starts just, you know, with nothing written on the tape and it's in state B.

308
00:37:37,130 --> 00:37:46,730
And then after the first step, it's got to and then a couple of zeros and so forth.

309
00:37:46,730 --> 00:37:55,310
And then it goes on. Now again, as I've said, you've got this oddity that we've got quite complicated behaviour here.

310
00:37:55,310 --> 00:38:02,570
If the machine was put in the standard form, we'd have far less change from one complete configuration to another.

311
00:38:02,570 --> 00:38:08,360
But that doesn't mean that's the basic idea is that whenever you have a Turing machine,

312
00:38:08,360 --> 00:38:14,930
whether a complex one or a simple one, you can in principle list the complete configurations one after another,

313
00:38:14,930 --> 00:38:15,530
after another,

314
00:38:15,530 --> 00:38:25,100
after another with columns in between and each complete configuration shows you exactly what the stage of the calculation was at that step.

315
00:38:25,100 --> 00:38:33,440
OK. But. So now cheering again, he's going to modify this format.

316
00:38:33,440 --> 00:38:40,160
He's going to replace the state code just in the same way as he's done with the quintuple, so instead of the old Q,

317
00:38:40,160 --> 00:38:51,740
we going to have Daddy AA and AAA blanks are going to be replaced by D zero by DC, one by DCC and Schwab by DC CC.

318
00:38:51,740 --> 00:39:03,900
So exactly as we had before. He's replacing the symbols in the complete configurations by this.

319
00:39:03,900 --> 00:39:11,150
This sequence of letters, so the result of these substitutions in to see is that OK,

320
00:39:11,150 --> 00:39:16,670
so you may remember see which we had before and we now get to see one.

321
00:39:16,670 --> 00:39:25,730
So effectively, what these sequences are encoding is a sequence of complete configurations.

322
00:39:25,730 --> 00:39:28,340
This is the sequence of symbols on f squares, he says.

323
00:39:28,340 --> 00:39:37,200
What he means is remember, we're trying to produce a machine in prime which is going to copy the behaviour of a machine.

324
00:39:37,200 --> 00:39:49,190
And it does that by referring to a specification of M, which is going to be written on the left hand end of the tape.

325
00:39:49,190 --> 00:39:53,540
So before the show was OK, there's going to be a left hand.

326
00:39:53,540 --> 00:39:58,130
There's going to be a description of the machine to be copied.

327
00:39:58,130 --> 00:40:04,270
The machine, which is going to be in this standard form with these scissors and so forth.

328
00:40:04,270 --> 00:40:10,700
And now what Turing is saying is what we want to happen at the right-hand end of the tape is we

329
00:40:10,700 --> 00:40:16,700
want a sequence of complete configurations like this to be generated in the same kind of format,

330
00:40:16,700 --> 00:40:21,860
diseases and so forth. So the machine in prime,

331
00:40:21,860 --> 00:40:30,290
which is being designed to print out the successive configurations of machine and is to do so in this form on the edge of squares.

332
00:40:30,290 --> 00:40:37,530
So we've no we've no longer got f squares being confined to zero and well.

333
00:40:37,530 --> 00:40:41,700
He remarked that if any can be constructed, then so can him prime,

334
00:40:41,700 --> 00:40:47,970
and it would operate by referring back to a copy of the standard description of him written on the tape.

335
00:40:47,970 --> 00:40:54,450
So having seen the way the Turing machines work, the kind of editing that they do,

336
00:40:54,450 --> 00:41:00,180
the way they can go back upwards and forwards, comparing symbols, copying them and all the rest.

337
00:41:00,180 --> 00:41:05,160
I hope you will find this credible that if at the left hand end of the tape,

338
00:41:05,160 --> 00:41:16,350
you've got a standard description of machine em and if and at the right hand end you've got a sequence of complete configurations.

339
00:41:16,350 --> 00:41:24,150
Then what machine am prime is going to do? It's going to look at the the last complete configuration.

340
00:41:24,150 --> 00:41:32,310
Oh, I see we're in that state with that symbol. Then it's going to shuffle back to the beginning of the tape.

341
00:41:32,310 --> 00:41:44,190
Look at the machine table for em, and it's going to identify what it should do, given that symbol and that state.

342
00:41:44,190 --> 00:41:53,280
So let's see that spelt out a little bit more. So Entrain will print out in sequence the complete configurations that M would produce at each stage.

343
00:41:53,280 --> 00:41:59,460
It will have a record of the last complete configuration that's at the right hand end of the tape

344
00:41:59,460 --> 00:42:06,720
and a record of MS rules in the form of the standard description at the left hand end of the tape.

345
00:42:06,720 --> 00:42:13,350
It will shuttle back and forth, checking the latest configuration that is the state and the symbol from the right,

346
00:42:13,350 --> 00:42:19,050
then finding the rule that this matches at the left, then moving back to build the next complete configuration accordingly.

347
00:42:19,050 --> 00:42:24,510
On the right side, right side, shuffle over to the right.

348
00:42:24,510 --> 00:42:28,140
What's the current configuration? Okay, you go back to the left.

349
00:42:28,140 --> 00:42:37,650
What's the rule for that configuration? OK, now we know what to do and it has to go back and it has to copy that configuration again,

350
00:42:37,650 --> 00:42:45,210
making changes the few changes that are required by the latest action.

351
00:42:45,210 --> 00:42:49,200
So it's keeping track as it goes.

352
00:42:49,200 --> 00:42:52,440
Of all the configurations,

353
00:42:52,440 --> 00:43:03,460
right here are the configurations in C one so C1 that we saw a slider two ago generated by the non-standard machine to the machine we saw.

354
00:43:03,460 --> 00:43:10,020
And what I've done here, I've underlined the configurations. OK.

355
00:43:10,020 --> 00:43:21,330
So here what you've got is the state here you've got state and symbol, here you've got state and symbol.

356
00:43:21,330 --> 00:43:35,770
OK. So in each case, the state will be a deal followed by a number of ayes, and the symbol will be followed by a number of seats.

357
00:43:35,770 --> 00:43:40,830
OK. OK.

358
00:43:40,830 --> 00:43:45,450
Recall that the complete configurations are separated by columns, so at the right of the tape,

359
00:43:45,450 --> 00:43:55,680
we've got complete configuration column, complete configuration code, complete configuration as you see within them.

360
00:43:55,680 --> 00:43:59,760
Just one state represented by D, followed by a sequence of A's,

361
00:43:59,760 --> 00:44:06,930
will appear followed by the scan symbol on the current square represented by D, followed by a sequence of CS.

362
00:44:06,930 --> 00:44:14,130
And I suggested that when you go through this, you might find it helpful to refer to the text on Page 151,

363
00:44:14,130 --> 00:44:21,620
where during spells out these these various translations.

364
00:44:21,620 --> 00:44:32,900
OK. What about the standard description? Remember, the standard description is the the left hand end of the tape.

365
00:44:32,900 --> 00:44:41,400
So here what I've done. I've underlined what I call the trigger configurations, so we've got the standard description of the machine.

366
00:44:41,400 --> 00:44:47,270
Remember, it consists of lots and lots of encoded quintuplets.

367
00:44:47,270 --> 00:44:52,880
And here all the various quinta balls for the machine we're looking at here.

368
00:44:52,880 --> 00:44:56,660
And what I've done here, I've shown you how the translation takes place.

369
00:44:56,660 --> 00:45:01,430
So initial state be read symbol blank, right?

370
00:45:01,430 --> 00:45:06,190
Symbol zero. Move right into state C.

371
00:45:06,190 --> 00:45:11,480
Okay. So first of all, we no the states and the symbols. So we get initial state.

372
00:45:11,480 --> 00:45:22,250
Q One read symbol, snort right symbol S1 move right into state Q2 and then the cues are being replaced by D,

373
00:45:22,250 --> 00:45:31,280
followed by the appropriate number of A's. The symbols are being replaced by D, followed by the appropriate number of seats.

374
00:45:31,280 --> 00:45:35,450
In the case of the blank. No signs because that s not okay.

375
00:45:35,450 --> 00:45:48,020
So if you look there d a d, d, c, r d, that's the first quintuple being encoded and daddy is the configuration.

376
00:45:48,020 --> 00:45:55,520
That's the state plus the symbol. That's what determines what should happen, what should happen.

377
00:45:55,520 --> 00:46:00,500
After you write this symbol, you move right and you go into that state.

378
00:46:00,500 --> 00:46:07,910
So if you put those two things together here on the right hand side of the tape, we've got the configurations,

379
00:46:07,910 --> 00:46:10,520
the complete configurations being built up,

380
00:46:10,520 --> 00:46:18,650
which is a record of what what is the case at each particular stage of the calculation you look there to see,

381
00:46:18,650 --> 00:46:23,780
I mean, you look at the last configuration to be written and you identify this part of it,

382
00:46:23,780 --> 00:46:29,240
the part that that gives you the configuration, the state and the symbol.

383
00:46:29,240 --> 00:46:35,600
And then you shuttle off back to the left hand end of the tape and you look for the the matching trigger.

384
00:46:35,600 --> 00:46:40,430
And when you find that, okay, that's the quintuple on which I need to act,

385
00:46:40,430 --> 00:46:49,460
that's the quintuple which is specifying what needs to change with the configuration, you know, as a as the next configuration is written.

386
00:46:49,460 --> 00:46:54,510
Okay? This is obviously quite complicated.

387
00:46:54,510 --> 00:47:04,250
I do urge you to read it through carefully. In petzold, it's not essential to understand, you know, every last detail of how this is working,

388
00:47:04,250 --> 00:47:08,720
particularly all the detail of how the universal machine is defined.

389
00:47:08,720 --> 00:47:13,490
But what's crucial is to have have the general idea of how it's worked, how it works.

390
00:47:13,490 --> 00:47:20,000
I mean, once you've seen some Turing machines in action, as you will have done by that stage of the book, including,

391
00:47:20,000 --> 00:47:28,430
you know, Petzold ingenious machine that does the square root of two, it gives you a feel for how these things operate.

392
00:47:28,430 --> 00:47:36,140
And then you should be able to see that in principle, you know, it's going to be fiddly, but you can see that it is possible to do this.

393
00:47:36,140 --> 00:47:42,710
You know, the universal Turing machine is certainly a possibility.

394
00:47:42,710 --> 00:47:50,240
Okay. One thing we've not done, we've not yet dealt with the figures that are printed.

395
00:47:50,240 --> 00:48:00,320
So to mimic MS generation of a computable number. We also have to print out at each stage any new figures, zeros and ones produced by the transition.

396
00:48:00,320 --> 00:48:04,760
And these are going to be colon separated between the successive complete configurations.

397
00:48:04,760 --> 00:48:09,590
So you just want to explain this zero and one or a special case?

398
00:48:09,590 --> 00:48:15,140
Right? All the other stuff that gets printed by the machines is working.

399
00:48:15,140 --> 00:48:24,440
The zeros and ones that are printed actually specify the computable number, the number that's going to end up on the tape.

400
00:48:24,440 --> 00:48:33,890
What Turing is saying is that rather than having zeros and ones printed, you know, and then printed again and again and again,

401
00:48:33,890 --> 00:48:41,090
because as we've seen with each quintuple, if you if you leave a square, you then have to print it again.

402
00:48:41,090 --> 00:48:46,250
What he's saying is you kind of save up the zeros and ones and you print them at the end.

403
00:48:46,250 --> 00:48:56,240
So as you go step by step through the as the machine churns from one state to another, you print out a complete configuration.

404
00:48:56,240 --> 00:49:07,430
But if a zero or a one has been printed you, then you add that at that stage after the complete configuration again separated by a colon.

405
00:49:07,430 --> 00:49:12,260
You'll see that if you look in the book, you'll find that that illustrated,

406
00:49:12,260 --> 00:49:19,400
which makes it very straightforward to understand if M Prime has been designed designed.

407
00:49:19,400 --> 00:49:25,040
Appropriately, then, this is the key move we've designed,

408
00:49:25,040 --> 00:49:33,920
and in prime and prime is this machine that refers to the description of machine and the left hand end of the tape and at the right hand

409
00:49:33,920 --> 00:49:41,180
end kind of reproduces its behaviour by generating complete configuration after complete configuration of the complete configuration.

410
00:49:41,180 --> 00:49:46,190
And between those putting in any zeros or ones that have to have been printed,

411
00:49:46,190 --> 00:49:52,430
you can actually see that if we change the description of anyone at the left hand end of the tape,

412
00:49:52,430 --> 00:49:58,460
then the same machine is going to mimic whatever machine description we put there.

413
00:49:58,460 --> 00:50:01,400
So actually, we have generated a universal machine,

414
00:50:01,400 --> 00:50:08,750
replacing the standard description of the left of the tape with the standard description of a different machine and will mean that

415
00:50:08,750 --> 00:50:16,550
we end up with the sequence of figures that end would generate on the tape instead of the sequence of figures that we generate.

416
00:50:16,550 --> 00:50:19,070
So now obviously,

417
00:50:19,070 --> 00:50:29,240
the universal Turing machine is not going to be generating exactly the same stuff on the tape as the machine and that it's mimicking, right?

418
00:50:29,240 --> 00:50:38,090
It's not mimicking, and in every respect, it's going to have loads and loads of working, all those complete configurations that M doesn't generate.

419
00:50:38,090 --> 00:50:39,980
But the crucial point is the figures,

420
00:50:39,980 --> 00:50:49,280
the zeros and ones are going to come out in exactly the same order from the universal machine as they do from machine.

421
00:50:49,280 --> 00:50:57,450
OK, so we end up with the same computable no.

422
00:50:57,450 --> 00:51:05,190
OK, so finally, I'm not going to go through how the universal machine works in detail, I've said go and look at that in the book and again,

423
00:51:05,190 --> 00:51:14,250
don't feel that you've got to understand every last detail, but do read it through and make sure you've got a feel for how this is working.

424
00:51:14,250 --> 00:51:25,710
So Section seven describes the universal machine in detail. It uses the kind of subroutines that we were talking about earlier those functions.

425
00:51:25,710 --> 00:51:30,390
This was the first proof that there could be a universal programmable machine

426
00:51:30,390 --> 00:51:37,950
capable of computing any number that we know how to compute when given the recipe.

427
00:51:37,950 --> 00:51:46,110
Now, Turing here is obviously focussing on computable numbers, the generation of sequences of zeros and ones,

428
00:51:46,110 --> 00:51:54,180
but by extension, it's clear that any other computer will function will be achievable by the same means.

429
00:51:54,180 --> 00:52:03,720
I mean, we've we've got a method essentially for replicating the computational behaviour of any Turing machine at all.

430
00:52:03,720 --> 00:52:12,450
And if Turing is right, as he argued, we looked looked at two lectures ago.

431
00:52:12,450 --> 00:52:23,340
If he's right that his kind of computing machines actually capture all the possible mechanical methods of computation,

432
00:52:23,340 --> 00:52:31,380
then it follows that we actually have a universal machine that is capable of replicating anything that can be computed.

433
00:52:31,380 --> 00:52:37,200
So a momentous result, indeed, and we'll say a little bit more about that next time.

434
00:52:37,200 --> 00:52:43,798
Thank you.