What Computers Can't Do - with Kevin Buzzard

[Applause] killer robots so killer robots actually a real and they're accompanies making killer robots and so you need to know about killer robots the characteristics for killer robots there's two main characteristics of course firstly killer robots could kill secondly killer / - robots but there's another key characteristic so killer robots are controlled by humans because there's a line so this I mean at this point so this is a YouTube screenshots of Boston Dynamics - the company that makes killer I won't play the video but Sir this is a well you can watch I mean you can find it it's on YouTube is uploaded in October 2003 it's his fabulous video of a killer robot and basically it just spends eight minutes running round the car park of his company in America that designed his killer robot and occasionally it's all runs past a kind of a sort of fat balding bloke who's holding a controller and he's running around you know he's running this killer robot round and but you see at the end of the day that's to put the point is it's not just the killer robot it's the it's the bloke with the controller he's controlling the killer robot so the robot running around the car park it's been controlled by a human and the question is could a computer control that killer robot instead you see could a computer you know computers disruptive technology computers like to relieve humors of their jobs so kind of computer control the killer robot okay and in fact we could go a step further could we write an app the people could download on their phone and the oh now I know how long I have can we download an app on our phone which which when you type in someone's name into the apps that then some killer robots are unleashed and goes and kills that person so could there be a killer robot can computers can computers do that so that's kind of an interesting question so what would a company need in order to make that killer robot app so firstly they need a good database right because the other is you type someone's name in and it's going to find them so you need names addresses and accurate information about the daily routines of billions of people so secondly we need two people that can write the app so we need employees they're very good at writing your beauty programs thirdly we need very good facial recognition software to make sure the killer robot kills the right person fourthly we're going to need experience in kind of control that this is somehow one of the hardest parts we need to control the killer robots like out of this out of his car park and towards the correct person and then fifthly of course we need army of killer robots so we have all of those things then we can write killer robot so what's the company that has all of those things how about Google so let's have a look right does Google have names addresses locations billing people absolutely right even if you don't have an Android phone even if you don't have a smart phone at all somebody you know your boss your work colleague your wife your you know your grand your granddaughter somebody has type your name and your phone number and your address into their into their Android contacts and they've sync that contact list with Google and Google knows what your name is what your address is and where you live and and your phone number - so just Google have employees it can write good computer rooms of course it does just Google have facial recognition software of course it does I had an Android tablet once and I just looked at it and it would unlock it was a very kind of cool thing does it have computer programs that can drive machines around of course it does because it's currently spending a lot of money on self-driving cars so the only question left is does Google have an army of killer robots and the answer is well you see Google has a motto which is don't be evil which it quietly dropped in 2015 and possibly unrelated to that in December 2013 Google bought Boston Dynamics and seven other robot companies and now suddenly Google owned all these scary killer robots exactly so how many killer robots have Google actually got probably enough to make it feasible to write that so actually I think in theory I attempted to construct a proof that in theory somebody at Google could write an app which really were to have the property that you download it you type someone's name in and it unleashes several I mean you'd probably have to do some experiments so I got how many was enough but enough killer robots to finish this person off so that's that's something computers can do I think at this point in time all the ingredients are there okay so this talking about what computers can't do but this I think puts it into some kind of perspective so so here's another question what about if Google godís word Google hat was sentient and realized that it could you know maybe we need a human Terrell yet maybe the computer could write it up maybe somebody 2001 maybe the computer could write the app and maybe the computer could just decide to take over the world because it's got access to the facial recognition software on the database maybe the computer could just kind of go rogue and you know and take over the world anyway so maybe computers would find that appealing but I'm not so sure because we're computer to make that leap and decide that it's going to kill everyone in the world the computers have to be able to synced and I don't know if computers can think so we've seen some in computers can do if somebody wrote the program they'd kill everyone but we've also seen maybe they can't think okay and in my personal opinion I don't think computers can think so here's a picture of two things the thing on the left is Garry Kasparov's he was the world chess champion in 1997 which is when this photo was taken and the thing on the right is what at the time was a very fancy looking monitor and that monitor was attached to a computer and the computer was called deep blue and it was made by IBM and it was the best chess-playing computer at that time so world chess champion versus computer chess champion this was a six-game match played in 1997 and it was big news Kasparov lost in 1997 marked the era when computers became better at chess than humans and since then all this happened is computers got much much much better and now there aren't any more competitions between humans and computers because no human with any cents would ever dream of trying to play computer at chess anymore so who is thinking in this picture well Garry Kasparov certainly looked at if he's thinking that's a I think that's a Sicilian defense where a few moves in and he's probably trying to work out what the best move to players and he's using his intuition he's using insight he's using experience he's also using psychology even though he's playing a computer he's somehow played this computer before he knows what kind of positions that computer plays well on what kind of positions that computer plays badly he's adapting his play to try and beat that computer what's the thing on the right doing is to thing on the right thinking I'm also sure that thing is thinking is deep-blue thinking I don't know what does the computer do and computers the devices very very good at following instructions very very quickly right and that's different to thinking in my opinion right so the basic logical instructions for the computer follows it contains something called a computer program and I'm going to have to tell you something about computers and computer programs in this talk but I'm going to try and keep it simple while it's also attempting to get to the difficult point so let me tell you two things about a computer first thing simply to have memory it computer needs to store information because sometimes it's just calculations then remember the answer and look back at the answer later so computer needs memory right where the computer stores informations the computer program is typically stored in the memory as well and the computer also needs a processor the processor is basically the bit of the computer that reads all the instructions in the program and does them one by one very very quickly and sometimes the instructions say go and do this instruction instead jump over here yeah the processor works very very fast following these instructions okay so nowadays process can process what a four gigahertz processor I probably have one of those in your phone now that's that's doing four billion yeah that's following four billion instructions per second and so you can see even in 1997 because IBM had love you know interest in computers and doing a lot of research into making abuse very fast that computer deep blue it was analyzing 200 million computers positions every second right so what was it doing it was just trying all the moves even the moves that were ridiculous even try ever try move to the wrong place at that piece I move last time let's just put it back that is that's the kind of move at the truck if we try every single move we try all the responses all the responses and keep going very very fast and then it would make some kind of guess as to which positions looked ok and then maybe follow up with them but Kasparov wasn't playing like that at all Castle there are many moves in a given chess position the Kasparov would not even consider because he could see yet the intuition he knew they were going backwards but intuition ultimately gets defeated by brute force search analyzing millions and millions of chess positions per second eventually we've now proved that computers can do this better than humans so I don't think that's thinking so I think we're kind of safe from computers going rogue and trying to kill us all but you see the reason I don't think it's thinking is because I do a lot of unloading the dishwasher and unloading the dishwasher is a very mechanical procedure it's like there's a plate and over the plates go and there's the bowls and over the bowls go as the cutlery and I never the cutlery goes and I just sit just unthinkingly I sit and put everything away and actually I even unload the dishwasher in exactly the same order every time because I have I'm trying to be like a computer in some sense and while I'm doing that I'm thinking right and I'm certainly not thinking about what I'm doing what I'm doing is somehow subconsciously happening in the background well I'm doing yeah I'm tend to be freaking about mathematics or whether I'm hungry or what I'm going to do after I finished unloading the dishwasher you see and that's that's that's thinking and where is the computer when we have robots to unload dishwashers they will just unload the dishwasher and they'll be gone right so I need to talk about certain puzzles certain probably need to talk about problems and whether or not we can do them or not okay so I want to talk about problems but the only problems I've mentioned so far been very difficult problems I've talked about the problems of you know writing an app you know the ultimate unleashed killer robots that's actually a very difficult problem for an engineer because there's lots and lots of components that need to go in it and then somehow beating the world chess 7hs is also very difficult and what does it mean for it can be even trying to work out what the questions do computers think that's very very hard and you know different people have different opinions so we won't we need to talk about some simpler problems if you actually want to get anywhere and what I'm going to do first because I don't know how many of you are very happy with the abstract notion of a computer I want to forget about computers as well and I just want to talk about the idea of what a problem is and how to solve it and how to know and how to know we've solved it but also if we get a problem is stuck on then wondering that problem can be solved I want to consider these ideas and the reason I'm giving this talk really is because I was TJ big course this seven I thought a lot about about proving things and how to prove things and so that one thing led to another I got very interested in this topic so here's a ROM raised by the ancient Greeks can I bisect an angle using ruler encompasses so there's an ancient that 2000 year old problem the age degree so you know we have Euclid we were very good at this kind of thing the ancient Greeks they were very interesting this kind of question so if I can have the visualizer on I will now demonstrate what an angle is and how to bisect it using ruler encompasses for this on the Holloway Road today just the same as the one I had when I was in the sixth form and lo and behold pair of compasses fabulous and a ruler and I've also pinched one of my daughters felt-tip pens so if she calls I'm sorry here we go so first of all I need to draw an angle so there's an angle that looks or so okay I think that's okay I don't a fiddle can you see the angle I think it's okay there's a shadow maybe I shouldn't worry and here's so right so what's the angle and what the job is what's the question the question is can we bisect the angle and bisect as maybe many of you remember bisects means I need to draw a line sort of just around down there kind of exactly in the middle of this angle I see well I need to cut this angle into two equal pieces right that's the kind of thing that the ancient Greeks were doing these people like these people are usually wrote entire book on it right so can we buy sake the same you see in the point is you can't get you can't going to go well it's kind of you saw about that's you're not allowed to do that you're not allowed to guess you got to do it exactly but we don't just have a ruler what some compasses can we see them there we go so watch this is how you do it first of all you put the point of the compass dead on that angle and then of course we draw a circle okay or I only get all that bit of that circle and now the thing about circles is the the distance from the center of the circle to the edge of the circle circumference of the circle is always the same wherever you try on the circumference so two things I know for sure well one thing I know for sure is that that line there that red line there is exactly the same length as that line there because I tell you I tell you what the length is the length is this length here the length is the distance between the pencil tip and spikey bit so those two lines are definitely the same length okay and now I'm going to do something I'm going to put the spiky bit here it's probably got a name but I never they don't even have these I went to the seige recovered it Imperial said could have a pair of compasses there looks me like I was an idiot so apparently things have moved on I don't know so they're well I'm chatting away I'm doing site of hat you didn't even see what I was doing I put the I put the I put the point thing there and I drew a like I drew put the pointy thing there and I drew a little arc and those two arcs have met at that point there and I'm going to draw these two lines now and again in both cases that is a line that went from where the point of it was to where the pencil pit was so I've drawn four lines now with all those lines of the same length so great for sided shape all lines of the same length what's he going to be it's going to be a square so it's not square because it's a bit squashed it's called a rhombus okay and now we open our copy of Euclid's elements there's 300 BC can we find the proposition so it says you've got a rhombus like this and you draw the diagonal of the rhombus I still in pencil it is not the same that all the red lines of the same notes here we go let's do that in pencil there there's the diagonal of the rhombus and you can see the rhombus is very very symmetric right and so this is a line of symmetry of the rhombus and everything's all the same this angle this angle and this angle are going to be the same Thanks because of oh it looks quite oh yeah I just was looking at that one it looked terrible it does look quite good up there so there we go so we've drawn this line and it's cut and it's cut the angle in two to eight is clever who's been known for two thousand three hundred years and yeah in a book that was apparently forcing to read even up to the 19th century if you were an educated person than you'll read Euclid right i bisected the angle and I need to can I can I have the the PDF sides oh here we are so I bisected that angle so here's a question here's a theorem here's a theorem a mathematical theorem it's possible to bisect an angle using ruler encompasses okay and the proof of the theorem is you just watch me do it right and I talked I talked your way through it and I convinced you tutor that I was doing it and of course Euclid does more than that he like labels for things a and B and C and you know just sort of math see things that you maybe do at school and and ends up proving that you can bisecting angle using ruler encompasses so it can be done and you know not only that the reason it can be done is because I did it okay so in fact Euclid did it 2200 years ago and now here's another problem based by the ancient Greeks can you trisect an angle using ruler encompasses so bisect means cut it into two equal bits trisect means cut it into three equal bits so can you try section angles using ruler and compass you kind of think once you got bisecting you kind of thing you you know you're on a roll you try try setting and the ancient Greeks couldn't do it okay they found it very difficult to trisect angles using ruined compasses so so that problem sat around unsolved with nobody doing it and and and somehow if you can't do it then what other alternative is there in two thousand years eighteen 1837 chap called Pierre Bansal proved it was impossible to do so that's why the Greeks couldn't do it because it was impossible to do it and I mean bisecting the angle is kind of cool but this is super interesting because proving that is impossible to do something that the questions are formally very similar bisect an angle trisection angle but we solved one of them by doing it and then two thousand years later we solve the other one by proving it can't be resolved the question it cannot be done and that's why the Greeks felled but the Greeks didn't want to conclude it couldn't be done they just wanted to conclude they couldn't do it so however does one prove it's impossible to do something it somehow I don't know and since that result seems striking to me so what advance will have that the ancient Greeks didn't have the ancient Greeks you know they had they had geometry and they were beginning to develop some arithmetic and these were some other two fields that mathematics they were completely disjoint sometimes they didn't have much abstract mathematical machinery available to them by the early 1800s when bouncer was around mathematicians had worked at what 0 was room for the Greeks every number was positive they'd invented zero negative numbers the Cartesian coordinate is a big insight Rene Descartes observed if you have a point on the plane you can think of that point of having an x-coordinate and a y-coordinate so suddenly that point which hitherto had been a geometric notion that point who suddenly has a as an arithmetic interpretation it's we can we can explain where that point is using numbers this is a link between geometry and arithmetic that the Greeks didn't have so you know it took Rene Descartes and but nowadays everyone you know it's kind of a trivial thing you draw graphs and this is y this is X and you just thought it but someone had to discover this the tedactive genius they discovered it and also these people got you know because they were also quite good at arithmetic that long since isolated these four basic plus minus times and divide but now instead of thinking about all the numbers they've been interested in kind of subsets of numbers there may be things like the rational numbers you can do addition subtraction multiplication division on them and and now this is somehow when things begin to get interesting they developed an abstract theory of dimension so they consider these fields of numbers they consider a collection of numbers call it field numbers so they consider a bigger collection of numbers they call it a bigger field of numbers and they realize that there was a notion of dimension the bigger thing had had a dimension over the smaller thing and if you make the smaller thing really small you can make the dimension get very big so this is not kind of a real-world dimension this is an abstract mathematical notion of degrees of freedom and you using these abstract collections of fields of numbers they could they could construct objects that had some abstract very large dimension okay so 2,000 years to develop these concept but once they were developed Basile could take them and he realized that it was impossible to try set notches anyiah he proved it was impossible even to trisect a 60 degree angle using ruler encompasses so basically he looked at the system's I don't want to bore you really but this is why I teach in my third year Galois theory course he looked at the systems of numbers generated by the coordinates of the using he turns the geometric problem into an arithmetic one he looks for the number systems generated by the coordinates of these points that you can only construct with the ruler and compass and he proved that the dimension of all these fields was always a pair of two eveni proved that the system of numbers you generate if you can try section 60 degree angle got to mention three and three is not in that list that this goes 1 2 4 8 16 dot dot never contains number 3 so this is how the proof worked so the conclusion so far is that Euclid proved it was possible to bisect an angle and Vance will primitive is impossible to trisect an angle using ruler encompasses and so we've learned from this the mathematicians can prove something is impossible by just doing it the maker also prove that something is impossible but actually it lies deeper right it often lies deeper you know it might take thousands of years to develop the theory ok so we're going to see another example of this next so bansal's fritter and of course as a remarked vassal previews of modern tools you know modern things that were nowhere near known to the ancient Greeks and but the modern tools as well as doing modern mathematics they can solve ancient problem so he's in some sense vindication of the modern tools the fact that they can resolve ancient problems so this film is commonplace in mathematics you you get questions to arrays and sometimes take hundreds of years to answer and the tools you'll use it answering them are often not tools that were even in existence when the questions were stated so there's mathematics now let's talk about computers so there's the first error computer programmer ADA Countess of Lovelace so why she the first ever computer program because she wrote the first ever computer program so guy called Charles Babbage he was not really a mathematician he was more an engineer but he designed something called barrages analytical engine and and the idea you know he was a machine but actually it was a machine you could set the dials and you could actually tell the machine to do lots of different things it was it was a very primitive kind of computer you set the dials that's like writing a program and then you run the machine and the machine runs according to where the dials are said so this is really the the first the first computer that was around in some sense this analytical engine and Berridge gave lectures on in Italy somebody took notes in French and these notes made it into the hands of Ada Lovelace who decided to translate them into English and while she was translating them of course you translate them you read it she read it and she learned the material and then she wrote series of appendices after that at the end of Babbage's those and appendix G the last appendix there's an example of where you could set the dials in order to run a program that would compute Bernoulli numbers which were at the time worth think you know people you know people would compute things by sitting down with pieces of paper and writing them all out and her observations binary numbers kind of a bit annoying to compute but if we have one of these analytical engines then actually we could just set the dance like this switch you on and out come the bedevi numbers it would you know save somebody a job so Ada Lovelace she wrote the computer she wrote the first computer program and so also so we can describe to her a theorem a computer can calculate the nume numbers right and the proof is do it just like the proof of bisecting the angle was doing it the proof is let's just write a computer program that computes Bernoulli numbers so that's what she did she never she ever saw it run because a Babbage's analytical engine was never built in fact theater so there were technical design problems at the beginning and by the time these things were resolved the money had run out the funding dried up and the analytical engine never got built and Lovelace died at 36 and never saw her program run but of course nerds went away and you know made made other ones so it does work and it computes binary numbers so you can see if you're thinking you see where the story is going right so now the theory now we skip forward a hundred years to Alan Turing and ensuring he thought about computers as well but he wasn't an engineer he was a mathematician and so he started thinking about mathematically modeling a computer kind of like using arithmetic to study points in geometry he started he started to wonder whether you could kind of model a computer using the language of mathematics and nowadays this thing is called the children machine ensuring the mathematical description of a computer it opened the doors for mathematicians now to start proving much more deeper and profound results about what computers could or couldn't do and of course we're in just the same situation right you've got a problem the question is kind of computer to it if the answer is yes how do you show the answers yes you just write to computer only does it how do you show the answers no that's going to be difficult right so Lovelace isolated this interesting problem computing veneering numbers the charity computer could do it insuring also isolated an interesting abstract problem but he showed because he had more tools than updates he showed a computer could not solve this problem and again when you just step back however are you going to prove something like that is it how can you check that every single computer program that ever was written will be written can be written will not solve this problem I'm going to try and explain to you how he did it and the probably wasn't just an abstract form as well it's not just a bisect the angle not so this is kind of sad thing Bansal proved you couldn't tri-state the angle by this stage nobody cared whereas cheering cheering works on a problem so actually even though in 1936 when he worked on it complete still there was still no computers right the first computers that started appearing in the forties and you know ensuring actually was involved with several of them but cheering prove this theorem in 1936 before a single computer had ever been built and a single computer brain had ever been run and he proved and he wanted even interested in the idea that computers might sometimes crash and computers crashing is a pain right you lose data you lose information you have to switch it off and on again we don't want computers crashing cheering could see that this was going to be an issue before any computers ever even existed so I'm going to try and tell you a bit about what cheering did so let me try and explain to you what a computer program looks like so this is a computer program written in pseudo so it's kind of read in English but the idea there's all sorts of steps and what the what the processor will do is it will just go from each set to the next step unless somebody tells it to do something else and each that it will carefully read what's there and it will do what it's told okay and it will and it will do it very very quickly so this computer program here step one is going to ask the users of site so you run it you click on you know you have it on your phone you click on the little app and a little screen pops up just type in a number and then you type is number like 53 and you click OK and and you've typed in 53 and the Box disappears and now step two is there XP that number so now if we typed in 53 X would be 53 now step three is a funny thing that involves the question is X equal to 7 but we typed in 53 so X is equal to 7 if X was equal to 7 we've gone somewhere so X is equal to them so we go to step two sinks so we've typed in 53 X is 53 we're at step three eight thousand seven so let's go to step six step six we print hello on the screen and then we stop so when you run this app on your phone you click on the little app it says type of number we type in 53 we click OK another little box pops up saying hello and then that's it that's finished so and that's not if you play with it for a bit you'll realize that's what it normally does but then eventually you hit on the idea of typing in the number seven and so you type in number seven the computer let X be seven in step 2 in step three it notices the X is equal to 7 and so in faragon steps weeks ago step four and in step four as I can see what to do in step four says go to step five so go to step five and step five says go to step four and so it goes to step four and they spent false let's go to step five so it goes to step five and it just alternates between step four and five and this is why you could tell the computers not thinking zippy she even had to do that they get bored at some point but the computer will just keep doing it that's exactly what they're paid to do this is quite happily mindlessly follow the instructions so the computer will get stuck going between steps four and six five now you're running this if your operating system gets stuck in that kind of loop then it stops you've seen line one it's kind of implicitly saying what's the person pressing on the keyboard but if you're just hopping between set for and Step five you're not the computer isn't looking at the keyboard or the mouse or anything like that you riddle these things around and nothing happens and you know what's happened right when your computer's in that state you press the caps lock key in the lights come on you know that your computers had it and you have to switch it off and on again so computer Bri and sometimes get stuck in loops and you've all seen it happen so there you go if the user types in the number seven that computer pro you get stuck an endless loop so it crashes right so here's a much more complicated program and we're not going to analyze it because we just basically spend all day analyzing it all I'm showing that other one had seven steps this one's got nine steps but it's vastly complicated you also uses a type number let's say I don't let's say they type in the number nine step two next be that number step three X is 9 if X is bigger than 10 it's not bigger than to 9/5 and 10 so we go to step six step six says it is less than 10 and it is lesson 10 because 9 is there some turn so we go to step 4 step 4 X changes step 4 we replace X by 2 times X so now suddenly X was 19 at 18 and then what do we do then we go back to step 3 now X is 18 and now X is bigger than 10 so we go to step 7 and you can see me kind of jumping around right X is 18 step servitors if X is less 100 go to step 4 step what we've been to step 4 before so you got anything already an infinite loop but we're not in an infinite loop because we were in step 4 before X is 9 and our it's step 4 again but X is 18 and so we're not in exactly the same state as before so we might not be in an infinite loop and X is going to replace by 36 and you got to see it jumps around right we didn't even go to the side something to step 5 is ridiculous we it's not really clear whether this this is the question can this computer program get stuck in an infinite loop that is a tricky logic puzzle right and don't fancy doing it in somehow I would try and do it using intuition I would kind of try to find key numbers which somehow behave differently to other numbers but can this computer own get stuck in an infinite loop figuring out that kind of question is a complicated logic puzzle now I like doing complicated logic puzzles but actually at the end of the day what what kind of gadget is really suited to solving complicated logic problems it's a computer so what we should really do is not bother solving that one we're told we should what does that mean does that does mean I stopped right let's I'm halfway oh that's good because I'm halfway through the sizes are because the last two slides are jokes so this is the sort of puzzle which would be ideal for computers to work on and so this is what shirring decided to work on let's try to compute a program that checks other computer programs to see if they get stuck in infinite loops right so when a computer brand get stuck in at input a loop will let it crash and that's bad right so we'll say a computer program is bad if you can get stuck in an infinite loop and whilst a computer browny who's good if it never gets stuck in an infinite loop right so there's some there's some definitions and now cheering says how do we check to see if a computer program is good right we want to tell the good programs for the bad programs so he's going to write a computer program right so he's in his 1936 paper he act abstractly action Batali's mathematically what a computer was and so now he could use mathematics to work on this question and he found the solution which so you probably guessed minor so turns going to try and write the computer program and the end purpose of the computer program is not a number and this isn't about like you've probably gone to some websites and I do this or I'm typing in when I'm writing references you click on something it says upload your reference and you find the reference and you just drag it over it's not computer programs will quite happily accept random files as inputs rather than just numbers so this computer running the cheering scanner right it's going to write computer bro that takes us input an arbitrary computer program a different computer program and then Curie's computer brain is going to print out good if it's a good one and bad if it's a bad one okay so Cherry's going to try and design that computer program okay so but actually that something interesting has kind of happened here because if I've got a computer program that takes as input a computer program that means that you kind of like take the computer program itself and kind of put the computer program into itself which is a little bit better and and that was somehow that was where the fun that was where the fun started so cheering roads if he could tell good from bad with the computer program then he could write a ridiculous useless computer program computer program K which would behave like a bad program of human such a good program will behave like a good program if you input is a bad one so the idea is you input the program the computer where you you know crazy program K figures I've if it's good or bad it is bad that's great it just if it's bad it will just stop and if it's good it will intentionally go into an infinite loop and be bad so program K is bad if the inputs good and okay is good if the inputs bad and then of course you take program Kay and you feed it into itself okay now what's the consequence so now we could ask is the aunt if the are going to be good or bad if cait's bad then you feed into k and it's good right if K is bad then K must be good and if K is good then K must be bad so there's something wrong right because the computer Rome Carly both good or bad so we must have made a mistake because we've got a contradiction and the mistake is of course the two letter word that I underlined that I'd put in red right the tulip the mistake is cheering's initial assumption that we could write a computer program which can tell good code from bad code so that's chewings mistake i mean it's not a mistake of as an assumption the assumption is the only part of the earth of the argument that he could make completely logically valid so his assumption is wrong and cheering conclusion is it's impossible to write a computer program which can check any and every other computer program for bugs you cannot and this is why computer variants will crash because it's impossible to tell evade complex so cheering rigorously proves that in 1936 remarked still before any computers had existed took him I mean I've sketched the idea but but what you know what I want to stress is absolutely crucial to it all was the fact that he could turn the kid abstracted what a computer was and put it in mathematics you see so there we go so there's a summary of this bit Lovelace proved that a certain interesting problem can be solved using a computer program the proof was just do it cheering proved that a certain program a certain problem could not be solved using a computer program 100 years later once the once the machinery got more sophisticated so again we see an example cheering proof that it was impossible to do something and in my mind you know it's kind of an amazing it's an amazing thing to prove you can't do something okay so it's formally just like try selecting angles right you so this is what happens in life this is ivan's in mathematics people work on areas of interest and eventually their range of obstructions they run into problems which they can't solve and people work on them and of course sometimes they get solved later on but sometimes they remain obstinate and then eventually it turns out the reason they were obstinate is because it's because the answer is that you know you're you're mathematical machinery cannot cannot solve this problem right so you know I mean so very brief summary we could be possible to do something by doing it we can prove is impossible to do something but it often lies deeper so we've seen an example in pure mathematics and we've seen an example in theoretical computer science theoretical computer science with a capital T really because what do I mean there's an issue with cheering's computers that I'll come to now so what we're really interested in nowadays is because now computers do exist and they're becoming vastly dominant in our in our lives I'm going to talk about a practical problem involving computers so let me first tell you I told you that cheering acts humanized abstractly what a computer was and here's some of the problems with cheering spherical notion of a computer firstly had an infinite amount of memory because mathematicians kind of used to things billion but there's infinitely many numbers so had an infinite amount of memory and he didn't really care about processing speeds or what he cared about was did he get stuck in an infinite loop or not right so if you had a program but it turned out got stuck in a loop that would basically take a million years to get out of but in a million years your mouse will magically start working again and your computers didn't crash after all you see you don't really that's until you don't somehow if it's if it's going to take a million years you're not really interested right so in reality computers have memory a memory this is an engineering quote memories made of stuff right like terabyte hard drives are made out tiny tiny little magnets and solid-state drives are made out a little you know electrical circuits but any memory locations that source a piece of information is going to be needs to be physically made if you're going to make one in our universe and stop looking at abstract computers like cheering so we're going to need like at least a particle okay one at least like bare minimum we're going to need a particle to make that thing and unfortunately there's only 10 to the power 18 but that's one with 80 zeroes there's only one with 80 zero there's only that number of particles in the entire universe so that puts a limit on how much memory it actually computer a computer can have and similarly quantum mechanics says that when you look very very small things get much you might expect so one of the consequences of quantum mechanics some currently believed theory is that there's basically a smallest unit of distance which is meaningful to talk about and beyond that things just get kind of get too straight and is a very tiny distance but beyond that distance somehow everything becomes meaningless their information if you believe relativity information can't travel faster than the speed of light so one might ask how long it the light would take to travel one of these are one of these plank distances is all doing with Planck's constant stuff and it turns out that light would take ten to the power minus forty four so that's naught point and then 44 naught sort of one no it's not it's nor point there forty-three naught send one there's one Planck time ten to the minus forty four seconds so you cannot hope that your computer can do anything because it's impossible to do anything in a unit time shorter than one Planck time well of course the earth will become and it habitable around a billion is we're interested in computers on earth then this is going to be an issue and if more generally we'd be interested in computers in the universe that we have to kind of figure out when the heat death of the universe will be but I read a lot about this on Wikipedia and somehow that's scientists aren't sure they don't really know if the universe is going to expand forever I mean they know they believe in the Big Bang but they don't know if there's going to be a big crash or if it's just going to stop or so I don't really know when the universe will end but certainly the Sun will burn out in a few billion years and by by 1 billion years it will be this red dwarf and this you know this seas will be boiling so and again if you think about it that puts some theoretical limit on the number of instructions that any computer can do so let me just summarize so summarize I'm not now interested in Turing's abstract theoretical computers what about computers on this planet they can't run a program which involves storing that much information where that much is just some number I've chosen very large to make sure that it's more than the number of particles in the universe and similarly they can't run computer programs in which the processor has to do that many instructions because again I've just chosen it's very very large number to make sure that even if it did 10 to the power 44 instructions every second is still you know the the you know the world is going to be a dead Hulk by then so there these are limitations that cheering didn't that tune didn't really care I mean tearing out other things to think about I mean there was a war on and but these big men these issues but these issues are now practical right it's not just can be solved upon more not is can we solve the problem quickly okay so these now give rise to new questions it's the last thing I'm going to talk about the remainder of the talk I'm going talk about a third question so here's two computer they're not like these nightmare once I just showed you here's two very simple computer programs because I need to teach you a concept computer program one the user types in a number the user types in 53 and then step two let X be that number so X is 53 and all it does it doesn't print hello this when it prints out X okay so Sowell run a program but the user types in number 53 and clicks okay and the computer printout 53 so just print out what you type ok so computer program to formally looks very similar this time the user types in a number you let X be that number but now instead of printing out X using our normal notation for printing numbers out instead of all it does is print our X think am 53 has a meaning right 53 means 53 sins so instead of printing out our clever notation it actually prints out the meaning of the number so it prints out 53 things so well I'm if you don't like 9 3 then how do you actually print out X 0 is what you would really do is you just print out 1 0 and then you'll decree text by 1 and if it was still positive then you'll keep going back so you'd actually do this using a loop so that's how you that's how you print out X zeros using a computer program so now of course sample run let's type in 53 again and this is the output we just get 53 zeros so now let's have a race program one against program to will type in 53 so both of them in who's going to win program one's gonna win because program twos got to a lot more work you see first prime is going to finish what I mean in practice of course both both will finish in the blink of an eye so you won't even be able to notice but I want to explain a way of telling why this second program must be worse than the first program what it's or less why it works more slowly and is because of scaling so by scaling I mean let's not type in 53 let's now think about typing in a bigger number let's five a five and then a three type another number so instead of typing in 53 let's type in 531 okay and now let's run our two programs we saw apple and we type in 53 now let's type in 531 right the first program or you still have to print out 53 now it's got to print out 531 it just takes one more digit right not really much more time at all the second program is going to print out 531 things now when 531 is about 10 times 53 so the second program is going to take 10 times as long to finish so they behave in very different ways with a small perturbation of the input date if I make the input date or a little bit bigger the first program deals with it easily the second program the second program the amount of time it takes gets multiplied by constant so you have this compound interest phenomenon so if you leave if you leave a penny in a bank long enough eventually you'll get to a million pound sort of thing because because things can blow up some substantially yeah if you if you if you double your money every time then by the time you've doubled your money 10 times you've you've multiplied your money by over a thousand so this is this is an issue that the second program has it doesn't scale well you make the input a little bit bigger and suddenly it takes a lot longer to run so when you're trying to solve real-world problems input data might well slowly increase so you kind of make sure you want to make sure that your computer program doesn't ground to a halt if the input data starts getting bigger and bigger okay so an example is you know it's a very complicated problem trying to work out when all my students when all the students in the college you're going to take exams because lots and lots of students have lots and lots of different courses so you have to make sure that every student they haven't taken two courses for each the exams at the same time but all these has got to be crammed in to a small period of time so you have to have some exams at the same time very delicate question so right if we wanted to compute a prime source code of course we do have a computer problem to solve this to this and we want to make it scale light program or not like program to so scaling I talked about it informally the mathematicians have formalized these notions okay so the first time you do a history historical search the first time you see this notion of pro-people really beginning to care about not just abstractly where the computers can do things about how long it takes them to do them within letter 1955 letter enjoy this is the beautiful mind guy 1955 letter from John Astor the NSA the American you know security agency where he began began to lay down the URI he isolated the issue that actually it's not about whether the computer can solve it it's about how quickly the computer consultant and he raised explicit problems in the area someone which you can solve so if you like so I'll tell you what now said because these are kind of important words and it's just Skinner so computer runs in polynomial time if you scales up the first program that's an informal definition I'll give you a proper definition it's the proper definition there so formally a computer program runs in polynomial time if there's a polynomial function like that n to the power 20 plus 1000 so so if you've input number with n digits then the computer one will turn away and it will finish but how long will it take to finish the program will finish but it will do what most PN steps okay that's the idea if you can write a computer run like that then you've got a polynomial that's kind of controlling how fast your computer will take to calculate and polynomials don't grow too quickly this is a somehow morally forethought but also in practice polynomial time computer programs or what people are after they were holding if you give you've got a problem you can solve in polynomial time then somebody has already written the codes that will solve that problem for you it will run very efficiently so we're interested now in the collection of problems which can be solved not just we can be solved with a computer and furthermore the confucian solve it quickly problems that can be solved in polynomial time and mathematicians being what they are they needed a name for this collection problems so they called it P because that's kind of that's what they do so that's now called P so a collection of problems which are actually which we can solve in practice quickly okay so now let me just mention codes a little bit coat secret codes are really good you agree on a secret code with your friends and then you've got you've got the secret code your friends got the secret go but nobody else has and now you can send messages to your friend using the secret code because you got your message you equip to using the secret code you said to your friend and they decrypt it using this you post up the secret code but no one else has got the secret code so it works so I'm afraid nowadays things aren't so easy because I want my phone to kind of connect to random - yeah I want my computer to talk to well because if I go to a web site never been to before my computer is suddenly talking to another computer that's never met before and I might have to type in my credit card details if I want to buy something and now I need to talk to this other computer I need to send the computer secret piece of information but we haven't got a secret code and having it you see the problem is people can hear what you're doing on the internet your ISP knows what you're doing you have the government probably knows what you're doing and like people that are just generally snooping around on the Internet my see packets going by from your computer so this is kind of a problem it means what secret codes aren't good enough anymore we need something called public key cryptography where the orders I establish a code we're going to use and even if somebody is snooping on my packets even if my next-door neighbor has got some kind of Wi-Fi detector thing and they're watching all my Wi-Fi packets I need to make sure that they can't they can't find out what my credit card is so these things are called public key codes public key cryptography and rather surprisingly they exists they were invented they were invented in the seventies when these when it was realized that these things are important and the way they work is they exploit eight symmetries in encoding and decoding algorithms so the idea is you want to make sure the encoding is quick but decoding is slow so let me give you an example of an asymmetry we've got a piece of cotton I'll give you a long piece of cotton and I'll give you two minutes that you can tie as many knots and as you like and you can tie lots and lots of knots and at the end of it you can imagine you can make this piece of cotton into a real mess lots of lots of tiny little knots you pull them tight but like after a while the knots kind of get you've had done this I've done this if the knots kind of get closer closer together and they kind of start compiling up on each other and at the end you get a nice kind of chunky little thing that's really difficult on time so you get turned a piece of cotton into a big company and you know it's very easy give me a couple of minutes are you complicated not on the other hand you've got a big complicated knot you got to untie it it's gonna be very difficult see a skirt is going to be possible but it's going to take a lot more than two minutes okay so something's inside for a symmetric right and surprisingly something you know a lot about multiplication turns out to be one of those things so here's a multiplication problem without today I'm going to tell you the answer don't worry well it's 43 times 61 there's a method right you learnt at school wrong multiplication 43 times 61 a Devery do one three one four three sixes and four sixes and what and then we do some adding and we've got the answer and how many steps could be actually take we need 1 times 3 1 times 4 3 times 6 4 times 6 we did we did under 10 steps ok so long multiplication is actually a really good method for multiplying numbers together that's scales real here's the clue that it scales very well what are the numbers involved the smallest number involved is 43 but did it take 43 steps right did we actually win remember that computer role that you typed in 43 would print out 43 zeros that takes forty three steps here we didn't use anywhere near 43 steps we did it at under 10 so that's the clue it scales very well ok so now let's add multiply so here's the answer 2193 i times two numbers together and I got 2183 and what were those two numbers now they don't teach you how to do out of school and and so let's do travel now was it two times something we could divide 2001 183 by 2 it doesn't work we get remainder 1 so let's divide it by 3 it doesn't work we get remainder 2 and so this divided by 4 or if you're smart you'll skip 4 because you're done too and you'll go to 5 but you keep dividing and dividing and dividing and eventually you divided by 36 it doesn't work you get remainder 23 you divide 2183 by 37 it works on the notes there's no remainder it's 59 so we include 2183 state 7 times 59 but when you think about it so what are the numbers involved in this question 2183 and 37 and 59 and how many steps did it take you see this method is give a scale poorly because we basically took 37 I guess we took 36 steps because we didn't divide by one but this particular method for undoing multiplication scales very very poorly just like the second program because the answer the answer involves 37 but it took 37 steps whereas before you're multiplying these things together we do it under ten steps you see so there's an asymmetry you multiply them together in just a few steps but I'm multiplying them fighting them is called it took forever well it took 37 steps I mean 37 is a very long really but a so before I get on to that point that I was about to make every published method for unmultiplied numbers in fact scales poorly some of them scale less poorly than this one every published method scales poorly we don't know how to do we don't know how to do that so factoring actually might be a problem that is not possible in polynomial time and now let's scale if instead of multiplying two digit numbers together we started multiplying 100 digit numbers together then we can multiply them together we have to do this times this this times if you have to take a digit from the first time but it is you from the second number they'll take that 100 times 100 10,000 so we do 10,000 multiplications who do 10,000 additions if we do about 20,000 steps right that's not a problem do 20,000 sets in the blink of an eye but remember I'm talking about numbers with a hundred digits here those numbers have a meaning right they we write the values neat way one nor nor none always very clever but they have a meaning and the meaning is vastly vastly huge number of things that you can't even comprehend and indeed it's a number too big to fit in the universe it's a number bigger than the number of particles in the universe so that number is representing an idea that's too big for our universe you see if we just know the answer the 200 digit number which we get might items together and we want to recover the factors and we're going to use this method I explained we might have to count all the way up to a 100 digit number and we can't do that right because the universe isn't big enough we don't have enough time and we'd have enough space and it can't be done at least within my lifetime and when you're sending secret codes you kind of you're not really worried about whether they cracked after you're gone all right so it's so this kind of is not just yeah that's my lifetime is somehow this is our relevant data but here's a funny thing about factoring if somebody actually told you the answer so he said you know what I think the answer might be this and they just gave you two 100 digit numbers you would be surprised that they've solved the problem but you can check to see if they're right or not because you've you've got these 100 digit numbers you can tie them together and see if you get the 200 number you're supposed to get so factoring has it sort of funny this funny thing about it is hard to do but if somebody tells you what the answer is very easy to check because you can just because multiplying is easy so factoring it seems to be hard to do but it's definitely easy to check and the notion of a problem being easy to check turn out to be another central notion in a modern computational complexity theory so he got a name NP is the collection of all problems for which we can check a solution is correct very quickly by which I mean in polynomial time ok so I've defined two class of problems P because the problems we can solve quickly and NP the class the point that if somebody tells you what they think the answer is you can check if they're right or wrong very quickly so that there's there's subtle differences for different they are so every problem in P is a Tempe okay all the problems that you can solve quickly you can check the article Italy because if somebody if you've got your if you've got your P problem that you can solve quickly and something says oh I think I know the solution and they give you the solution you can check it by just solving the problem yourself you saw the reviews ever you see if you get the same answer so any problem in P is also an MP have I got a picture oh no but unfortunately there's plenty of MP problems problems where we can check the answers quickly but which we don't know how to solve them quickly so this raises a question so here's here are some examples of NP problems from as we can check quickly which not known to be NP so factoring large numbers I've mentioned that already we don't know how to do that quickly but if someone told you what the answer is we can do it clearly time table exams unfortunately so that's be another problem and general problems of that nature you know I just I've had three kids going to secondary school and the way it works the way it works is you is the council sent you a form and you fill in the form and this is in like November or something you send in the form and then the glorious news comes out where your kids can say grease cool on the first of March and why does that take four months is because trying to figure out a way of fitting every every eleven-year-old in the country into a school so that there's just the right number of students in each school is really really hard so those examples all over science these things I don't know what I just took these things off Wickery I've got no idea what any of those things mean but they look very important as I thought I'd mention them so this this is what I do know what it means decrypting datacenters we have a standard way of Sony data secure website to secure when we're typing in typing in the you know typing in credit card numbers to buy things on the internet and decrypting that without the decryption key is something that we don't know how to do very quickly but as I say it's in NP there's various other things candy crush is an MP Pokemon also an MP Super Mario Brothers also an MP basically trying to solve a Super Mario Brothers level is very hard because someone comes along and so if somebody comes along and does it you can clearly check that they've done it because I've got to the end so we don't know if I'll spent of solving any of those problems but we have a fast method for checking the answers so there's examples of problems there's our MP but we don't know they're in NP but we don't know if they're in P okay so there's the question does P equal NP if we can check if we have a problem and it turns out we can check to see if the solution is correct quickly kids we actually have solved the problem quickly in the first place without knowing what the solution was am i doing all right I thought I was going to overrun I'm doing great so there you go by 1971 Steven cook had formalized this notion and he raised this question explicitly in 1971 having laid down some mathematical background so he's given a rigorous mathematical notion of what a problem was or what a solution was and the class of problems that are in P in the class of problems are in NP those sorts of mathematics and rigor that I'm suppressing but he did it and he raised this question he's recently and then the year after he failed to get tenure UC Berkeley and because computers in 1971 were really irrelevant right so it's an abstract well-defined mathematical question and it was an cell problem that the mathematicians that UC Berkeley decided was a peripheral interest but you've seen now the kind of the kind of implications that solving this from might have and it's now regard as one of the most important problems in mathematics is one of the seven clay millennium problems if you solve whether if you solve it some entrepreneurs donated and milli but as motivation to try and solve these problems turns out so that's what we've got the problems in P they're in there with the problems in NP and then the question is they're actually definitely a problem that's lurking where that question mark is there's in MP you can check the answer quickly but it's definitely not in P right so we know plenty of problems that are in P and we don't plenty of problems that are in NP and we don't know if they're in P or not but that's that's the current state of our knowledge okay so what would happen if somebody proved the P when in P because mathematicians are working mathematicians theoretic computers working very hard on this problem what would happen somebody prove P equals NP then all of a sudden a whole bunch of problems which we didn't know how to solve suddenly we could solve very very quickly using a computer right so suddenly transportation get scheduled optimally we save lots of fuel people and goods move around quicker and cheaper factories become infinitely more efficient dramatic advances in medicine because suddenly we can you know we've cure cancer that I'd every cure cancer we would certainly make vast we totally do much quicker experiments perfect computer vision computer language recognition so you see the problem it wasn't very important in 1971 but better predictions of weathering of earthquakes huge advances modern mathematics because you solving a mathematical problem is a great example of something that's in NP I work in a problem I can't do it there's lots of actions I don't know which to I don't know where I don't know how to apply them or what order to apply them in but if somebody comes along and has to be a proof of this you know if someone says I can prove something I can sort everything you're working on here's the question you're working on here's a proof of it I can read the proof really quickly I can check and that's the mathematical proof that's kind of part of my training so I can check the answer quickly and so a pig with MP I can solve a problem quickly so we can just get computers to do lots and lots and wonder mathematics and also means of course there is no such thing as encryption anymore so the government can read all your emails even if you encrypt them and Internet Security is now broken you can't type your credit card into the internet so online banks instantly everything gets stuck so society really changes the internet it stops the internet stops working but maybe we can cure cancer so it's but the world would be a very different place unfortunately my army or possibly fortunately most computer scientists believe for P is not equal to NP they believe that there our problems out there which are easy to check but hard to solve easy to check the solutions for how to solve so what would happen if we proved that people's not equal to NP then we know then with these then these guaranteed out we have algorithms which we now guaranteed can't be sold quickly now we definitely know we can talk in code so I know that the government can't spy on me that's really good and terrorists also know the government can't spy on them and all the people that are currently selling illegal drugs and weapons on the dark internet and that really is happening they can sit comfortably knowing full well that sir they can definitely not be traced so again the world changes a little bit but and this is currently the working model right to resume was very very upset about about this you deserve as an iPhone story remember this some guy the incriminating evidence on his iPhone but they couldn't unlock it and an Apple said they weren't going to unlock it and but yeah the problem resolved itself but that's the tip of the iceberg more will happen again there will be police officers that know full well that there's an encrypted driver if they could decrypt then this guy's nails but they can't decrypt it if P is an MP we can we can design codes that going to be impossible to prank so it should be clear that it's clearly important to locate peers MP or not right so all the problems in PR in MP but the question is are there problems in NP but not in P though where am i it's me I thought I'd finished if you tell me the suit will probably class P I've said all this already so hard I know this is a point sorry I will tell you the point how does a mathematician so P probably isn't equal to NP so has the mathematician going to prove that right and this is the point all they have to do is I have to find something in that question mark I have to find a problem which is in NP we can check the answer quickly but they have to prove they had to prove that this problem cannot be solved quickly that's that's what the problem is and we're not yet at the stage where we have to see reticle tools to do that this is the issue we have to prove that you can't do something and we could only prove you could do things in the seventies so when are we going to be able to prove that you can't do things right so here's the time frame now the third example of doing things are not doing things not you know formulates the question gave easy examples of problems too could be sold quickly cook formalizes to mathematics raises the question explicitly and then we don't know what happens right somebody at some point probably will find an example of a problem where they could check answers quickly but they can prove that you cannot solve it quickly but we are not yet there took two thousand years for the Euclid one how long will this take so many modern mathematical techniques have been tried all of files so and you know say some technical thing there was a promising there was a promising promising approach developed in stud initially in 2001 and then really prominently in 2011 using geometric complexity theory and again follows exactly the same pattern as the other things this use modern algebraic geometry which was only invented in the 1960s and modern representation theory so using these very very modern techniques that weren't around we were like Cooke and Nash geometric complexity theory was an attempt to resolve this question but the big breakthrough in April last year was a team of people proved that actually the path that we were following using geometric complexity theory to prove that people sausage wouldn't be they proved that it would not work so you see mathematicians are good at proving that things don't happen but in this case it wasn't proving the P wasn't MP is through that our idea is even some SMS ax right the strategy of proof cannot cannot succeed so they go so that's the end of the talk how do we prove the interviews can solve a problem quickly currently we don't know the answer but yeah so thank you you

Channel: The Royal Institution

Views: 275,616

Rating: 4.1599374 out of 5

Keywords: Ri, Royal Institution, computer science, millennium prize problem, science, mathematics, p vs np, p versus np, computing, kevin buzzard, computer

Id: jQPb7DRMoZY

Length: 64min 5sec (3845 seconds)

Published: Wed Aug 02 2017

Reddit Comments

[u/CultistHeadpiece]

Very entertaining