Turing 2018/3: “On Computable Numbers” – Turing’s 1936 Paper

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.