Turing and von Neumann - Professor Raymond Flood

what I want to do today is to talk about John what Lyman and I'm cheering and both of them had an enormous range of interests not only in pure mathematics but also in practical applications they made major contributions during the Second World War cheering on cryptography and Vannoy minore weapons development the Turing machine formalized the idea of an algorithm and the Turing test is important in artificial intelligence while one Norman finder the subject of game theory and both of them are considered finders of computer science and what I'm going to do is to tell you first a little bit about what Norman up to the time that both he and cheering were in Princeton together then I'm going to talk about when Norman's World War work some of cheering's war work and then finish off with their contributions a brief introduction to their contributions to biology so what Norman was born in 1903 in Budapest Budapest at the turn of the century produced many fine mathematicians and physicists but for Norman's brilliance stood out he was a child prodigy learning several languages and showing early exceptional ability in an enthusiasm for mathematics by age six he could divide to eight digit numbers in his head by age it he was studying the calculus by age 12 he had read and understood Burrell's theory of functions they also had an amazing memory I was supposed to be able to memorize at a glance the names addresses and telephone numbers in a column in a telephone directory and he retained this ability of absolute recall all his life now as father was now kenan and becoming a mathematician didn't think the money was good enough and they compromised on a career in chemistry he studied chemistry first of all in berlin from 1921 to 1923 and then mathematics in budapest although he never attended any lectures there nevertheless in 1926 he received a diploma in chemical engineering from Zurich and a doctorate in mathematics from Budapest he was famous for his speed of thinking on many stories of a disability and one of my favorites is solution his solution of the famous fly puzzle so the setup is as follows two cyclists start 20 miles apart and cycle towards each other at a constant speed of 10 miles per hour at the same time fly starts the leftmost cyclist flies towards the other cyclist and speed of 15 miles an hour then when it arrives at the other cyclist turns Rhines it's quite large flies you've noticed turns rhine and flies towards the leftmost one and then when it arrives at the leftmost one being a fly it turns around and goes back again and the question is how far does the fly travel and of course the slow way to find the answer is to calculate the distance traveled on the first leg at the top then the second leg then the third one and so on and then some the resulting infinite series of distances but the quick way is to notice that the cyclists meet exactly one hour after they start they're both traveling at 12:00 at 10 miles per hour under 20 miles to go so they meet after one R the fly is traveling at 15 miles an hour and it's flying all the time so the fly travels 15 miles when von Neumann was asked the puzzle he replied instantly with the right answer of 15 miles and the disappointed questioner said something like oh you've heard it before and know the trick and what Norman replied what trick all I did was to solve the infinite series so for Norma's doctoral thesis was entitled the axiomatic deduction of general set theory and was very influential it would introduce the idea of ordinal numbers that we that we use today the definition of ordinal numbers and he kept an interest in set theory and logic for the rest of his life towards the end of the 1920s he had academic positions at Berlin and Hamburg now to us me an interest during this time were quantum mechanics and operator theory and his basic insight there was at the geometry of the vectors in certain infinite dimensional spaces called elbert spaces they had the same formal properties as the structure of the states of a quantum mechanical system much of anointment work with axiomatic starting off for the set of axioms that modeled a physical situation and then deriving consequences and this was the analogy between the states of a quantum mechanical system and this abstract operators on these abstract Hilbert spaces we rebelled critics find that Nobel physics prize winner Eugene Vigna said that for Norman's contributions to quantum mechanics alone would have secured him a distinguished position in present-day theoretical physics in 1928 he published a paper establishing the subject of game theory and Foreman's work in games as characteristic of a lifelong approach of using mathematics in practical situations and the consequences of his work go far beyond the application to games of chance I'd have been important that he can all make psychology sociology politics and military strategy I want to spend a little time tell you what he actually did in game theory all right so it into just some terms for the first couple of slides so zero-sum game between two players as one in which the game to the winning player exactly equals the loss to the loser so the total payoff to both players sums to zero essentially von Neumann proved that zero-sum games are not worth playing that is the summary of his result in the sense that each player can always obtain an optimal strategy and more can reveal it to the opponent let me explain well he developed game theory with the following set up conflicting situation finite number of players each player can take one of a finite number of actions different players can have different lists of actions at each play of the game players don't know what action would be taken by the other players the result of the game determines a payment to each player which can be positive negative or zero enough of mentioned as the sum of the payments to all players a zero the game is called a zero-sum game and of course if there are two players then it's called a two-person zero-sum game well a crucial concept in game theory is this concept called the payoff matrix and here's one that I've just made up there are two players there's me under zero you can take one of three actions you get the Greek ones alpha beta gamma Y also have three actions one two three and the entrance at the entries and the payoff matrix give the payment I receive corresponding to our choices of action so the payoff matrix is written from my point of view so if I choose action two and you choose action gamma I'm going to win it Pines alright on the other hand if I take one of the ones it's negative I take action one and you choose action beta then the payoff to me is minus five in other words I lose five points you gain five fights so how should we play the scheme with this payoff matrix so the payoff matrix describes the game that we play with each of three courses of action and depending upon what each of us choose then we know what the outcome is going to be well we're both going to adopt a risk-averse strategy and what I'm going to do is to look and see what happens what's the worst that can happen when I take each of the three approaches that I can have so if I take action one the worst that can happen is that I have to give you five points if I take action too that's it I take action to the worst that can happen is that I gained six points there are other alternatives is that idea nine and gaining it and thirdly if I take action three the worst that can happen is that I have to give you three Pines so what's the best of those worst outcomes the best of those are worst outcomes is that I should take action too and that should be my strategy so that's the maximum of the minimum entries in each of the rows but let's do the same analysis from your point of view now remember from your point of view so that the earthly action I should take action to with a payoff a guaranteed payoff of at least six times irrespective of what you do because I looked at all my actions I find what the minimum payoff was for each action and then I took the best of them now from your point of view remember the payoff matrix is written from my point of view so and really you if you were to write it from your point of view all the numbers would be inverted and sign but you do exactly the same thing you look at your actions and this time you maximize the number that appears in each column all right so for you taking action alpha the worst that can happen is that you're going to have to give me six pints that's the worst the biggest I come in the first column if you take action beta then there we are it's going to be nine pounds as the worst that can happen and similarly with your ahead of me on action gamma is going to be eight Pines so what's the thing that's going to minimize the worst outcome from my point of view it's that if you take area if you also if you take action alpha and you see that in this situation for the matrix at the payoff matrix as I've constructed it and the payoff for both of us is going to be me winning six pints at winning at least that and you're losing at most six points right and this particular approach to it let me see here we are here using the risk-averse approach I want to maximize the row minima and you want to minimize the column Maxima and for this game these two numbers coincides with action two for me an action alpha figure giving a payoff for six to me and since it's a zero I've got some game you're losing six no there's another word that used to describe this and which is that it's an equilibrium point an equilibrium point to the game and the reason we call it an equilibrium point is that neither of us has any incentive to move away from it there's no incentive to move away from this equilibrium point and furthermore both players can announce their decided course of action in advance with God giving advantage to their opponent and there's another way of looking at that's a graphical way of looking at it which I find very useful we can think of although there are only three courses of action for each of us we can think of perhaps my courses of action being plotted along an axis say the x axis your courses of action being plotted along another axis say the y axis and then along a vertical axis what we have is the payoff so there'd be a payoff corresponding to each pair of numbers an action for you and an action for me and that's going to give a surface and on this surface what I want to do is to get the highest point and what you want to do is to get the lowest point and if we have it here this s it's a saddle point because going in this direct it's the lowest point which is what you wanted but going in the other direction it's the highest point which is what I wanted so these equilibria point equilibrium point for games such as this are often called saddle points no what did wouldn't know I mean do well he looked at a different type of zero-sum game where there were no saddle points so that the payoff surface didn't have a saddle point and I'll give you an example of such a game classic game of rock-paper-scissors where I've written down the payoff matrix here again from my point of view and this is a game where we each of three actions and it's one of these things that's not transitive and rock beats scissors paper beats rock scissors beat paper and I I've written down what the payoff matrix is there and you can see that it doesn't have a saddle point from two points of view if you look at the minimum of the rows the minimum of the first row is minus one the minimum of the second row is minus one the minimum of the third row is minus one so the maximum of those minimums is minus one if you look at the maximum of the columns that's going to be one for that column one for that column one for this column so the minimum of the columns is one this time they don't coincide so there's no saddle point but even more potently I think you know there's no saddle point because if you were to peek if you were to look and see what I was going to do which one of the three I was going to put out rock paper or scissors and you knew it was you could always beat me so knowing what my strategy was we give you an advantage and that doesn't happen if you have a saddle point know what for norman said was that what you did was you just didn't play the one strategy all the time as we would have done in the first situation what you did was to adopt a mixed strategy which was to play your strategies with a certain probability and he gave a way of being able to calculate what that was so one mixed strategy for this game is for each of us to play a with probability 1/3 each of the three possible actions that we could take and when you did that then it would be the case so this is this minimax theorem that we have here he proved that for every two-person zero-sum game there exists a mixed strategy for each player so the expected payoff for both is the same magnitude when the players use those strategies the same magnitude one of them will be positive one of the movie negative that's what I'm saying at the bottom there as the game is zero-sum so taking a probabilistic approach to the playing of the game always give you an optimal strategy and it's what Norman said about this result later on as far as I can see there could be no theory of games without that theorem and I thought there was nothing worth publishing until the minimax theorem was proved now as I've said but Norman to work on is characteristic of a lifelong approach of using mathematics in practical situations and he published this minimax theorem in 1928 and subsequently collaborated with The Economist Oscar Morgenstern and produced this book in 1944 theory of games and economic behavior and I show the title page of it here and show the minimax theorem down here at the bottom and I think apart from the details of the notation which I haven't explained here you see what it's doing it's showing that the max of a min is equal to the men of a max which is just what we were doing when we were looking along our rows and our columns and game theories continued to be important in economics and so the minimax theorem provided a solution to two-person zero-sum games but not for more general games or for more players and in 1994 the Nobel Prize in Economics was awarded essentially for a result in pure mathematics it was awarded to John Nash John Harsanyi and Reinhard selten for their work in game theory and the Nobel citation which have got down here on the right for John nice says that he introduced the distinction between cooperative games in which binding agreements can be made unknown cooperative games where binding agreements are not feasible and then he developed the analogous thing to an equilibrium position the way I was telling you about a saddle point there that's called Nash equilibrium and I've just given you the rough statement of Nash's theorem and any end person so he's increased the number of people that can play a non cooperative qiyam so you can't form binding alliances zero-sum or known zero-sum that's very much the core of it for which each player has a finite number of pure strategies it has at least one equilibrium set of strategies and that was the subject of the American film here a beautiful mind ok and the situation for cooperative games such as the prisoner's dilemma still remains as a challenge to be to be understood well in the late 1920s for Norman's lectured at Berlin and Hamburg he then taught for three years of Princeton University until he's appointed as one of the finding professors of the newly created Princeton Institute for Advanced Study a position that he held for the rest of his life and he was appointed at the age of thirty he was the youngest professor at the Institute which is a very distinguished history as you can see there and it was each of 38 school of mathematics and he was frequently mistaken for a graduate student so let me turn then to one noise it took from von neumann to cheering by 1936 when Norman was well established in the Institute for Advanced Study when Alan cheering visited Princeton University cheering was age 24 he arrived in September 1936 he was to spend most of the years 37 to 38 their leaving after his awards his doctorate in June 1938 and he'd previously met one know him in 1935 so he was renewing contact with them there but let me go back a bit say a little bit about cheering's life up to this point it was for in Paddington in June 1912 went too sure bro and boarding school at the age of 13 he was too independently minded to be a conventionally successful student instead he stood at modern ideas such as Einstein's special theory of relativity on his own and his grandfather gave him probably for Christmas 1927 a book on the theory of special relativity here's copy that I've had on the left from for many years but what cheering did was he wrote a commentary on this book written by Einstein explaining the theory of relativity and saying press a made by Alan Turing at the age of 15 and a half on the theory of relativity by Albert Einstein and apparently the guide to reading was for the use of this mother what every mother wants is a present right but if you go through it and it's available yep which will be on the on the handout you can collect afterwards it is very available at the digital cheering archive and it's really fun to read through it here I've taken two extracts the one on the left is the longest one and it is about chapter 11 and what the fifteen-year-old cheering says I like the way he said he was 15 and a half it's very much a childish sort of thing to do although I'm starting to do at nigh and my 60 in stein just gives here the equations of the lorentz transformation unless they'll be taken for granted unless you read his complex proof of Appendix 1 I have got a proof though which will give you the result of chapter 17 directly and if you like the Lorentz transformation chapter 17 was on the moon scoffs key four-dimensional space-time he then starts as proof which runs for just over three pages and he finishes with the justification have gone roll it differently from the book because in this way it should seem less Magic eight and the other except well the proof that he gives actually is some little one that I gave on my first lecture this academic year on Einstein the other excerpt is about the chapter which discusses the equivalence of massive energy Turing's advice to the reader and this chapter is this chapter does not need very careful reading like the others I should just read it through and think about what interests you and on the rest of the page you can see down towards the bottom he calculates the energy that would be released from the annihilation of one gram of matter and says it would be enough to lift 1 million tons to 9 kilometers well it's still an undergraduate he was in his third year cheering provided a rigorous mathematical proof of the central limit theorem which is a result describing the behavior of averages unfortunately then find hurt it have been proved 12 years earlier but he was nevertheless encouraged that submitted for his fellowship a nomination election I think and he was successful and at the age of 22 he was elected a fellow of King's College Cambridge in 1935 now while waiting for the results of the fellowship election cheering attend to the lecture course on the foundations of mathematics and there was to be one of the most important courses he went to in his life and this lecture course included the following questions turned out the answers which turned out to be the deepest results some of the deepest results in 20th century pure mathematics in 1928 David Hilbert during the International Congress of mathematicians posed three questions is mathematics complete that is in every statement in the language of number theory bees approved or desperate is it consistent that is is mathematics free from contradiction is it decidable that is does there exist an algorithm for deciding whether or not a specific mathematical assertion does or does not have a proof curt girdle had shown in 1931 that the answer to the first question is no the so-called first incompleteness theorem there are statements which can be neither proved nor disproved they also proved that if number theory is consistent then a truth of it does not exist using the methods of the first-order predicate calculus the second incompleteness theorem the last question is called the decision problem and was still an open problem when cheering attended his lecture course and cheering was intrigued by so let me just actually write from the slide Hilbert's decision problem given a mathematical proposition can one find an algorithm to decide whether the proposition is true or false an algorithm a mechanical way a procedure prescription that was the first problem that cheering had to face what do you mean by an algorithm and what he decided to do was to create a machine in the mind and change cheering's thesis was that I called the church cheering thesis church comes into the story and a slide or two and his thesis was that his machine will accomplish anything that could be done mechanically or algorithmically so when he's defining an algorithm as corresponding to the output of the Turing machine during machines and algorithms are the same thing and anything that anybody since has come up with as a prescription or a definition of an algorithm has turned out to be equivalent to the cheering machine approach so let me show you what a Turing machine is like cheering machine very simple it's an infinite tip which acts like the memory in a typical computer not a typical computer is very much like a Turing machine it seems quite odd to try to illustrate a Turing machine and using the ideas of a typical computer this is why it's known as one of the finders of computer science but cheering machine and then tip it acts like the memory each square is usually blank initially and can be written with symbols I'm going to illustrate for this three simple Turing machine uses assemble 0 1 and blank the machine is a head which can be positioned over one square of the tip that's my drawing of the head positioned over the square of the tape containing a symbol 1 there here it's positioned over the leftmost non blank head no with this head positioned over a square of the tip the things that it can do is that it can read the symbol it can leave it unchanged or it can edit the symbol by writing another symbol and then it can move the tip left or right by one square so that the machine is then looking at the neighboring square alright the other thing I have to tell you about the machine it's the only other thing the machine can be in different steps and what is the state of the machine well a state of the machine tells you tells the Machine what to do depending upon what symbol it's reading so in a particular state when the machine reads a particular symbol it will move the tip left or right it will write something down and you know that and just just to sort of illustrate it here I've got a cheering machine it's going to do a bit inversion so it's a Turing machine that's going to start off with the tip 1 0 1 and it's going to end up with the all the ones turned into 0 and all the zeros turned into ones which is not the case there because I've made an error that's this that is the deliberate mistake which I which should have left you to catch right so pretend there's a zero don't know so this is just use just the idea of stents and a chewing machine to do this but inversion properly just contains two sets the stop spit which does what it says if your if the machine is in the stop stead then it stops irrespective of what character it is reading and this other stick which I'm calling state zero just another step unlisted if it sees so let me start with the the second roll around here if it's in this state if it sees the symbol zero it writes one and it moves the tip to the right in other words the head moves to the left so that's the head moving to the left down here if it's T's one then it writes zero and moves the tip to the right in other words the head moves to the left of it so the head is moving what should be happening is the head is moving to the left on each time that it reads a symbol it's converting it until this operation happened down here then when it reads the blank over here it goes into the stop state it moves the tip to the left goes into the stops death and halts ant cheering's assertion was that you can develop something as an algorithm to do it you can get a Turing machine to do it okay unless as I say you need to remember that any other approach to defining algorithm such turned out to be equivalent but here's where it starts to go he then went a step further and he envisaged a universal Turing machine that's a Turing machine that could emulate all other cheering machines now you've just been exposed to them you need a little bit of time to get the familiar with them but how it is done is that if you have a cheering machine all right that shirring machine can be described by a string of 0 & 1 symbol so in other words the different states that the machine can be and can be encoded in a bit either way as a set of zeros or ones if you want to find out what that machine will do on a particular input you give me its description in terms of zeros and ones you give me the input upon which you wish it to act I feed it into the universal churning machine and it simulates it emulates the cheering machine that you had and so this one machine that I have can emulate any other cheering machine and this was just absolutely cool I mean it's it's analogous a modern computer works that way because you can get a computer to do different things by giving it different programs so that's exactly the notion that we have here the program is fair stored-program idea for modern computing well and this 1936 paper on computable numbers cheering answered the decision question in the negative he showed that there are mathematical propositions that are undecidable no algorithm can decide whether they're true or false in other words he showed that there was no Turing machine to do very many particular tasks let me give you one of them which Turing actually uses in the paper it's now called the halting problem cheering showed that there was no algorithm that could decide the halting program now the halting program will be very worthwhile to have it would be an algorithm that would look at any computer program and the input that you were going to give it and we tell you whether or not that program with that input would keep on going forever or would halt an equivalent formulation of it would be there are lots of programs written in languages people want to write a program to do the same task but perhaps in a more efficient language it would be very good if you had an algorithm that you could bring along the two programs and the inputs that they were to act upon and ask well they would both have the same result there's no such algorithm so there are important practical problems the cheering showed and have got no algorithmic solution to them aren't the idea of a Turing machine I think you can see from it became the foundation of the theory of computation this idea of being able to describe a program in terms of the input input to to a computer not cheering is a bit unfortunate again that the resolution of a decision problem had been obtained simultaneously by two people cheering and the American logician Alonzo Church who had a different formulation of what an algorithm would be it was subsequently shown that the two were the same church was BS to Princeton and later in 1936 cheering went to Princeton to study first doctorate with Church as a supervisor and as thesis was logic and called systems of logic based on ordinals and at the conference in Princeton and 2012 to Marcus and Thierry of cheering's birth who said the cheering's thesis was one of the two most important ever done at Princeton the other was by John Nash and we've already met well this is an answer to a question that was asked at the end of the lecture last week and cheering Reuters modern arrival of Princeton at the mathematics department here comes fully up to expectations there's a great number of the most distinguished mathematicians here and he writes for norm instead of the list on the grid bridge mathematician geh Artie was visiting for the term somebody asked last week about the interaction between Hardy and cheering and cheering route to his mother at first he was very standoffish or possibly shy I met him at Morris prices rooms the day I arrived and he didn't say a word to me but he's getting much more friendly now well in 38 1938 cheering was initially unsure as to whether or not his fellowship would be renewed and in fact his father asked him to explore the possibility of getting a job what was the possibility of the war coming but there weren't many available and there was fierce competition for those that were for all the mathematicians who were fleeing pre-war Europe for diamond offered him a job as during a job as his research assistant insuring her that his and fellowship would come through and he preferred to return to Cambridge and the subsumed careers of von Neumann and joing were to be heavily influenced by their involvement on the war that was soon to begin all right Paul Hamas was a recent was a research assistant to charity for Norman at Princeton during the war and he wrote the year 1940 was just about the halfway point of all Norman Norman scientific life and his publications show a discontinuous break them Tulane he was a top-flight mathematician who understood physics after that he was an applied mathematician who remembered his pure work he became interested in partial differential equations the principal classical tool of the application of mathematics to the physical world and he continued his papers from this point are mainly on statistics shockwaves flow problems hydrodynamics aerodynamics ballistics problems of detonation meteorology and last but not least to known classical aspects of the applicability of mathematics to the real world games on computers for Norman's contributions to war were manifold most often mentioned is this proposal of the implosion method for bringing nuclear fuel to explosion and then after the war is a spice all of the development of the hydrogen bomb and after the war von Norman they had a team of Princeton and the development of a computer very much based on the ideas behind the universal cheering machine numbers in the machine were represented in binary form so any device holding a digit needed to have only two states and here is for Lyman in front of the completed machine in 1952 at 3,600 vacuum tubes a memory of five kilobytes it was the first stored program computer that's the idea of the universal Turing machine you've got the one computer that you can get in different programs to unlike previous computers that were programmed by altering their circuitry eluard had its drawbacks the Von Neumanns design was very influential now cheering's wartime contributions are probably better known and recently been the subject of the film the imitation game cheering joined the British government code and cypher school which was BS the pledge sleep Ark in September 1939 and there he joined the attack on the Enigma coding machine and I want to try and give you an idea of one of the things that he did so briefly to describe the Enigma there is a picture of it there and what happens is that when you press up here oh yes you press a key an electrical current goes through a plug board then through three rotors then it's reflected by a reflector and comes back and lights up one of these lamps so that you have an encoding of the letter that you have typed in and here is an illustration of it here the three rotors 1 2 3 and the wiring of them is no one was known to the Crypt analyst because of espionage by the French and the Polish and what you see here I'm typing a and it goes Ryan reflected and compiled its G now what happens is that after you type a and the first rotor rotates so if I were to type a and again there would be different set of contacts now and it wouldn't be G that would come I'd put some different letter C then the first rotor would rotate again and after the first rotor has rotated 26 times the second rotor rotates once and after this one has been made to go around after the appropriate number keypresses the third one goes right so it's what's called a polyalphabetic cipher but that isn't all complications because there's this thing called the plugboard here which is where we have a swapping of pairs of letters going into the machine and coming out of the machine and if you look at the number of steps for this polyalphabetic machine by that I mean that in any given stage of the Machine it will encode the letters of the alphabet in a particular way but once you press a key to do it for one of them the machine moves into another state where there's a different substitution alphabet right and if you look at the number of states there are 17,576 ways and for the different rotors to be configured that's 26 times 26 times 26 now that's not a big number because you could if you could step through a rotor position one a second and there are 3600 seconds and an hour so that would only take about five hours to to do all of to check all of the rotor settings so it's not big and the oops sorry the Rueter order they're six ways well I'm actually hiding lots of the details because you could have more than three rotors you could choose 302 five you can put them in different orders where the big number comes from is the plugboard this number here just gives you the number of ways of selecting seven pairs of different ways of selecting of connecting seven pairs of letters right so the total number therefore is that the product of these here which is big and you want to find out more about the two excellent books here one by Simon Singh the codebook which is where I'm going to be taking the diagram I'm using in a moment from and then this excellent biography by Andrew Hodges of cheering alright oh yes yes well I will leave this up too long in case you start to get terribly interested but well sign yes it was Simon sings book it contained the crossword set in the Daily Telegraph by Bletchley Park to recruit code breakers they challenged readers to complete it in less than 12 minutes and those he did so were invited to a further crossword test and it led to six new recruits so you might have a new career in front of you and I what I've done is to give a web reference that will be in the notes which you can download at printed items set your stopwatch to see if you can do it within the 12 minutes all right now what Turing and his colleagues did was to analyze the logical structure of enigma in particular youth they used the feature that if the enigma and any stick changed a into e then it would also change e into a because of the the reflector I'm just using a and E as examples it was a swapping a range of insulative letter one letter went to another letter they would also go the other way right I thought that's core now it was a practical advantage to that from the operators point of view because it meant that an if you were encoding something you would type in the plaintext and overcome the ciphertext if you wanted to decode it then you would type in the safe you accept the rotors up appropriately said type in the cipher text and overcome the plaintext so at each stage of the Enigma it performs a substitution by the Polish script analyst had and Bletchley Park had essentially cracked enigma in the early months of the war but that was due to the way it was being used at being used in a particular way to transmit the keys for a message and essentially what had happened was that they the key was not just sent once it was repeated it was sent twice and not provided a weakness but cheering was tasked with not cracking assistant but cracking the machine and he used this notion that the Machine performed swapping in order to do it so let me just try to show you hard by various means which you can read about in the books it was possible to get crimps and the crimp is knowing the plaintext meaning of a piece of ciphertext so for illustration purposes here I've written down there's this cipher text and by some means it is believed that that corresponds to the plaintext for these letters up here wete 4 so somehow we have got that now the thing about this crib is that it contains a loop all right because when this transposition is made from W to e the machine is in some state s but of course as I've told you once a substitution is made the Rooter clicks on once so the next substitution will correspond to state s plus 1 then the next to s plus 2 the next to s plus 3 that's saying that the rotor is clicking along as it goes now where is the loop well we've got W goes to a a goes to T t goes to W which is back where we started so instead as W is going to a then the lip goes W a T W ensuring idea cheering and the colleagues idea at Andrew Hodges goes into and the analysis of you know who did what and when was in this example here we've got a crib a look in a crib the livers of length 3 we take three cheering machines and we connect them together and it was an electrical circuit to mimic the loop so here we are okay this is the first cheering machine at the top second cheering machine down here third one now if you look at our loop it corresponds to some particular state s so we set the first machine at state s we don't know what it is we select some state we select the next machine because that's the next element of the loop loop one Rooter click on so setting s plus one and the third element of the the crib of the loop at the crib is at s plus three so we set the next one here a setting s plus 3 now the essence of it is we're going to parallel the loop in the crib by an electric circuit we connect the output of each enigma to the output of the next so e coming out of the first is connected to e going into the second I T coming out of the second is connected to T going into the third and then W is connected up here to the W here so it's electrically wiring up of the same thing that we have in the loop and you say to yourself what does that achieve but you need to think back to the numbers that I put up on that slide the big number was the plug board the plug board gives you that massive number the number of rudra positions was not grid and by connecting the machines in this way cheering and the colleagues essentially canceled out the effect of the plug board so let's say I was able to ignore able to ignore millions of their settings because although we don't know what's happening in here because of the plug board a is connected up to l1 when it comes out here the e goes back to l1 so the effect of the plug board is essentially neutralized so by connecting the machines open this way you neutralized the effect of the plugboard so it's canceled between the first two and a similar sort of way we have here now we have got the L 2 coming out it's connected across to the L 2 here so it goes from L 2 across the T but then it goes from T back to L 2 uncertainly the second and third sorry the first and second Council the second and third and then the third and the first I'm not really giving you enough time or detail to get with it but if you just go with the idea of a look then you take the output you take the same number of machines that you have letters in the loop and you connect them up this way then effectively you cancel out the effect of the plugboard with only one thing you don't know where the first one goes in but there are only 26 possibilities for that and 26 is a much smaller number than that this we know this one here all right and so what you can do is you can either try each of the 26 possibilities or you could have 26 circuits each with a light bulb then you set your router stepping through them all right so what I mean by that there is that you you keep them going along in unison in other words that this one is always one beyond that and this one is always three beyond that but you step them through and then five hours later within five hours some light bulb will have come on so the core being and you can see how it relates to a lot of the stuff he was interested in both with logic and with mechanical things and machinery is to implement in electrical circuitry what was happening in a logical analysis okay so I've finished by briefly mentioning two other interests that annoy Minh and cheering had in common and that is in biology now during a lifelong interest in the development of pattern and form in living organisms and he looked at how biological systems that are symmetrical at the start can lose that symmetry and wondered how this could be caused by the dynamics of the way that chemicals to furies and react quite an amazing idea because normally when things diffuse and react they tend to go towards an equilibrium but he was using it to try to show that they became known equilibrium in other words you know cause pattern caused form so using a computer he carried out pioneering work in modeling these chemical reactions and published his results on this paper here the chemical basis of morphogenesis and underneath is a double Dam patterning that he got again from using one of his Verity computers of course Wood had to be one of his early computers and here we've got another major contribution he made was his paper on Computing Machinery and intelligence in the journal mind and cheering started I propose to consider the question can machines think and he refined this question by introducing what he called the imitation game that's the heading of the first section and in this game there's a machine a woman an interrogator and the object of the game called the Turing test it's for the interrogator to determine which of the others is the machine and which is the woman they can communicate with the interrogator but only in a matter of course that gives no clue to their identities point I want to make here is that earlier we've been concentrating or cheering concentrated on what machines cannot do but now focus with us what they can't do and in particular whether the behavior of the brain can be replicated by a computer and the Turing test remains important in philosophy and artificial intelligence well anyway after the war was over cheering went back to the National went to the National Physical Laboratory in London to work on the design of an electronic computer the automatic computing engine is his final University position was deputy director of the Manchester computing laboratory and he continued to be consulted by GCHQ to Bletchley Park but then he lost his security clearance when he was brought to trial for homosexual activities in 1952 and came under intense scrutiny and he died of cyanide poisoning aged 41 a half-eaten Apple beside his bed and the inquest brought in a verdict of suicide and when Owen also died young not quite as young and his kiss at the age of 53 and he left unfinished his research program on a new information and computation theory for biological systems especially the brain and this was inspired by cheering's Universal machine and he was developing his theory of self reproduction of automata and several years five years before the work of Watson and Crick on the structure of DNA and its role in biological self reproduction so to conclude for doormen and cheering made massive contributions to mathematics computer science and the times in which they lived their work was crucial to the shift in the middle of the last century from the scientific paradigm based around the principle of the conservation of energy to the new fields of information on communication and computation which continued to have a fundamental impact on our world today so thank you very much for coming along and I hope you enjoy next year's program of lectures you

Channel: Gresham College

Views: 77,512

Rating: 4.8726115 out of 5

Keywords: John von Neumann, alan turing, Neumann, Turing, WW2, Turing machine, algorithm, weapons development, cryptography, artificial intelligence, ai, game theory, computer science, Theory of Functions, Modern Mathematics, history of mathematics, computational mathematics, Mathematics, gresham, gresham talk, gresham lecture, gresham political history, gresham mathematics, professor of geometry, geometry professor, mathematics lecture, mathematics talk, Oxford Raymond Flood, raymond flood

Id: fJltiCjPeMA

Length: 52min 11sec (3131 seconds)

Published: Tue Apr 26 2016