The Most Difficult Program to Compute? - Computerphile

Key Takeaways

so far we've looked at primitive recursion things where you can use recursion if you want to but you don't have to because it can be dsed and turned into an iterative for Loop and we did factorial and we did Fibonacci both of which are primitive recursive in this sense and there would be a great danger in thinking well surely you can do anything then in four Loops why bother with a recursion at all well there are some things which are so fundamentally recursive that you just have to do them recursively it became clear to mathematicians really at the turn of the last century about the nature of functions in general that there were some things that were so if you like huge so enormous so badly behaved that they just had to be recursively defined and I think one of the earliest people to realize this was a research student of David hilberts now who is David Hilbert we're back on number five territory again probably perhaps the greatest mathematician of the late 19th and early 20th century he was phenomenal uh mathematical genius capabilities and so on he was at gutan in Germany and I think I'm right in saying that aaman was one of his research students and it's V aiman's function that we're going to look at today the test was can you come up with something that just has to be done totally recursively you can't do it as it were in a for Loop even those those haven't been properly invented at that stage what became clear as a result of work started by aiman and by others is that we've got a hierarchy of programed types right down at the bottom the simple ones we've seen the ones that can be D recursed these are primitive recursive there's a whole layer of on top of that where there functions where you just have to Define them recursively just above this set are the recursively innumerable functions let's be clear here by saying primitive recursive at the bottom I'm including every other program that isn't recursive I'm regarding a thing that just goes through a sequence as being a very simple example of a primitive recursive program with no real recursion in it and anything that's got for Loops or nested for Loops will actually you could have done that recursively and probably languages like hcal do for all I know uh but they they still count as the simplest form of program primitive recursion if it's got recursion in there at all you could always D recurse it make it into for Loops this next thing recursive on top of that there's a even more problematical set of programs above that which says they're recursive but for some values of the arguments you put into the function they will stop and give an answer and for others they will go on forever and they will never ever stop to how do you define forever then come on forever and ever and ever they will go into just repeating the same old stack frames and you may not be aware of it and just go round and round and and then you'll say but how can I decide ahead of time for given arguments whether it will stop or won't and the answer is hello Alan churing in general that May well be undecidable so above here out in hyperspace is the great undecidable Universe there are some problems you can set in Computing that just are not decidable at all not by any algorithm and one of the great names in this was Kurt girdle in the early 1930s and the second great name for computer scientists that linked girdle's work with how computer programs worked and with his touring machines was Alan touring he wrote a famous paper in 1936 about his touring machines referred back to Kurt girdle's work and basically said there are some things in Computing that are undecidable but for the moment we're coming in here at the next level above primitive recursive going to take a look at a recursive function where I can reason through with you that it will give an answer it's not in the nasty set above it the recursively innumerables where sometimes it would go wrong and just end up spinning and not doing anything useful this thing and this is a good introduction as well to the way that theoretical computer scientists of which I am not one but I'll try and give you the flavor about how you can reason about programs and how they behave even without actually executing them the version of aiman's function tends to be used nowadays the one Modified by Peter and by Robinson here is where all the hard work occurs this is the recursive function itself we declare a for short a function with two incoming integer arguments and here look it delivers back an integer result it delivers back the integer result in its local variable that it declares for itself for holding the answer and eventually of course look it's going to return the answer but how does it do its recursive Horrors if the incoming argument m is zero then deliver back the integer answer n + 1 so if I came in with acan 02 because the m is zero it would deliver Back 2 + 1 3 easy otherwise if that isn't true if M isn't zero if it's any other integer else if n is zero then the answer is what you get by calling up acen recursively again but this time by reducing the first argument by one call up acan with M minus one not M and with the first argument one otherwise now that's bad enough here comes the real killer if M isn't zero and if n isn't zero What's the general case the general case is that the answer is aaman of M minus one notice you're reducing M again look and this is where headaches start to set in this blows your brain and makes you realize why you can't D recurse this into iteration the second argument for that generalized call of aiman is itself a call of aiman so you have to go through endless thousands of Stack frames to calculate just what the second argument must be to another call of acan that's going to go through the same Agony all over again now I think you can mentally visualize just what a huge amount of computation might be involved here and how big the numbers might get to be but what I would like to just draw your attention to because this is important is that every time M and N are altered in going round recursively they reduce we found out that on the second line it says if n was Zero then you called up a thing with acan of n minus one in it yeah so you're reducing M at that place and even in the horrible worst case the third line you reduce the first argument to n minus one and within that vile second argument it's acen of m n minus one so as you go around this if M and N change at all they are reduced therefore if your first two traps which we've got here are for when M gets down to zero and when n gets down to zer then in the end it will terminate so long as you feed in positive integers for m&n now as ever I have done no error checking whatever that's down to you I want you to concentrate on this yeah if you put negative in numbers in there boy are you in for a rough old ride yeah it's got to be positive integers zeros are fine but it must be zero or positive integers although this is a huge recursive me yes with millions of Stack frames nonetheless by reasoning and saying that when these values are altered they always alter downwards you can convince yourself that this will eventually deliver an answer now the only trouble is that in delivering an answer there may be a huge amount of computation involved particularly when we get onto this third line and you have to run aiman's function in order to work out what an argument to aiman's function is going to be and just to show you how bad this gets I've set up two nested for loops on I and J taking I from zero through to five actually because it's I less than six J from zero through to five and I call up the aaman function as the argument to be printed in the standard piece of text here so you'll get things like aaman 0 0 is whatever and you call a baman recursively to work it out so how's that going for you how is that going for me well what Steve and I Dr heart bleed as we now call him we set this going four weeks ago nearly now the first few have vanished off the talk you'll be delighted to know that aan of 03 is a value of four that aan of 22 is seven aen of 32 is 29 doesn't look too bad now it did have a bit of a gasp for air between 4 Z which is 13 and it finally decided that aaman 41 was 6,533 it still took it recursively on this machine three minutes to work out that aaman 41 was 65533 so this is progress because this of course is a fairly modern quad core penting or whatever it is running Linux the previous machine I had when I first tried this about seven or eight years ago was a venerable Sun Spark blade and the spark blade Miracle of its age took 20 minutes to work that out so 20 minutes 3 minutes we're progressing and then you know I was looking at this with Steve we've set the thing going it's still running and I said oh you know it probably won't be that bad it'll be if it took 3 minutes to work out something whose answer was 65533 it'll take about maybe 65,000 times 3 minutes to work the next one out and did a few calculations yeah about four months on this machine something like that uh no I've just looked into it more deeply and reminded myself of the appalling properties of the acan function when it starts to build no it will take two to the power of 65533 times three 3 minutes per go it will take three time 2 to the 65533 minutes to work out that value that is unimaginably huge it's no good saying it's astronomical it's Way Beyond astronomical the number of particles I think including all dark matter isn't more than about 2 to the 300 something like that the number of seconds since the Big Bang is probably about 2 to the 500 or 600 at most not 2 to the^ of 6553 3 but what's going to happen eventually 2 to the power 65533 is such a big number so we're going to start getting wrong answers we'll either get overflow happening or perhaps if integer overflow isn't signal to us you know integer numbers sometimes tend to roll over the top and go negative so who knows what will happen I'll probably stop this off now when we've made this video because frankly I have not I don't think I'm going to survive for two to the power of 65 , 533 minutes multiply by three for this to come to an end I think the astronomers will probably say the Big Crunch when the universe all gets down to a DOT again even that is probably going to happen in about another two to the power few hundred this sort of behavior is often called super exponential one of the ways of indicating that a function probably has to be done recursively and can't be done in for Loops is when it starts behaving super exponentially not just like n to the power n which will be exponential but n to the power of n to the power of n to the power of n to the power of n done end times and your brain just collapses and refuses to even contemplate what that means in fact I've noticed one commenter thank you whoever it was when somebody said uh surely you can do anything in four Loops what do you have to do toally recursively somebody's picked up I think one of those numbers I don't know much about really big ones called Googles and Google plexes but they've been covered in number far and said how about aan of g64 I think it's called how about aaman of g64 g64 the arguments before you ever start inflating them are still absolutely astronomical but the really interesting thing is that although we can never know what the answer is and the answer to 2 to the 65,000 whatever divide it by three that is going to en 20,000 decimal digits when it finally comes out Way Beyond the big crunch but by reasoning with the program in the way we did we know it is not uncomputable think back to the original hierarchy because we can never know the answer to some of these values does it mean it's uncomputable no uncomputable means there is no algorithm for doing it acan is a perfectly good algorithm you can prove it terminates it's just none of us are going to be around long enough to find out what some of those values are oh I don't know what factorial 3 is it's three times factorial 2 so I've got to know what factorial 2 is so here's the and you draw an arc and you end up with this beautiful looking spiral known as the Fibonacci spiral