OK, today we start on Turing's famous paper of 1936, very justly famous.
The paper, which invented the Turing machine and showed that the shadings problem was unsolvable.
We're going to be going through it with the help of Petzold book the annotated Turing,
and I'll be referring to that quite a lot as we go now, as we saw last time.
If you want to tackle the incidence problem, the decision problem, then you have to have some notion of effective computer ability.
The idea is that there what cheering wants to show is that there is no effective procedure for deciding any proposition of predicate logic.
And in order to get a handle on that, he has to be able to define what counts as an effective procedure.
So what cheering does is he characterises effective computer ability in terms of the behaviour of an extremely simple kind of machine.
And the claim is that this machine can execute either directly or indirectly
all possible methods of mechanical information processing mechanical there.
As I explained last time, means that you can specify exactly what each step should involve.
No intuition, no strokes of genius. Nothing like that.
Just following a rule, the machine is, of course, universally known as the Turing machine.
So let's have a quick outline of the 1936 paper.
So first of all, he defines the concept of a computable number, and he focuses on binary fractions.
He sometimes calls these decimals. Unfortunately, we're going to call them by animals.
OK, so the concept is a straightforward one. It's just like with with decimal fractions after the binomial point is,
I'll call it the the next digit represents the number of halves, the next the number of quarters, eighths sixteenths and so on.
So it's a very similar concept, except we're using binary rather than decimal.
And what I'm hearing is going to show is that these numbers,
these by minimal numbers between zero and one are more extensive than the algebraic numbers,
and therefore there are more of them than there are algebraic numbers hints that are more of them than the raw, rational numbers.
Or at least there are more in the sense that there are computable numbers, which are not algebraic.
There are computable numbers which are not rational, though actually he's going to show that they are nevertheless innumerable.
So in another sense, there are exactly the same number of binomial computable numbers as there are algebraic numbers.
OK. And he's going to show that there are innumerable by showing that the machines that generate them are innumerable.
OK. So he's got this simple machine. He's going to use those machines effectively to define the computable numbers.
And then he's going to show that because the machines themselves are innumerable.
It follows that the numbers are innumerable. OK.
So in part one, section one of the paper, that's page 68 in Petzold book.
So when you see page numbers, they're always referring to Petzold book, which of course, contains the the whole article by Turing.
He explains the structure of the Turing machine. But first of all, we're going to talk about the justification of the Turing machine.
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.
The justification lies in the fact that the human memory is necessarily limited.
And here he refers to forward to section nine of the paper. Now I'm actually going to go to section nine now,
so we're going to look at the justification for the Turing machine before we get into the technical details.
And he's going to argue that his kind of machine, the Turing machine,
really is capable of calculating anything that a human can calculate mechanically.
That is OK. Computing is normally done by writing certain symbols on paper, we may suppose this paper is divided into squares.
I assume then, that the. Tation is carried out on a tape divided into squares.
I shall also suppose that the number of symbols which may be printed is finite.
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.
And he's claiming that without loss of generality,
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.
Now you might at this point object, you might say, but wait a minute,
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?
Well, put that to one side, actually, it's going to turn out.
No, but we're not going to argue that here.
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.
OK? A person employed to calculate things so the behaviour of the computers.
Any moment is determined by the symbols which he is observing and his state of mind at that moment.
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.
We will also suppose that the number of states of mind which need be taken into account is finite.
If we admitted an infinity of states of mind, some of them will be arbitrarily close and will be confused.
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.
And that maps into a state of mind, you know, the state in which your mind is at that point.
Bearing in mind what's happened before and also the symbols that you're looking at now.
So you may be in the process of performing an addition. That's your state of mind.
You're remembering where you are in the sum and then you look at a symbol and you act accordingly.
And what you're saying is it's reasonable to suppose that you've only got a
finite possible number of states of mind because if you had infinitely many,
then some of those would be so close together that they could be confused. They'd be arbitrarily close.
Okay, so all seems fairly plausible. It's this isn't a, you know, absolutely knockdown demonstrative argument,
but it's a persuasive case that his machine is going to be able to do all the things that a human could do.
At least, you know, it's a very strong preliminary case.
It's not. It doesn't rule out that problems might be raised later.
Okay. So the repertoire of operations that the computer can perform,
that is the person performing the calculation or later the Turing machine is going to be precisely specified in terms of simple operations.
So let us imagine the operations performed by the computer to be split up into simple operations.
Every such operation consists of some change of the physical system consisting of the computer and his tape.
We may suppose that in a simple operation, not more than one symbol is altered.
We may, without loss of generality, assume that the squares whose symbols are changed are always observed squares.
Okay, so you've got the computer. The person is doing the calculation on the tape.
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.
Only within the part that they're observing now during is saying that this is without loss of generality.
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.
Besides these changes of symbols, the simple operations must include changes of distribution of observed squares.
In other words, changing the squares that you observe. The new observed squares must be immediately recognisable by the computer.
It is reasonable to suppose that they can only be squares whose distance from the closest of
the immediately preceding previously observed squares does not exceed a certain fixed amount,
say L squares. And it may be that some of these changes necessarily involve a change of state of mind.
Okay, so the computer has a long tape on which all the calculations are being carried out.
He's able to change the squares that he observes, but only by a limited amount each time.
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.
And as you are moving your obviously your your state of mind will change because your state of mind will
have to record the fact that you are in the process of moving from one part of the tape to another.
So the state of mind is crucial because that keeps track of what you were doing at each point.
OK. The most general single operation must therefore be taken to be one of the following.
A possible change of symbol. Together with a possible change of state of mind.
The possible change of observed squares together with a possible change of state of mind.
And then the actual operation that's performed.
I mean, you know what changes of symbol? What changes of observed squares, what possible changes of mind?
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.
OK. So at any point in the calculation,
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.
That's it. And the possible changes that can result from that of just these.
OK, this is all quite abstract. It becomes easier to to see when we actually look at a Turing machine in operation.
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.
Okay, so I'm going to call end configuration a state.
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.
So I'm generally going to talk about the state of the machine as what Turing calls the M configuration.
The machine scans B squares corresponding to the B squares observed by the computer.
In any move, the machine can change a symbol on a scanned square or can change any one of the scan squares
to another square distant not more than L squares from one of the other scan squares.
The move, which is done in the succeeding configuration, are determined by the scan symbol and the M configuration the state.
Now, Turing is then going to say and he doesn't prove it, but he's right that you can actually simplify this model,
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.
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
he introduces early in the paper are actually a subset of the machines that he's just argued,
give a generalisation of the mechanical possibilities of computation by a human computer.
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.
But it's a plausible argument to say that any kind of calculation that can be mechanically specified
in such a way that a human could carry it out can also be carried out by a Turing machine.
OK, so what does the Turing machine comprise?
You've got a potentially infinite type, and it's divided into numbered squares and you can write symbols on the squares.
You can rub them out, you can erase them, or you can write new symbols on top.
OK? You can only have one symbol on a square at any point and then you've got a read write head.
I mean, most of you are too young, probably to remember tape recorders,
but the the idea of a read write head is that when you write to the tape that happens purely on the square
with that head is seated and the head moves up and down the tape reading as it goes and writing as he goes.
And the only reading and writing can be done through that head at its current position so that can scan the symbols,
and it can also write them or erase them.
Then you've got the state, as I say, Turing calls it name configuration, which takes any of a specified finite range of values.
And that's the active memory of the machine, and the computation always starts from the first initial state.
And then you get instructions in the form of a machine table which tell it what to do in each possible circumstance.
OK, so we're now going to see a Turing machine in action.
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.
And if this works, we're going to see it in action. Here we are.
So this is this is the turtle system, which some of you may know.
It's a system designed to teach programming. And in it,
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.
OK, so here we've got the Turing machine.
You can see it. It's working away and down.
Here we've got the machine table. OK, so the end this is I'm copying Turing's layout here.
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.
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.
You move, right? You prints an X and then you move rock again and you stay in state for it.
If, on the other hand, you're in state three and you encounter a one on the tape, then you move, right?
You print X right again, so you're doing exactly the same and you stay in the state.
Three. So in fact, the the actions are exactly the same for a zero or a one.
But if you encounter a blank, then instead.
In other words, no symbol you move, right? You print Z.
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.
And we've got not we've got the axe symbol there.
That's the nearest you can get on a computer keyboard to the show-offs symbol,
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.
You've got the possibility of specifying a blank. None.
And you've also got the possible.
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.
If you encounter anything else, you move left in the same state, too.
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,
and that switch cheering puts it is a sort of marker of the left of the tape.
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,
left, left, left left until you encounter the schwa and then you will go right and go Interstate three.
So that gives a simple example of how you can go through a tape, right?
That's that's taking quite a long time, isn't it, actually? How can I do this?
Let's see. And we know it's outputting at the bottom of the screen.
You can see it's outputting all the. Hmm.
Stephanie. And this is actually generating a number, which is probably a a transcendental number.
It's certainly irrational.
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.
It's never recurring. OK, we'll come back to that.
I'm going to escape from that now.
So that should give you the idea of a Turing machine. Now another use of the word configuration.
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.
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.
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.
And as we've seen, it can only take that into account in its behaviour in determining its next action.
The only thing that matters? Well, the only things that matter of the state.
What? What your ankles, the M configuration, the state of mind and the symbol on the current square.
And this combination the M configuration and the scan symbol of a current configuration of the machine.
So configuration is shorthand for those two things combined the state and the symbol.
At each stage, depending on the configuration, the machine can either erase the symbol or write a new one can move.
The scanning had one place left or right on the tape and can change to a new state.
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,
this one you can see in the table that sharing is allowing multiple actions here.
Right? I mean, here in particular, we got the shaft move right print of schwa move, right?
Zero right. Right print. Zero net flat. But a lot of actions taking place there later in the paper.
CHEERING it is only going to allow a single type of each action at each step.
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.
And during the paper, you'll see that he sometimes goes one way, sometimes the other.
In general, when he's explaining Turing machines and their power early on, he allows multiple actions.
But then when he's doing his proof, he wants to restrict them.
So it's as well to be aware of that. OK, section two of the paper, we get some definitions.
Turing is going to focus on automatic machines, though he mentions choice machines in passing.
Any machine is going to have a limited range of symbols that it can read and write,
and Turing is going to distinguish between what he calls figures digits,
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.
OK. And the crucial point here is remember that Turing is interested in computable numbers, in particular computer bull by animals.
So he is interested in fractional binary numbers, which consist after the binomial point of a sequence of zeros and ones.
So zero and one, especially when they get printed on a tape in general, they are not going to be erased.
They are going to be there for good.
And Turing is going to build up these by animal numbers by adding one after another, figure zeros or ones again and again.
Meanwhile, the other symbols are going to be used for working. So he explains that his machines will write figures only on alternate squares,
so the figures that is the digits zero in one will only be written on what he calls squares and the intermediate squares.
The alternate squares are going to be used for working. He calls them E squares, probably erasable.
So we then get a clarification here.
If a symbol beta is on an f square s and a simple symbol,
Alpha is on the square next on the right of s then s and beta will be said to be marked with alpha.
The process of printing this alpha will be called marking beta four s with an alpha.
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.
If you find that little bit confusing, it'll become very clear.
So an automatic machine, as Turing is going to consider them, starts from an absolutely blank tape in its initial state.
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.
You can define, for example, a cheering machine that will multiply two numbers.
And you may need to start out with those numbers written on the tape.
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.
You've got three and four on the tape effectively. And then you set the machine going and it multiplies them.
Okay? Turing's machines aren't like that. He starts from an absolutely blank tape,
and the machine is going to generate everything that comes onto the tape without any initial input from the tape itself.
OK. And the machines he's interested in are going to generate a sequence of digits, a sequence of figures, zeros and ones.
And that sequence is called the sequence computed by the machine.
The real number, whose expression as a binary decimal sic there is saying, Look, that's the way Turing says it.
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.
A binary point, please, is called the number computed by the machine and insurance machines.
The binary digits of this number are supposed to be printed left to right on successive f squares and never erased.
So let's just take a look at part of the tape while this is going on.
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.
These are figures written on f squares. Alternate squares, notice the zeros and ones.
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.
And we say that the one here is marked with that X.
OK. So you can see how a symbol written on one of the erasable squares marks the adjacent square to the left?
OK. So in this case, the computed number that's being shown so far is zero zero one zero one one zero.
Now, the machines that Turing is interested in are machines that go on writing digits forever.
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.
These define computable numbers. OK, bear in mind, we're interested in in by animals non terminating by by animals, you might say.
Well, what about those that terminate? Well, if they terminate, then it's just zero zero zero zero zero zero on forever.
That's fine. OK. So what we think of as a non terminating by animal is in sorry,
the terminating by animal is in fact the same as a non terminating by animal that just has zeros at the end forever.
And Turing is going to call a number that defined such a circle machine free machine a satisfactory number.
So the satisfactory Turing machines, the one that Turing is happy with all the ones that go on printing forever.
He calls these circle free and one that stops writing out binary digits.
He calls circular. Now this seems a little unnatural to us.
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.
So you need to put that thought out of your mind. Right? And a circular Turing machine is one that gets into a loop.
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.
So the name of the game is to produce an infinite volume. Okay.
During is interested in the number that is generated by a machine, and those numbers go on forever.
Of course, in practise, you'd never be able to display a tape with that.
But the point is that the number is defined by the machine. OK.
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.
The number of the scanned square.
The complete sequence of all symbols on the tape and the M configuration, the state will be said to define describe the complete configuration.
At that stage, the changes of the machine and take between successive complete configurations will be called the moves of the machine.
OK, so suppose you are computing something following the instructions of the Turing machine.
OK, put yourself in the position of the Turing machine.
So you have this tape, you're carrying out the operations in exactly the way prescribed.
And then the dinner bell rings. Or you've got to go to a lecture and you've got to put everything away.
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.
What information do you need to record in order to be able to continue in the same way?
Well, you need to record the complete configuration, right? You need to record everything on the tape.
You need to record where you are on the tape and you need to record your current state.
Yeah. And as long as you do that and you start again, you know, using the same machine table, everything will go fine.
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.
Okay. So you can think of the complete configuration as showing the the state of the entire calculation at any point.
OK, that's a lot of setting up. Let's now look at some examples of machines.
That is the binomial number for one third. OK, let's let's look at some machines that generate that.
Here's one you can see it's just printing out.
Zero one zero one zero one. And so on forever.
How does it do it when it starts in state one, it encounters no symbol on the tape.
Of course, it's a completely blank tape to start with. It prints the zero and moves right interstate to.
In state, too, of course, it encounters the blank again. It moves right and goes, Interstate three doesn't print anything.
But that means we've now had to move to the right in state.
Three. It proves one and moves right and goes Interstate four.
And then in state four, it moves right. Doesn't print anything and goes into state one.
And we're back where we started. OK, very simple machine.
You can see it is generating the by animal for one third.
So one third is therefore a computable number.
You can specify a machine which will generate the infinite sequence of digits that make up the Baynham over one third.
OK. Let's look at another machine that generates the same thing.
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.
Blank, it prints a zero. Stays in the same state, of course, there is only one state if it encounters a zero.
It's just sprinted to zero, hasn't it? So second time around, it doesn't count for zero.
It moves right to spaces and free zone. And again, it stays in the same state.
If you can count as a one, it moves right to places and prints zero and again stays in the same state.
And from then on, he just alternates between these two that are right.
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,
you can do that. All right. Okay, so.
So that's why we've got two different machines here that print that by animal.
One of them is in the sort of strict form of the Turing machine, where you've only got one Operation PC configuration.
One of them is in the abbreviated form. So that simply says what I'm asking you,
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,
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.
I'm going to use this this font when I'm reproducing those.
But he chooses letters which have a sort of mnemonic quality like beginning.
So here you can see in the first state it prints are zero means right, then that puts it in the second state.
It then moves right again, beats one and moves right, moves right again and so on.
OK. And this shows a simplified table where we're allowing multiple operations with a single configuration,
so that's the table for the simplified cheering machine we've just seen.
OK. Then we get the more complex example that we've actually already seen.
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.
It's a nice example because it shows straight away.
Here is a number that clearly is irrational.
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.
And this never occurs. You can see that straight away. OK, yeah.
I mentioned just in passing that on Turing's tapes, he always puts two schwa characters at the very left.
And when you get two blanks, always indicates that you're at the the other end.
OK, so if we look at.
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.
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.
Okay, so he's going to make sure that you never get two blanks in a row in general, except then.
OK, so here we've got the the one that's generating that transcend number two shows here.
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.
It's pages and you'll see, OK? Right now, touring illustrates the working of that machine with a sequence of complete configurations.
This is going to turn out to be very important.
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.
It tells you everything about the current state of your calculation and what cheering he's going to do then,
is actually end up listing these as a record of the calculation.
So if you take a look at this format here, what you've got is between the colons.
You've got a sequence of complete configurations and the what the complete
configuration shows is the current state at each point and what is on the tape.
So here what we've got is schwa schwa zero and the state name that is showing where on the tape we currently are.
Sorry about schwa Chuck Schwab zero, space zero and the the oh, that is showing that we're in state.
So at that point, then here we've got Schwab one zero, space zero and now we're in state queue at that point.
Okay. This format is flanked this.
See, this is we're going to come back and look at that later. And I mentioned the two pages in Petzold.
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.
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,
but by the time you've got through it, you will understand pretty well how they work.
Petzold gives a couple of examples which I'm going to show you here, and this is the binary counting one.
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.
And you might notice that the take is moving backwards rather than forwards. OK,
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.
But what it's doing is it's giving a nice example of how you can do more interesting things with Turing machines.
And what I really like, I have to say, I think it's really clever.
So this is a Turing machine for calculating the square root of two in binomial.
Now it's going to take a long time. So what I'm going to do if this will work is click the good.
I had this running two million steps this morning and generated, I think it was 34 by animal digits of the square to two.
And I checked it and it was right.
Well, you know, when I multiplied by it, by itself, I got lots of ones indicating that it's getting very, very close.
You know, it's square is very close to to to.
Very clever. I mean, there's a lot at stake. That's not the whole table. But I can confirm the petzold is right.
His machine actually works. And one of the nice things that we can do, that cheering, of course,
couldn't do is actually run simulations of the various machines and check that they do work.
That it turned out that there were various misprints in Turing's paper which are mentioned in Petzold,
but there are no misprints in Petzold specification of this machine.
OK. Now, before finishing this lecture, I want to introduce you to something which is,
I suspect, one of the most difficult things to understand about Turing's paper.
So when you go on to Section four and you look at the abbreviated tables there, you might initially find them extremely puzzling.
So I'm going to take you through an example, and I hope having gone through that example,
it will help you to understand all the others that are introduced there as well.
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.
So he uses what he calls skeleton tables to define Turing machines or to define part of the activity of Turing machines.
And these make use of M functions, as he calls them,
which enable many different end configurations that is status to be defined that have very similar behaviour, but with slight differences.
So, for example, we might want our machine to do more or less the same thing, but on different symbols,
sometimes on zero, sometimes on one, sometimes on alpha, sometimes on beta and so on.
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.
So we might have to say three states which we use to handle alpha.
Another three states very similarly defined, but with beta instead of alpha and so on.
So let's take a look at the M function fine.
So this is the first one that's introduced. OK. So when you when you see these things right, that's quite puzzling.
You think what on earth is going on here? I thought M configs were meant to be simple things like letters or maybe numbers.
But now we've got some complicated function as an m config.
How does that work?
OK, here's the most important thing when you see something like this, remember that in any particular case, those are just ordinary states.
What this is doing is describing the state in a in functional terms.
So that might be state 314, 315 316.
But suppose we want to remember, we want to keep a note for ourselves.
What is it exactly that state 314 does? Oh, that's the state that searches for an alpha.
And if Alpha is found, it goes into State C.
And if an alpha is not found, it goes into State B, OK, that's what state 314 does.
Oh, how does it do it? Well, it does it by using state 315 and 316, what do they do?
Oh, don't worry about what they do, but they're just defined like that with C and B substituting accordingly.
Got that! So what we've got here is a pattern which we can use to add three new states into our Turing machine.
And if we define them like this with C and B and Alpha appropriately substituted,
then that gives us a means within our Turing machine of performing that find operation to repeat,
find an alpha on the tape if it is found going to state C if it isn't found going to state B.
In fact, it searches for the left most alpha symbol, as you see at the bottom.
Okay, so let's see how that works then. Rather than using the table, it's much easier with a diagram.
So I've said this could be state 314 353Nm 16.
It doesn't matter, right?
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.
Okay, so we go into this state, remember that's just a state, right? I know it's got a complicated functional label there.
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.
Just the machine moves left and stays in the same state.
So it goes left, left, left, left, left, left, left left until it encounters a schwa.
When it encounters Ishwar, it goes left and goes into this other state.
315 state 315 has been defined in such a way that if an alpha is found, it goes into State C.
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.
And if you didn't cancel blank, it goes into this state, which states a 360.
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,
it goes right, right, right, right, right, right, right.
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.
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.
How do we know that we're at the right hand end of the tape? Answer two blanks in a row.
How do we test for two blanks in the row? Well, if we find one blank, none, we go into this intermediate state.
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.
If we've only had one blank, not two in a row, go back to that state. So all right, everyone.
Happy. Good.
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.
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.
If it finds it, it goes into State C at that point.
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?
OK. So again, note that these are just functional labels for the three states whose behaviour specified here these 19 states 314,
315 316 say of the relevant machine. But the point is that when the first of them is entered,
the machine will either find the leftmost alpha on the tape and Interstate C on the square or fail to
find an alpha and then to state the on the square to the right of the 32 blanks at the right handed.
Okay, so that specifies exactly what's going on now when you go through that chapter, having understood this one,
I hope you will find that the other skeleton tables are pretty straightforward as well.
You do not need to understand absolutely every detail of how these work.
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
and at least go in detail through enough of them to give you confidence that you could understand the rest.
OK. And on that note, I'll finish today and we'll look more at this next time.
Thank you.