In the last lecture we saw both for the Turing machine is and we saw something of what a Turing convention machine is,
a Turing convention machine is a Turing machine in which we follow the conventions that Turing does in his 1936 paper,
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.
We also saw briefly at the end, a sort of subroutine that you can have within a Turing machine.
And we saw how this provided a general recipe for adding functions to a Turing machine.
Turing does it in the way of skeleton tables.
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.
And what this does is it searches for the leftmost alpha on the tape.
If one is found, it goes into State C at that point.
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.
Then it ends up in State B. And remember the crucial point?
I emphasised that you mustn't think of this state as some funny beast.
This is just a label for it. OK? It is just a state like any other.
But this is a functional description of it.
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,
if not, so it gives us a general recipe.
We might end up adding lots and lots and lots of states like this.
You know, we've got three new states here that we've introduced for this purpose here.
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,
depending whether something is found or not.
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.
And this imposes a sort of order on it. It makes it comprehensible what's going on.
So here is a summary of the function of this here.
I've just reduced to a single state. I'm ignoring the other two states that are added to enable this to work.
We can simplify and just think, well, this if we add a state like this, then if an al.4 exists,
it's going to move to the square containing the less most alpha and Interstate S. And if no alpha exists,
it will move to the square after the two blanks at the right and go into state B.
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.
Okay, we're now going to see quite a lot of these Turing skeleton tables.
I haven't given you all of them here. I've chosen a representative sample.
If you read Petzold, you'll see all the others. And I do give a list of them later in the lecture.
But once you've got the general idea, it should be relatively straightforward to see how these things would work.
So here is erase once. So this is a this is a function which finds the leftmost alpha and then erases it.
OK. How does it work? Well, you can see here that it's very simple.
It doesn't take any account of the symbol that's there at the time.
It doesn't do any special behaviour. It doesn't move left or right or print anything.
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.
So notice this is using the find function. So it is looking for the leftmost alpha.
If it finds the leftmost alpha, then it goes into this state, which is this one here, which is about to be defined.
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.
In other words, it prints of blank on that square and then goes into State C so that I can.
So Turing is using the find function here to define an erase function.
And again, in order to implement this, you can see you, you need two new states.
So for any, any time you want to include some kind of erase function like this,
you need to add two states to your Turing machine and you give them this behaviour.
And there you have it. Okay, so Turing defined two versions of this.
This is a version that you can see has three arguments, and we'll see that there's another as well.
That's the summary for you. Raise again.
I mean, once once you get the hang of these, I think you'll find it will become straightforward.
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.
You just know that given the way this is being defined, if it finds an alpha,
it's going to move to the square of the leftmost alpha and erase it and move into State C.
And if no Alfred exists, then it'll move to the square after the two blanks.
Right? Okay, I'm going to be OK.
So here is a another version of Erase, and this just has two arguments.
So what this is going to do is erase all the alphas on the tape and then move into state.
Be right this time. There's no choice. It's just going to remove all the alphas.
It's not searching to see whether there is one. It's just getting rid of any that there may be.
Again, it's this is completely insensitive to what's on the tape at the particular point where this arises.
It doesn't have any printing or moving behaviour.
It just goes into this state and you can see that that state is defined functionally as erasing the leftmost alpha.
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.
So it just repeats itself again and again and again and again, it's easier to understand, probably with an arrow diagram.
You start off coming in this state. This just transitions immediately to this.
If an alpha exists, it moves to the square of the leftmost alpha and erases it and goes back into this state.
So it just follows around again.
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.
Print at the end function, again, I'm I'm not going through all of these, but just choosing a representative sample.
So here there's the skeleton table.
Here's the corresponding diagram.
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.
Remember, the tape always starts in the Turin convention machine with two shows at the very left.
They get written right at the start. This is moving to the left most of those, and then it's moving into this state.
And in this state, you can see that if it encounters anything other than a blank,
then it's moving two steps to the right and it's keep staying in the the same state here.
Eventually, it will encounter a blank, and when it does so, the prince of beats of that and goes into state C.
So essentially it it's going right to the left. The left hand end of the tape to the schwa.
And then it's going through two steps at a time until it encounters a blank square.
And at that point, it's writing a beta and moving into state c.
Whatever sees remember state when state B and C when you see these,
these are variables you can choose whatever state you want for it to go into at that point.
OK. These are very, very simple.
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.
OK, so we've just introduced a state whose only function is no matter what may be on the table at that point,
move left, go interstate sea, whatever seas will move right and go interstate sea.
And these get used in within these functions because essentially what they mean is that after something has been found,
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.
OK, so again, this is using functions that have already been defined.
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.
So if we go into this state, we.
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.
Okay, so that is using. This function here, this is the one that does a fine and then moves left.
Okay, so now we're using that.
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.
And then if on that square there's a zero printer, zero at the end of the tape.
If on that square there's a one printer, one at the end of the tape.
And of course, you could have more symbolism as well. You hear I'm only dealing with the figures zero and one.
But it might be that you'll have other things written on the tape that you want to copy at the end.
So essentially, what this is doing, this is looking for the square that is marked with a particular symbol.
So suppose you've got a figure square with a zero or one there, and it's marked with an X.
What this is doing, it's looking for the X, then it's identifying the digit that's been marked with the X,
and then it's copying it to the end of the tape. So you can see we're building up quite sophisticated behaviour.
Is the comparing function, Turing's description of it here,
the first symbol marked Alpha and the first mock beta are compared if there is neither alpha nor beta,
then go to St. E. If there are both and the symbols are alike, go to St., see otherwise go to state A.
And again, I see India all variables here.
A word of warning when you're reading Turing's paper, he uses these gothic letters and it can be very confusing.
The Gothic e looks ever so like the sea at this particular point.
Just be warned.
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,
we found that there's a couple of varieties of copy.
There's a replace function where you can replace any given symbol by any other copy at the end,
all the symbols marked with an alpha without erasing the Alphas.
And then there's some comparison functions, as you see.
Yeah, there's a function to find the lost alpha. And I've pointed out here that it's littered throughout Turing's paper.
There are various unfortunate misprint.
The great advantage of studying it through Petzold book is that Petzel points these out that I'm just drawing this to your attention.
Be aware that it looks like Turing mixed up Q and G a couple of times, and this actually arises later as well.
So be aware at Page 124, Petzold explains this it's worth bearing in mind.
OK, so we've got here a whole library of subroutines, as it were now.
I want very briefly to go back and look at a machine that we were seeing yesterday.
This is Turing's machine that prints out this probably transcendental number.
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,
some copying, but now it's going to the left goes to the right, marks the figures.
Now it copies them and then it's going to add an extra one.
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.
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.
Copying it to the end, et cetera, et cetera. You know, erasing the symbols.
And so if you see this kind of thing in operation, it helps to understand why Turing has defined these functions as he has.
Now we're going to find later in the lecture that this business of if you like, subroutines editing the tape become absolutely crucial.
When Turing defines the universal Turing machine, he's deliberately selected functions, which will enable him to do that.
So we'll see that before long. OK.
Section five of the paper enumeration of computable sequences.
So what Turing is now going to do is explain how any Turing machine can be put in a standard form.
And ultimately what he's going to do is assigned to every possible Turing machine a number, a natural number.
It's going to immediately follow that if there are if every single Turing machine has a unique natural number,
then there cannot be more Turing machines than there are natural numbers. So all the possible Turing machines are going to be innumerable.
You could, in principle, put them in a list, an infinite list of goals,
but they are innumerable and that's going to have consequences for computable numbers because a computable number,
remember, is a number that can be generated by a Turing machine.
And if there's only an innumerable number of Turing machines in the zone and in Europe, innumerable number of of computable numbers.
So there are going to be fewer computable numbers than there are real numbers.
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.
You only have one print, one move left or right.
OK. All stay still.
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.
OK. So. Every single line of the table,
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.
So we're getting rid of the letters that Turing's being used using up to now we're just going to number them.
We have a particular symbol on the tape at that point. Snort is the blank S1, S2 as three, as four or other symbols.
So they all have to be numbered in sequence and each line of the table.
What this will mean is if you're in state Q I and you read on the tape symbol SJ,
then what you are to do is print onto the tape symbol s k, which could of course, be the same right.
It might actually be leaving the symbol unchanged, move left and go into state Q.
And so there are three different forms.
This one's moving left. This one's moving right. This one's staying in the same place.
No move. OK, so our Turing machine, then we've we've simplified it in a sense, made it more complex in another sense.
I mean, if you if you have a Turing machine that let me just illustrate that again, if we go back to this.
Rats, maybe if you remember that Turing machine, the one that prints out the animal for one third.
This has false statements and the action in each state is very, very simple.
Whereas. This machine does the same thing with a single state, but its actions are more complicated.
It has to move moves right when it encounters a zero or a one.
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.
But there's a sense in which it's more complex because it's got more complex actions.
Okay. So in order to apply what Turing is doing here,
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.
OK, so we have a line of text consisting of quintuplets separated by semicolons.
We're going to take all these quintuplets. The quintuple is simply that that list of five things all the quintupling that
make up the machine table and we're going to put semicolons between them.
And then we have a line of text which gives a description of the machine.
In this description, we shall replace QE by the letter D,
followed by the letter a repeated eight times and SJ by Dat D, followed by C repeating j times.
So just to spell it out. Q one, that's the first step it will become a Q two will become a s zero.
That's the blank which becomes D x one becomes DC S2, becomes the DC C and so on.
So we end up our Turing machine, which started as a nice, easy to read table,
is being successively transformed so that we just end up with a line of text
consisting of letters and semicolons and that describes what the machine does.
And he calls that the standard description.
Then we go on again and we replace the letters by digits, and that gives us the description number of the machine.
So let's let's see an example here again, is that machine that we've just seen running machine one of S. three.
Okay. There we are.
That's the table when we rename the end configurations, this is quoted from cheering,
its table becomes this so you can see we've now numbered the state.
So instead of giving them all their own letter, we just called them Q1, Q2, Q3, Q4.
In every case, we're looking at the blank symbol. So it's not here.
We're printing in zero, but this one and moving right here, we're printing a one that's s two and moving right.
And so you'll notice that there's a slight additional complication here.
Where is this just says move right from St.
This is saying move right and print a blank.
It's reading a blank and printing a blank. So it's leaving the tape unchanged. Right?
So if you move and you leave the tape unchanged, you have to print back the symbol that was that.
But even if you don't move, you have to.
You can see, actually, that's going to make the tables rather more complicated because we can no longer really use a wild card.
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,
you're going to have to print back onto the take that same symbol, which means you need to record it.
So you're actually going to have to have a lot more states. But let's not worry about that.
You can see how in principle it would work.
We're still quoting cheering other tables could be obtained by adding irrelevant lines such as this last one.
So here we've got the same machine table, but we've got an extra line here.
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.
Never, ever happens. Because here we are.
It's still churning away, isn't it? What happens is in the first state you print zero.
It immediately moves, right? So you are never in the first state with a zero on the tape.
All right. You only ever encountered blanks that moves right?
And you see you come back into the first state from the fourth state just by moving right?
So it's moving right all the time. I can actually.
Stop it now. OK, so the upshot is here we've got a machine table,
which in behaviour is absolutely identical to the one before because we've added a line to it which is completely irrelevant,
which is never going to be reached. So cheering, as shown here, that many different machines can be entirely equivalent in behaviour,
if you add an irrelevant line to a machine table, it's going to change the machine.
It changes the description of the machine, changes the description number of the machine,
but actually the number that's generated by the machine will be exactly the same.
And of course, it's entirely possible to have the same number generated by a lot,
by lots of machines that behave differently, not just with irrelevant lines, but in other ways.
So it follows that you can have lots of different Turing machines,
which all generate the same computable number, which all have the same output in terms of figures.
So the mapping from satisfactory machines remember satisfactory machines of a circle, free machines,
the machines that carry on generating digits forever, like the one we just saw the mapping from those to computable numbers is subjective.
In other words, every computable number can be computed by one of these machines.
At least at Turing is right that these machines correctly capture all possible computations, but it's not going to be an injected function.
There will be lots and lots of different Turing machines that all mapped to the same computer bill.
No. OK, so I'm quoting cheering again, our first standard form would be.
So this is where he's taken the machine. He's divided up into lines, put those into Queen two falls.
No, the states, no the symbols and separated the semicolon.
So that's a single line that this is the standard description.
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.
Q2 has become Kia. Q3 has become a and so.
Okay, so you can see it pretty easily how you get from the table to that.
And now what we're doing, we're simply doing that substitution into this and we end up with that.
Then we replace the letters and indeed the semicolon by digits, and we get this, so that's all one single number.
This might remind you a little bit of what we saw with girdle.
We find some method of converting a formula or in this case, a Turing machine to a number.
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.
And the aim is to prove some theoretical result. This is the description number of the machine that has the extra state.
And I've just shown in red the the extra digits that have been added at the end for that last quintuple.
OK. To each computable sequence that corresponds at least one description, no whale, to no description, no.
Does that correspond more than one computable sequence?
OK, so a description number simply gives you a effectively a formula for generating a Turing machine.
A Turing machine can generate, at most one computable No.
Circle three. It will generate a computable number if it's not circle free.
If it halts gets into a loop without outputting any more figures, then it will not generate the immutable number.
But at most, it will generate one. The computable sequences is numbers are therefore innumerable.
OK. You can put them in a list. You can list all the possible Turing machines in the order of these numbers,
and you can thus produce a list of all the computable numbers by putting next to each description.
Number the corresponding computable number of course, you can't in practise because they're only infinite, but infinitely more and more digits.
You can't write them out. But we're doing this conceptually. OK, so it follows.
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.
They can't be put into a list. So there are far, far more real numbers than there are rational numbers, for example.
That's a kind of slightly surprising result. I mean, to a very close approximation, all real numbers are irrational.
It now follows that to a really close approximation, all real numbers are non computable.
That means actually, if you have a non computable number, it's very hard to see how we could even refer to it.
I mean, you clearly, clearly can't write it down. You can't even generate a formula to specify it.
You can't. You can't. You certainly can't write a programme that is going to generate its digits.
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.
We can't refer to them, but we know by cantors proof that they're there.
So you can see how this kind of result might stimulate quite a lot of interesting thinking in the philosophy of mathematics.
We're not actually going to go there, but I I simply point that out as an interesting consequence of what Turing has done.
I think it's it's a much more striking result than the result about there being more real than rational numbers.
They're being more Reelz than computable numbers is is more dramatic because, of course, Pi and E and so on are computable.
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
even specify them by means of giving a computer programme that will generate digit by digit.
OK, so that's that's quite momentous. Let's move on to section six.
Another really momentous result the universal Turing machine.
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.
Now there's any compute of sequence of digits, any computable number.
So up till now, we've had Turing machines, each of them generating at best one computable number.
It's a circle circle. Three machine generates one computable number. Now he's talking about a single machine generating all computable numbers.
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.
If you start with a blank tape, any given machine will generate a single computable number at best.
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.
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.
Right. So we're going to end up with a universal machine, a Turing machine,
which effectively runs from a specification of some other Turing machine and and
generates exactly the same computer for number as that of a Turing machine would do.
So if this machine you is supplied with a tape on the beginning of which is written,
the standard description of some computing machine in the Turing machine, in other words, then you will compute the same sequence as in.
OK, so Turing starts the discussion in a slightly odd way, but it's actually,
I think, quite a good way of introducing the discussion and making the point.
We can see at the end the denouement we we find we have actually done what we want to do.
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.
So we're we're going to focus on one particular case we've got a machine m a Turing machine,
and we're going to find out how we can create a machine m prime,
which will generate exactly the same computable sequence by referring to the standard description of N.
OK, so he's going to refer back now to machine to just to remind you that.
This one, the one that generates the number in which you've got successively larger numbers of ones.
Jason, followed by zero. It happened. She noticed a little bit odd.
It doesn't matter. But I just want to point it out because it might. You might find it rather confusing.
I mean, here we've got this machine, which has rather complicated behaviour.
This is not a machine in the standard form that Turing later in the paper is requiring.
We've seen that in order to produce the standard description of the machine,
we have to reduce the machine to quintuplets where it's divided up into steps and actions,
where we've got to at most one print, at most one right or left for each, each line of the table.
So actually, to produce this same behaviour by a standard Turing machine that is the form that he's using later,
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.
But that doesn't matter because what we're focussing on here is the behaviour of this machine,
what it actually outputs, and we will see how that works.
Okay, so I've just pointed out that oddity here. So we saw earlier this was on Slide 86.
And it's in Petzold book page 92 that we saw how a sequence of complete configurations can be listed.
Now remember, a complete configuration is what you see between the columns here.
The complete configuration is it shows everything on the tape at that particular point in the calculation,
and it also shows what state the machine is and where exactly it is on the tape at that point.
Right? So remember the complete configuration I explained to you in the previous lecture?
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.
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.
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.
So what Turing was illustrating here was how you could record the exact process of a calculation by listing the complete configurations.
I mean, it starts just, you know, with nothing written on the tape and it's in state B.
And then after the first step, it's got to and then a couple of zeros and so forth.
And then it goes on. Now again, as I've said, you've got this oddity that we've got quite complicated behaviour here.
If the machine was put in the standard form, we'd have far less change from one complete configuration to another.
But that doesn't mean that's the basic idea is that whenever you have a Turing machine,
whether a complex one or a simple one, you can in principle list the complete configurations one after another,
after another,
after another with columns in between and each complete configuration shows you exactly what the stage of the calculation was at that step.
OK. But. So now cheering again, he's going to modify this format.
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,
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.
So exactly as we had before. He's replacing the symbols in the complete configurations by this.
This sequence of letters, so the result of these substitutions in to see is that OK,
so you may remember see which we had before and we now get to see one.
So effectively, what these sequences are encoding is a sequence of complete configurations.
This is the sequence of symbols on f squares, he says.
What he means is remember, we're trying to produce a machine in prime which is going to copy the behaviour of a machine.
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.
So before the show was OK, there's going to be a left hand.
There's going to be a description of the machine to be copied.
The machine, which is going to be in this standard form with these scissors and so forth.
And now what Turing is saying is what we want to happen at the right-hand end of the tape is we
want a sequence of complete configurations like this to be generated in the same kind of format,
diseases and so forth. So the machine in prime,
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.
So we've no we've no longer got f squares being confined to zero and well.
He remarked that if any can be constructed, then so can him prime,
and it would operate by referring back to a copy of the standard description of him written on the tape.
So having seen the way the Turing machines work, the kind of editing that they do,
the way they can go back upwards and forwards, comparing symbols, copying them and all the rest.
I hope you will find this credible that if at the left hand end of the tape,
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.
Then what machine am prime is going to do? It's going to look at the the last complete configuration.
Oh, I see we're in that state with that symbol. Then it's going to shuffle back to the beginning of the tape.
Look at the machine table for em, and it's going to identify what it should do, given that symbol and that state.
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.
It will have a record of the last complete configuration that's at the right hand end of the tape
and a record of MS rules in the form of the standard description at the left hand end of the tape.
It will shuttle back and forth, checking the latest configuration that is the state and the symbol from the right,
then finding the rule that this matches at the left, then moving back to build the next complete configuration accordingly.
On the right side, right side, shuffle over to the right.
What's the current configuration? Okay, you go back to the left.
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,
making changes the few changes that are required by the latest action.
So it's keeping track as it goes.
Of all the configurations,
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.
And what I've done here, I've underlined the configurations. OK.
So here what you've got is the state here you've got state and symbol, here you've got state and symbol.
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.
OK. OK.
Recall that the complete configurations are separated by columns, so at the right of the tape,
we've got complete configuration column, complete configuration code, complete configuration as you see within them.
Just one state represented by D, followed by a sequence of A's,
will appear followed by the scan symbol on the current square represented by D, followed by a sequence of CS.
And I suggested that when you go through this, you might find it helpful to refer to the text on Page 151,
where during spells out these these various translations.
OK. What about the standard description? Remember, the standard description is the the left hand end of the tape.
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.
Remember, it consists of lots and lots of encoded quintuplets.
And here all the various quinta balls for the machine we're looking at here.
And what I've done here, I've shown you how the translation takes place.
So initial state be read symbol blank, right?
Symbol zero. Move right into state C.
Okay. So first of all, we no the states and the symbols. So we get initial state.
Q One read symbol, snort right symbol S1 move right into state Q2 and then the cues are being replaced by D,
followed by the appropriate number of A's. The symbols are being replaced by D, followed by the appropriate number of seats.
In the case of the blank. No signs because that s not okay.
So if you look there d a d, d, c, r d, that's the first quintuple being encoded and daddy is the configuration.
That's the state plus the symbol. That's what determines what should happen, what should happen.
After you write this symbol, you move right and you go into that state.
So if you put those two things together here on the right hand side of the tape, we've got the configurations,
the complete configurations being built up,
which is a record of what what is the case at each particular stage of the calculation you look there to see,
I mean, you look at the last configuration to be written and you identify this part of it,
the part that that gives you the configuration, the state and the symbol.
And then you shuttle off back to the left hand end of the tape and you look for the the matching trigger.
And when you find that, okay, that's the quintuple on which I need to act,
that's the quintuple which is specifying what needs to change with the configuration, you know, as a as the next configuration is written.
Okay? This is obviously quite complicated.
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,
particularly all the detail of how the universal machine is defined.
But what's crucial is to have have the general idea of how it's worked, how it works.
I mean, once you've seen some Turing machines in action, as you will have done by that stage of the book, including,
you know, Petzold ingenious machine that does the square root of two, it gives you a feel for how these things operate.
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.
You know, the universal Turing machine is certainly a possibility.
Okay. One thing we've not done, we've not yet dealt with the figures that are printed.
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.
And these are going to be colon separated between the successive complete configurations.
So you just want to explain this zero and one or a special case?
Right? All the other stuff that gets printed by the machines is working.
The zeros and ones that are printed actually specify the computable number, the number that's going to end up on the tape.
What Turing is saying is that rather than having zeros and ones printed, you know, and then printed again and again and again,
because as we've seen with each quintuple, if you if you leave a square, you then have to print it again.
What he's saying is you kind of save up the zeros and ones and you print them at the end.
So as you go step by step through the as the machine churns from one state to another, you print out a complete configuration.
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.
You'll see that if you look in the book, you'll find that that illustrated,
which makes it very straightforward to understand if M Prime has been designed designed.
Appropriately, then, this is the key move we've designed,
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
end kind of reproduces its behaviour by generating complete configuration after complete configuration of the complete configuration.
And between those putting in any zeros or ones that have to have been printed,
you can actually see that if we change the description of anyone at the left hand end of the tape,
then the same machine is going to mimic whatever machine description we put there.
So actually, we have generated a universal machine,
replacing the standard description of the left of the tape with the standard description of a different machine and will mean that
we end up with the sequence of figures that end would generate on the tape instead of the sequence of figures that we generate.
So now obviously,
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?
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.
But the crucial point is the figures,
the zeros and ones are going to come out in exactly the same order from the universal machine as they do from machine.
OK, so we end up with the same computable no.
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,
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.
So Section seven describes the universal machine in detail. It uses the kind of subroutines that we were talking about earlier those functions.
This was the first proof that there could be a universal programmable machine
capable of computing any number that we know how to compute when given the recipe.
Now, Turing here is obviously focussing on computable numbers, the generation of sequences of zeros and ones,
but by extension, it's clear that any other computer will function will be achievable by the same means.
I mean, we've we've got a method essentially for replicating the computational behaviour of any Turing machine at all.
And if Turing is right, as he argued, we looked looked at two lectures ago.
If he's right that his kind of computing machines actually capture all the possible mechanical methods of computation,
then it follows that we actually have a universal machine that is capable of replicating anything that can be computed.
So a momentous result, indeed, and we'll say a little bit more about that next time.
Thank you.