Right. Today is our last lecture on Turing's 1936 paper, so we'll be coming to the culmination of that.
There's quite a lot of technical stuff in this lecture. You've got the handouts.
I'm not going to be going through all of it in great detail.
But the idea of having it on the slides and on the handouts is I hope to make a bit more accessible.
Some stuff that really is quite difficult. It points to the key issues, the key passages,
and I hope you will find it helpful when reading Pezzullo's book and Turing's paper to look at these slides at the same time.
So some of today's stuff I'll be going through quite quickly, some of it lingering a bit more.
Okay, so Turing has shown that the computable numbers are innumerable.
We saw that last time. But there's a bit of a puzzle here that he remarks on.
Remember cantors diagonal argument from our very first lecture?
Now, it might seem that a similar kind of argument can be launched against the claim that the
computable numbers are innumerable because if the computable numbers are innumerable,
we should be able to form a list of them. Or at least it should be possible in theory to put them all in a list.
Of course, what we're concerned about is binary fractions, endless sequences of zeros and ones.
So let's imagine that we have those all in a list. Every single computable number occurs somewhere in that list because they are innumerable.
But now suppose we do a cantor and take the digits down the long diagonal and switch them.
So whenever there's a zero in one of these digits, we change it to a one whenever there's a one.
We change it to a zero. It looks like that is going to give us some well-defined number,
but that number is not going to be in the list because it will differ in the ninth place from the ninth item in the list.
So doesn't this refute the claim that the computable numbers are innumerable?
Well, no, not exactly. It looks like it might, but it's only going to refute that claim if in fact,
that number is itself computable and we haven't shown that it is computable.
How can it fail to be computable? We're going through the integers one after another.
I mean, imagine that we just go through, you know,
zero one two three four five six and whenever we hit a number that could be the description number of a Turing machine,
we use that to construct, construct the standard description and then we simulate that machine.
We know from the universal machine that it's possible to do that.
So why don't we just do that repeatedly mimic in turn, the first, second, third, fourth, fifth machine and so forth?
Find out what the institute is, swap it and then move on to the next one.
Why won't that give away of computing this diagonal number beta?
Well, the answer is that it's not enough.
When we are generating these machines,
we're going through looking at internet every integer that can be the number of a Turing machine, and then we're running it.
It's not enough just to know that it is the number of a Turing machine.
We've got to know that it's the number of a circle free Turing machine because only circle free Turing machines,
that's the one ones that carry on generating zeros and ones.
Infinitely only those generate computable numbers.
So the construction must fail at that point. All right.
I'm Turing has argued, after all, that all computable numbers are innumerable. That looks like a very strong argument.
We have an argument here that seems to refute that.
Well, if the argument earlier was correct, this attempt must fail.
And here is where it must fail that if you are trying to compute that number beta the diagonal number,
it must be that as you try to construct these Turing machines that generate those numbers,
in turn all these computable numbers, you cannot identify whether the number is actually the number of a Circle three machine.
So Turing concludes that the cannot be any general process for finding out whether a given
number is the description number of a circle free machine in a finite number of steps.
So there's no computable way of working out whether a Turing machine in general is circle free.
Now, cheering remarks that the reader might find this a little bit odd.
The argument seems a little bit contrived. So he backs it up with an explanation of exactly where he thinks the attempt would fail.
So imagine that you have some machine, some Turing machine, which is attempting to construct this no beta.
Well, that machine itself must have some description. No, let's suppose its end.
And that machine, in order to create the digit of this number,
beta is going to have to first discover what is the ninth digit of machine with description.
No end. And then it's got to flip it so we can see actually,
we get a contradiction because what it's trying to do is find its own entry digit and then output the inverse of that.
In fact, it's going to get into a loop, isn't it, because it will be trying to find its own digit?
It will go through all that process in order to find its own digit. It has first to find its own digit and we will get into an infinite loop.
Now, although this isn't strictly Turing, I want to just pop in another diagonal argument here, which is somewhat reminiscent of this.
It's also reminiscent of cantors and girdles, and that is the proof of the halting problem.
Now, it's not quite the same as what Turing is shown, but it's very similar.
Turing is has shown that no Turing machine can be devised,
which is capable of telling whether some other Turing machine in general will or won't be circle free.
Whether it will or will not continue printing zeros and ones forever.
What we're now going to show is that the halting problem is unsolvable and this is something you might well have come across.
It is striking how easy it is to show this, and you will see that the reasoning is somewhat reminiscent of of Turing's.
Okay, so here's the Turing the halting problem x here we can forget about Turing machines for the moment.
Just imagine that you have a general all purpose, standard programming language,
and imagine that we have the text of a programme in that language p and that programme takes input from a text file.
T So we've got two files. One of them is the text of a programme in the standard programming language.
One of them is the text of the input into that programme.
So to solve the halting problem, what we want is a testing procedure, let's call it H.
Which will examine the text of the programme and the text of the input, and it will then reliably work out the answer to this question.
Will programme P when run with input t eventually halt or, on the other hand, will never terminate.
And Turing's argument, or very similar argument implies that h is impossible.
Notice there's a little irony here in that when what Turing thinks of as a satisfactory Turing machine is one that actually goes on forever,
whereas generally with programmes, a satisfactory programme is one that terminates.
So there's a slight difference there, but it's the same kind of principle. OK, so let's suppose we have here programmed h.
This is our hypothetical programme, which is going to solve the halting problem.
So it takes two inputs the text of a programme, the text of the input, and then it decides whether or not the programme p would halt given that input.
If so, it prints. Yes, yes. Meaning it will halt.
If not, it prints. No, no, meaning it won't halt.
So it goes up the Green Line. If if it will halt the Red Line, if it won't.
Now what we're going to do is modify that programme. Let's suppose that Programme H is a possible programme.
We're going to modify it both at the input and at the output, the input instead of putting the text on the programme in a separate inputs.
We're going to put the text of the programme p in as both inputs, and you might think that's very odd.
How often do you have a programme which takes its own text as input, but not often?
But what we're doing here is showing a case that gives rise to a contradiction.
So no reason in principle why we shouldn't do that. And you can see this is very straightforward.
All it involves is duplicating file p and then putting that into the input where T would have gone back.
We're modifying the outputs. Well, one of the outputs, the one that goes up the Green Line.
In other words, when the H makes the decision, the thing will hold.
We're changing it so that instead of printing, it repeatedly prints yes, until zero equals one.
In other words, until [INAUDIBLE] freezes over, it just goes on printing.
Yes Yes. Yes Yes. Yes Yes. Yes. Yes, yes. Forever. OK.
So both of those modifications are straightforward modifications. If Programme H is possible, then the modified programme is possible.
Let's call it keep his our modified programme. Now you've probably guessed what we're going to do is ask what happens when we
feed programme Q as input into itself again may seem a strange thing to do.
But the point of doing it is to show that H is impossible because if we feed Programme Q into itself.
Then, H, this hypothetical programme that decides whether a programme will halt, we've given input,
what that will do is decide where the Programme Q will halt given itself as input, if it will halt given itself as input.
We go up the green. Oh, but that never holds.
So that's a contradiction. Only in that case, it must decide that it doesn't hold open in that case, it prints no insults.
So either way, we get a contradiction. If it halts, it doesn't help.
If it doesn't call, it halts. So therefore, Programme H is impossible.
You cannot have a programme that in general solves the whole thing problem.
And you can see it's a similar kind of reasoning in many ways to Turing's, but a very, very powerful result.
Reach just in three or four slides. It's quite astonishing that that that can be done.
OK, so one point about putting that argument here is if you had any suspicion that
Turing's argument was dubious because it's kind of circular nature here,
we've got an example of a similar style of argument,
which is so straightforward that I hope you will find it very plausible to see that argument just is decisive,
that there's no funny business going on. It's a relatively straightforward argument.
OK, so Turing has shown that no Turing machine can provide a reliable circle free test.
He now goes on to prove a lemma, which will be very important later on.
We can show further there can be no machine e, which, when supplied with the standard description of an arbitrary machine,
M will determine whether M ever prints a given symbol.
Zero say. OK, so this theme is going to crop up quite a lot.
Take a particular Turing machine or the description of the Turing machine and ask Will that machine ever output a zero on its type?
And we're going to suppose that there is a programme that can determine that reliably, and we're going to show a contradiction from that.
OK, so suppose we have zero testing machine e and it's going to be applied to some arbitrary machine.
And so we've got some Turing Machine M and we're putting that description on our tape.
And what is supposed to do is determine in a finite number of stages whether M will or won't ever print a zero.
Well, you can probably see that it's not too difficult to modify Machine Am to produce other machines M1 into IN3,
et cetera, et cetera, which are just like M, except that they print out fewer zeros.
So one of the first of them, M1, just prints one less zero and two prints, two fewer zeros and three prints, three fewer and so on.
It's easy to see how to do this because what you do,
you simply imagine a machine that precedes in exactly the same way as M and then when the first zero comes out or would come out instead of printing,
if it goes to some other state and then goes back processing again, keeping a note of the fact that that's one down.
And then next time it comes across as zero, it just prints it out normally so.
So that will end up printing one less zero. And likewise, by having extra states, you could produce a machine and two that prints two fewer and so on.
OK, so now what we're going to do is create a Machine G fromI, which operates by mechanically testing and M1, M2 and so on, and outputting a zero.
Each time, if and only if, E! Would decide that the tested machine would never generate a zero.
OK, now that's all a bit confusing, I think, but it's much easier to understand if we look at an example.
OK, so here is our machine m and let's suppose M just for the sake of the argument.
Suppose M outputs exactly four zeros when run.
OK. In total, machine M1 therefore will avoid printing the first zero, but then we'll print the rest.
So it will end up printing three zeros machine and two will avoid printing the first two zeros.
I'll just put a five year instead of sort of arbitrary output,
and then it will print two zeros and three will print for three days and then one zero and four will print no zeros at all.
And five will print no zeros at all. OK, now our machine.
G What it will do if if the machine is testing does print is zero, then it will output nothing at all.
Whereas if our machine does not print zero, it will output a zero.
It's not OK. So here we've got the case of a machine and that outputs four zeros.
We've got the adapted versions M1 end to end three and four and five.
We can see how many zeros those output and then G outputs a zero.
If and only if the machine is testing at that point does not output zero.
Now imagine and one and two and three and four and five and six and seven and all the others.
Do you agree? All the others after M5 are going to output zero.
Yeah, we we're going to get a zero from G. Every single time from now on.
So we will end up with an infinite number of zeros. How could that fail?
How could we not get an infinite number of zeros from machines?
Well, only if and itself printed an infinite number of zeros.
If any prints an infinite number of zeros, then in one and two and three,
will all of them carry on printing an infinite number of zeros, in which case G will never output a zero?
OK, so we now have a test, whether or not any prints zero,
infinitely often what Turing's done is devise a clever way whereby he can transform the test of whether a
machine ever prints zero and he's made from it a test of whether a machine print zero infinitely often.
So if the machine exists, it follows that we can create a general process to determine whether any machine in print zero infinitely often.
And clearly you can do exactly the same process for one.
So this is quite clever.
If we have a test for whether a machine will print zero infinitely often and we have a test for whether a machine will print one,
infinitely often we can combine those together because if the answer to both of those is no,
then it means we've only got a finite number of zeros and a finite number of ones, in which case we have a circular machine.
We have a machine which is not going to carry on printing digits infinitely.
So if machines were possible, then it would be possible to produce a reliable test for whether a machine is circular or not,
and cheering has already shown that that's not possible. So therefore, Machine E isn't possible either.
OK, that's a little bit mind bending. It's this is not at all easy.
So, you know, if you find this a bit confusing, don't worry.
I mean, remember, Turing has shown that there is no machine that can reliably test whether a Turing machine is circular or not.
He's supposed that there's a machine that can test for whether a machine ever prints is zero.
That's machine e.
And then he's shown that if Machine E were possible, this other Machine G would be possible, which would actually provide a test for circularity.
Therefore, Machine E isn't possible. OK, so this important memories proved you cannot have a Turing machine,
which is able to test another Turing machine for whether or not it will ever print a zero.
That's going to be crucial for yielding the final result of Turing's paper regarding the incidents problem.
OK.
Section nine sharing wants to show that the computable numbers that he's defined include all numbers, which would naturally be regarded as computable.
This is generally known as the church sharing thesis. The church during a thesis basically is the thesis that Turing machine compute ability,
or a couple of other equivalent notions that will come across do successfully
characterise what we think of as computable the intuitive notion of computer ability.
He proposes three types of argument for this claim, and the third one is in section 10 will come to that very briefly later.
The first type of argument we've already looked at in the third lecture,
we saw Turing's argument that a Turing machine is a generalisation of human calculation.
Anything that can be calculated in a human way, Turing has argued, can be done by the Turing machine.
The second argument, I think, is certainly the most influential cheering argues essentially that Turing machine computer ability,
the kind of compute ability that he's defined, coincides with other important notions.
And one of them is to do with what is calculable using the Hilbert functional calculus that first order predicate logic.
And we will see some of that later. But first of all, cheering sketches how a cheering machine can be defined to generate,
in turn, all provable formulae of a system of axioms expressed in predicate logic.
This is what's commonly called the British Museum algorithm. He basically says, Look, suppose you've got a system of logic defined by certain axioms.
Imagine producing a Turing machine, which in turn goes through all the possible formulae,
generating all the possible proofs one after another, after another after another.
This is, in theory, possible. I'm not going to go through the detail of that, but do look at it in Pezzullo's book.
So cheering is argued in effect that anything computable through predicate logic can be computed by Turing machine.
That the numbers definable in terms of predicate logic by the use of axioms include all the Turing machine computable numbers.
So he sketched a proof that these two ways of defining compute ability, at least in their application to numbers, come out to the same thing.
OK. Now, unfortunately, Turing's magnificent paper that we've been studying, he sent it off in 1936, but it turned out that six weeks earlier,
Alonzo Church had published or sent for publication a paper a note on the children's problem,
which also showed that the children's problem was unsolvable.
So poor old Turing, he put all this work into showing that Hilbert dream couldn't be realised,
and then he found that somebody else had got there first. Now, Church had done it using his lambda calculus, which many of you will know about.
But Turing, of course, has done it in a completely different way.
And fortunately, it was considered sufficiently novel and significant that it was worth publishing,
despite the fact that its key results had already been scooped.
But what the editors did was asked Turing to add an appendix in which he showed that lambda defined ability as church,
a device and his own during machine compute ability were coincident.
And again, you can look at the book to see the detail of that.
He published another paper, Computer Bility in LAMDA Define Ability, which started like this.
Several definitions have been given to express an exact meaning corresponding to the intuitive idea of effective calcul ability,
as applied, for instance, to functions of positive integers. The purpose of the present paper is 1937.
Paper is to show that the computable functions introduced by the author are identical with the lambda definable
functions of church and the general recursive functions due to her brand and girdle and developed by cleaning.
It is shown below that every lambda definable function is computable and that every computable function is general recursive.
So this filled the last piece in that jigsaw. It showed that these three different notions actually completely coincide.
Now, many people thought that that's pretty strong evidence to the church during thesis.
Suppose you're trying to prove that the informal notion what what Turing calls the intuitive idea of effective calcul ability.
You're trying to show that there is a particular way of pinning that down.
Well, you try various ways you come up with or people come up with three different plausible ways, and it turns out they're exactly coincident.
That seems to give strong some strong evidence or at least significant evidence that whatever other attempt we may come up with.
At best, it will yield something that's equivalent. There's something a little philosophically odd.
It may seem about the whole idea of pinning down precisely an intuitive notion if you have an intuitive notion like effective calcul ability.
How can that possibly line up precisely with a formal notion?
But it is certainly striking that all attempts to do this have come to the same thing.
And one can argue that really, the formal process applications turn out to be what we should mean when we talk about effective calcul ability.
We might start off with some intuitive notion, but actually it may be that the only way of really making that precise in an acceptable
way is going to lead in the same direction as Turing Church Girl and so forth.
OK. We're not going to talk more about the church during theses, though it's obviously a very important legacy.
Section 10. I'm just going to summarise during gives examples of large classes of numbers which are computable.
All sorts of results. I mean, all the things that you would naturally think of as computable turn out to be so.
And again, this is given by Turing as an argument for supporting his notion of Turing complete ability.
OK, then finally, we come to the application to the end problem, the denouement of the whole paper.
This is what it's been building towards. Some of this, as I've said before, is very technical.
Some of it, I'm just going to skate over relatively quickly.
I'm not going to go into all the gory detail here, but I hope you will find that the general ideas are comprehensible.
OK, so Turing is going to show that the shadings problem that is Gilbert's decision problem is unsolvable,
and he's going to show that for any machine in,
it is possible to construct a formula of predicate logic that is equivalent to the statement that M at some point prints a zero.
OK, so we've seen the significance of this churning has already shown that you cannot produce a Turing machine,
which is able to determine if some other Turing machine, you know, machine description, whether or not a zero will eventually be printed by it.
What he's now going to do is to show how using predicate logic, we can provide a description of a machine.
And also, we can produce a predicate logic formula, which is equivalent to the statement that a zero will be printed by that machine.
Now, if in fact, Turing's right that it's not possible to produce a Turing machine which is
able to determine whether some arbitrary machine will or will not print zero,
it immediately follows that that formula of predicate logic cannot be decided.
The formula that is equivalent to saying there's an arbitrary machine will print to zero.
So that's how the argument is going to go. I propose, he says,
to show that there can be no general process for determining whether a given formula you of the functional
calculus K that is Hilbert is restricted for functional calculus predicate logic without identity.
By the way, the mean general process for determining whether a given formula you predicate logic is provable,
i.e. there can be no machine which supplied with any one.
View of these formulae will eventually say whether you is provable, this is different from girdles result.
We've already seen that. In the second lecture, Turing explained to OK during remarks that the proof appears somewhat lengthy,
but the underlying ideas are quite straightforward. You might, if you were to read the paper by itself,
think that actually it wasn't lengthy enough and that a great deal more explanation would be useful.
Pezzullo's book, of course, provides that explanation,
and I hope you'll find that these lectures will succeed in identifying the points that might otherwise cause difficulty.
OK, so what I'm hearing is going to do is characterise a Turing machine using certain predicates,
so these are three of them I K and R I X Y says in the complete configuration X, the Square Y is scanned.
So that's the current square in the complete configuration.
X the end configuration state is QM, so K, QM X and X is a number telling you what cycle the machine is through.
Zero one two three four. How many cycles has it gone through? So which config complete configuration are we on?
QM is one of the states, and this is asserting that on that cycle, it has this particular state.
Are in the complete configuration x of them, the symbol on the square.
Why is SL so you've got a whole range of these predicates, one for each state, one for each symbol.
Oh, by the way, I'm calling those scanners state symbol, I've put them in a different order from Turing and Petzold.
I've put them in alphabetical order here, and I'm going to keep the same order in the various formulae.
If you look at my slides and you see they're different from the ones in the book.
That's why I'll just call it scan state symbol. You've got those formulae, OK?
Those predicates enable us to specify any complete configuration of a Turing machine in terms of the step number, the cycle of that configuration.
OK, now the Turing machine rules the quintuplets. You know, the ones that say, if you're in this state and you're scanning that particular symbol,
then do this move right, move left, stay the stay in the same place.
Print one thing, one symbol or another and move to a different state, etc. Those quintuplets need now to be represented.
Turing is also going to need predicates that handle numbers, in particular, expressing that one number is the immediate successor of another.
So if X Y will mean essentially that Y equals X plus one.
And he will see that cropping up quite a lot. OK, so let's take a particular example, suppose our machine includes this quintuple q i sj k el que el.
So that's saying if square if in cycle X of this machine.
Square Y is scanned in state Q AI and while containing symbol SJ.
So remember that's that the trigger configuration. You've got a particular state and a particular symbol.
Then this quintuple basically specifies a rule that should be applied,
which is that in the next cycle, let's call that ex prime square y will change to symbol ESC.
Okay. The third element of the quintuple. The machine will move left, and let's say that that moves it to square.
Why prime? And Square, why?
Sorry. And it should move also into state que el. So that's the the last element of the quintuple.
Okay, so this is moving left. So although x prime equals x +1 because we're moving from cycle X to cycle x prime, so we're moving on a step.
So x prime is x +1 y prime.
That's the new square to which we're moving is y minus one because we're moving left.
Not right. OK. And in cycle X, these things are true.
Right? Set Square Y is staying with the machine is in state Q I on Cycle X and on Cycle X, where Y contains symbol S J.
If the quintuple is applied on Cycle X Prime, now we're scanning Square y prime.
We've moved into State Q and a square y now contains S.K.
Okay, so notice that we're scanning Square Y Prime, but it's Square Y whose symbol has been changed to the square that we moved from.
OK. We also need to express that all squares other than Y will contain the same symbol in the two cycles.
All right, so there's only one square whose symbol changes. OK.
So we get this formula during calls. This Inst followed by the quintuple.
And notice that the formula will be different depending on whether we've got LR or N.
This is the left moving formula. So let's just get through that for all y x sorry, x y x prime and y prime.
If we are in the scan state symbol condition for cycle X, which we've seen and if.
I'm sorry. That is the wrong way round. That should say X crime equals x plus one, I'm sorry.
And y prime equals y y minus one. OK, thank you to the conditions we have before.
Then we should have the scan status symbol, a condition that we saw before and for all Z and either Z is equal to Y.
Notice what this means is that Z is one greater than y prime.
And notice that Y is also one greater than y prime.
So this effectively means that Z is equal to Y, which is the square we've moved from.
So either Z is the square we've moved from, or Z contains exactly the same symbol in Cycle X prime as it contained in X.
OK, so we've got one formula here for every single possible symbol.
This is a zero, which is blank. This is S1, which is zero and so on.
So this bit of the formula is saying this last bit that the only square that does not remain unchanged or might not remain unchanged is Square Y.
Now you might think this is a little bit odd. Why does he not simply say here Z equals y y.
Express it this way? Well, it's because we're using the predicate logic without identity.
We haven't got the identity symbol to use. OK.
Right. I'm sorry, I have made the same mistake again, haven't I?
I do apologise that I should say again ex-prime equals X plus one.
So this is the formula for moving right? The difference is I've highlighted.
Whereas previously we have why prime equals one minus one. Now we've got way.
Crime equals y +1 because when we're moving right, the square to which we're moving is one greater than the previous square.
Okay. And oh, yes, and here notice that we've said correspondingly that Z is equal to y prime minus one.
This is saying why crime is the successor of Z. So it implies that Z is y prime minus one, which makes Z equal to Y again.
Right? So this part of the for in this part of the Formula Z has to be equal to Y, which is the square from which you've moved,
because it's saying that that square need not have the same symbol in y prime in cycle x prime sorry as it did in Cycle X for completeness.
Here is the formula for N where the head doesn't move at all and you might think here we don't need a y prime, after all.
Are we on the same square all the time? So why do we need to bring in a y prime?
Well, we need it because we haven't got the equality side, we haven't got identity.
So in order to express Z equals Y, at this point, we again need to use the same trick that we did last time.
We say Z is y prime minus one. So here we're making y prime equal to y plus one.
But we're simply doing it in order to be able to express Z being equal to Y at that point.
OK. That's quite tricky, but I hope you will find that with the prompting I'd given you of what's going on.
You will be able to go and look at Turing's text and make sense of it, particularly in Petzold company.
CHEERING, cheering. Make some mistakes. Here you can see how easy it is to make mistakes when you're doing this kind of thing.
Petzold usefully corrects those. OK.
So let's think about what we've now got. We've got going back in a little bit.
Slow to go back. OK, we've got these predicates which enable us to express the complete configuration at any point which square is being scanned.
What's on the tape? What's the state? We can do that. We've now got.
These formulae, which enable us to express the quintuplets that constitute the machine table, the rules by which the Turing machine operates.
Okay, so putting those together, we've now got the way, a way of expressing both the rules and the slates of any Turing machine.
OK. Every quintuple in the given machine can be represented by one of the formula we've just seen.
Put those all together that gives us something that Turing calls days of.
And so days of em is the description of the machine in terms of all the quintuplets that it contains.
In other words, it encompasses the machine table.
OK, now what we're going to do is use that to create another formula, which represents the statement that will at some point print a zero on its type.
So again, we're using this lemma. We know that it's not provable, that the Turing machine will or will not print to zero on its type.
What we're now going to do is express that in predicate logic.
There's a complication here, cheering needs to specify relevant properties of the number sequence.
I'm using this is a bit of an excuse us Petzold does to talk about pianos axioms.
These axioms specify the properties of the number. Series zero is the number.
We're talking about natural numbers here, beginning with zero. Every number has a successor that is also a number.
Zero is not the successor to any number two numbers that the successors to the
same number are equal and the property that enables mathematical induction,
which effectively means you've only got a single series starting from zero.
Okay, so pempel Pianos Act seems very familiar, Petzel.
This discusses them on Page 223, and I'd advise you to go and look at.
Turing doesn't need all of these axioms, but he does need some basic properties of integers.
He needs these because he's using integers in order to index the configurations of the machine.
He expresses the properties in this formula, which seems to be intended to capture pretty much the same as piano.
But actually, Turing gets it wrong. And in this case, I think Petzold gets it wrong as well.
Looking at this yesterday, I'm afraid I just came to the conclusion Turing is wrong.
His formula doesn't actually rule out a branching series. It may still be adequate for the purposes of his proof.
But I invite you to go and check my belief here that this formula does not actually successfully capture what the piano axioms do.
And anyway, let's leave that to one side. It's clear that one could substitute a formula that would have the desired effect.
OK, now we come to the formula, which is going to be undecided.
The one that says our machine. M. Fritz zero.
Well, that last monstrosity that we saw the piano axiom formula or intended piano axiom formula that's just abbreviated as Q so Q features here.
So what is this saying? Well, there is a, you know, that's a number zero.
So that's the number, but there is a configuration,
there is a number which is the number of a configuration such that within that configuration, every single square contains a blank.
Right? That says square y en in configuration, you can take a blank.
This is this is a universal quantified. It's saying every square in that configuration contains a blank.
Yes. Zero. And in that configuration, the scanned square is square zero.
And in that configuration, the initial state is sorry.
This current state is state one. So what that's doing that is describing the initial situation in which you have a completely blank team.
The machine is in its initial state and it's scanning square zero.
And then you add to that the description of machine and all the quintuplets.
And remember description of machine enemies, he's all in terms of the implications you can draw.
So imagine that you've got that to start with and then you've got all the power to apply those quintuplets to draw more and more implications,
which effectively correspond to future state of the machine feature complete configurations.
And what this is saying is if there is such a you, if there is such an initial state in which that is true,
then there is an s and there is a team such that in configuration s at Square T, a zero is printed because S1 is zero.
So that's saying there is some configuration and some square such that a zero is on the table.
So here we have been the of number sequence conditions there, the piano stuff, we've got a description of a blank tape there.
We thought a description of the quintuplets,
they're about given the machine and and and here this is expressing the implication that that lot will produce a zero.
If that formula is decided, well,
then it is possible to have a Turing machine that will tell you whether an arbitrary charity machine will print to zero or not.
And we know that's not possible. OK, so we nearly there there's a couple of lemons that Turing sets out to prove, which basically connect.
What we can see already is is going to be the case.
He's just proving that the prove ability of that formula does indeed correspond with the appearance of a zero on the tape.
So his first memories is if someone one that is the zero appears on the tape in some complete configuration of him, then un and is provable, right?
That's that formula that U.N. of M lImita.
If UNM is provable, then this one does indeed appear on the tape in some complete configuration of him.
This is somewhere where it would be good to go and look at the book, but I hope this will help you follow what's happening there.
It's it's relatively straightforward.
There are, you know, technical niceties there, but essentially what Turing is doing is formulating sequence of formulae.
CC0 CC one, CC two etc representing the sequence of complete configurations as M proceeds,
he uses an earlier abbreviation standing for this, which is part of the UN formula.
You may recognise that he uses FN to abbreviate the numeric successive relations,
and then he shows by induction that all formulae of that form are provable.
You get the base case on Pages two, seven, two to three and the induction step two seven three to five.
Essentially, the idea is that he's got this formula, which represents the sequence of configurations and CC zero,
therefore is just the initial configuration, and you can see that that is indeed going to follow pretty trivially from this.
The bits inside the square brackets, because that is that specifying the initial configuration.
So not surprisingly, that's pretty trivial. That's the base case.
I mean, because the formula contains all these quintuplets.
It's been fairly straightforward to get from one configuration to the next one because if the configuration can contains the appropriate,
if the complete configuration contains the appropriate trigger on the scan square, there is the right symbol and it's in the right state.
Then the quintuple is going to apply and DSM will contain the formula, which leads to the following complete configuration being adjusted accordingly.
So you can see how a proof by induction would go effectively simulating if you like,
or mimicking the application of the Turing machine to the take stage after stage.
So Lemma one follows because assuming that zero does indeed appear on the take in configuration and say, then CCN,
which includes all relevant are a con. They're the con. That say what symbol appears on the tape,
at which point that must include our S1 and for some square y.
All right. So suppose, suppose configuration end, you know, one million three hundred sixty five thousand four hundred twenty nine,
whatever it is, suppose at that point a zero does indeed get printed on the tape.
And then that configuration that that formula, which which specifies the configure the complete configuration,
will include an element like that specifying the appropriate square in which where a zero occurs.
So it will be a trivial implication from that formula that zero is printed.
The second Lemma, if undermines provable in this one, appears in some complete configuration,
that must be true simply by substitution of appropriate prop propositional functions.
So finally, we are in a position to show that the shadings problem cannot be solved.
OK, now some of the stuff we've been through here is, as you see, very, very technical.
Do not worry if you don't understand all of it,
it's worth going and looking at the paper and pencils description to make sure that you've got the gist of it.
But really, the most important thing is just to have the gist.
Turing has shown how the properties of Turing machines can be encoded in predicate formulae.
He's shown that a certain thing cannot be done with Turing machines,
namely providing a reliable test for whether a zero is printed on a tape ever by some arbitrary jury machine.
And he's provided a formula in predicate logic, which expresses that proposition that it is or is not printed.
And he's then concluded, therefore, that that formula is not decided.
So to sum up, the lemmer of Section eight proved that no machine can be constructed,
which will reliably determine whether any specified machine will ever print zero.
But since that behaviour, printing a zero or not can be captured by a predicate logic formula, you can.
Then it follows that no machine can be constructed, which will reliably determine whether or not that formula is provable.
Hence, the incidence problem to devise a mathematical procedure to determine whether or not any predicate logic formula is provable has no solution.
And that is where we finish with Turing's 1936 paper on next time to the 1950 paper, which is much easier going.
But I hope you've found the 1936 one of great interest.
It does repay a lot of study. Thank you.