The Most Difficult Program to Compute? - Computerphile

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 dearie cursed and turned into an iterative four 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 for loops why bother with the 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 Hilbert's now who is David Hilbert we're back on numberphile territory again probably perhaps the greatest mathematician of the late 19th and early 20th century it was phenomenal mathematical genius capabilities and so on he was at getting an in Germany and I think I'm right in saying that Ackerman was one of his research students and it's film Ackerman'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 Ackerman and by others is that we've got a hierarchy of program types right down at the bottom the simple ones we've seen the ones that can be dear accursed these are primitive recursive there's a whole layer on top of that where they're functions where you just have to define them recursively just above this set are the recursively enumerable functions let's be clear here by saying primitive recursive at the bottom I'm including every other program that isn't recursive and 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 four loops or nested for-loops well actually you could have done that recursively and probably languages like Haskell do for all I know but they still count as a simplest form of program primitive recursion if it's got recursion in there at all you could always do recurse it make it into four 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 do we how do you define for everything 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 in 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 Turing 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 curt girdle in the early 1930s and the second great name for computer scientists that linked girdles work with how computer programs worked and with his Turing machines was Alan Turing he wrote a famous paper in 1936 about his Turing machines referred back to Kerr girdles 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 and take a look at 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 enumerable x' 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 to give you the flavor but how you can reason about programs and how they behave even without actually executing them the version of atamans function that tends to be used nowadays is the one modified by Peter and by Robinson here is where all the hard work occurs this is the recursive function itself will declare AK 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 for two 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 plus one so if i came in with a common zero two because the M is 0 it would deliver back to +1 three easy otherwise if that isn't true if M isn't 0 if it's any other integer else if n is zero then the answer is what you get by calling up acumen recursively again but this time by reducing the first argument by one call up a common with n minus 1 or M and with the first argument 1 otherwise now that's bad enough the here comes the real killer if Emma isn't 0 and if n isn't 0 what's the general case the general case is that the answer is a common of M minus 1 notice you're reducing m again look and this is where a headache starts to set in this Lozier brain makes you realize why you can't de returns this into iteration the second argument for that generalized call of ackerman is itself a call of a come on so you have to go through endless thousands of stack frames to calculate just what the second argument must be to another call of a common it'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 around recursively they reduce we found out that on the second line it says if n was 0 and he called up a thing with a command of n minus 1 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 1 and within that vile second argument is Hackman of M n minus 1 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 0 and when n gets down to 0 then in the end it will terminate so long as you feed in positive integers for m and 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 rougher ride yeah it's got to be positive integers zeros are fine there must be zero or positive integers although this is a huge recursive mess 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 a Cummins function in order to work out what an argument to a Commons 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 0 through to 5 actually because it's higher less than 6 J from 0 through to 5 and I call it the Ackermann function as the arguments be printed in the standard piece of text here so you'll get things like acumen 0 0 is whatever and you call the back ermine recursively to work it out how's that going for you how is that going for me well what Steve and I dr. heartbleed as we now call him we set this going for weeks ago nearly now the first few have vanished off the top you'll be delighted to know that acumen of 0 3 is valuable for that Ackerman of 2 2 is 7 a kamila 3 2 is 29 doesn't look too bad now it did have a bit of a Gasper air between 4 0 which is 13 and it finally decided that Ackerman for one was sixty five thousand five hundred and thirty three it still took it recursively on this machine three minutes to work out that Ackerman for one was 65 533 so this is progress because this of course is a fairly modern quad-core pentium 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 SPARC blade and the smart blade miracle of its age took 20 minutes to work that out so 20 minutes 3 minutes we're progressing and then do 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 there and it'll be if it took three minutes to work out something whose answer was 65 533 it'll take about maybe sixty-five thousand times three minutes to work the next one out and did a few calculations yeah about four months on this machine something like that no I've just looked into it more deeply and reminded myself of the appalling properties of the acumen function when it starts to build no it will take two ^ 65536 it will take 3 times 2 to the 65535 imaginably 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 ^ 65535 65535 ever flow isn't signaled to us you know integer numbers sometimes tend to roll over the top of go negative so who knows what will happen I'll probably stop this off now when we made this video because friendly I have not I don't think I'm going to survive for 2 ^ 65,536 x 3 for this to come to an end I think the astronomers will probably say the Big Crunch when the universal gets down to a dot again even that is probably gonna happen in about another 2 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 ^ n ^ n ^ n to the power of n done n 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 surely you can do anything in four loops what do you have to do solely recursively somebody's picked up I think one of those numbers I don't know much about really big ones called Google's and Google plexes but they've been covered in numberphile and said how about acumen of G 64 I think it's called how about a comment of G 64 G suit of all 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 - to the 65,000 whatever divided by three that is going to involve twenty thousand 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 acumen 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 going so here's the fan you draw an arc and you end up with this beautiful looking spiral known as the Fibonacci spiral

Channel: Computerphile

Views: 1,270,902

Rating: 4.956687 out of 5

Keywords: computers, computerphile, ackermann, algorithm, decidability, recursion, programming

Id: i7sm9dzFtEI

Length: 14min 55sec (895 seconds)

Published: Tue Jul 01 2014

Reddit Comments

[u/MathPolice]

That's a fun video.

A few comments:

• Wow, K&R-style C. I haven't seen that in a good while. "Well-nigh on a quarter century, I'd reckon."

• Hmmm, non-indented code. Unfortunately, I have seen that recently.

• There will not be a "Big Crunch." Quite the opposite, in fact. They handed out a Nobel Prize a few years ago to the astronomers who showed just how massively "not a big crunch" the universe is.
  (as a matter of fact: "You're tearing me apart, Lisa!" <-- mandatory reddit karma pandering quip.)

• As others pointed out, the "recursion" can be done with for-loops and the appropriate data structures.

• If he knows he'll be dealing with recursion of depth 2⁶⁵⁰⁰⁰ then he obviously needs to worry about overflow in his stack pointer, too, and not just in the result register.

• I think (trying to remember what he said) he got his #particles in the observable universe and #seconds since the Big Bang wrong. it's about 4 x 10¹⁷ seconds since t=0. I.e., about 2⁶⁰ or so.

Despite my nitpicks, I love these Computerphile/Numberphile videos. Good enthusiasm. Good presentation. Excellent topics to spread to a popular audience. (Yes, I got very tired of explaining why -1/12 does not equal infinity a few months ago, but hey! it got people talking about Zeta functions, so it's a small price to pay!)

[u/[deleted]]

I just coded this up, and Ack(4, 1), which took the presenter's sytem 3 minutes to calculate, took less than six seconds on my 5-year-old Mac. Funny how computers progress. :)

Ack( 0, 0 ) = 1 (2e-07 seconds)
Ack( 0, 1 ) = 2 (3.9e-08 seconds)
Ack( 0, 2 ) = 3 (2.7e-08 seconds)
Ack( 0, 3 ) = 4 (2.8e-08 seconds)
Ack( 0, 4 ) = 5 (2.6e-08 seconds)
Ack( 0, 5 ) = 6 (2.4e-08 seconds)
Ack( 1, 0 ) = 2 (5.1e-08 seconds)
Ack( 1, 1 ) = 3 (4e-08 seconds)
Ack( 1, 2 ) = 4 (5e-08 seconds)
Ack( 1, 3 ) = 5 (4.8e-08 seconds)
Ack( 1, 4 ) = 6 (4.9e-08 seconds)
Ack( 1, 5 ) = 7 (6.1e-08 seconds)
Ack( 2, 0 ) = 3 (5.3e-08 seconds)
Ack( 2, 1 ) = 5 (9.1e-08 seconds)
Ack( 2, 2 ) = 7 (1.42e-07 seconds)
Ack( 2, 3 ) = 9 (1.58e-07 seconds)
Ack( 2, 4 ) = 11 (2.26e-07 seconds)
Ack( 2, 5 ) = 13 (2.78e-07 seconds)
Ack( 3, 0 ) = 5 (7.1e-08 seconds)
Ack( 3, 1 ) = 13 (3.61e-07 seconds)
Ack( 3, 2 ) = 29 (1.292e-06 seconds)
Ack( 3, 3 ) = 61 (4.555e-06 seconds)
Ack( 3, 4 ) = 125 (1.657e-05 seconds)
Ack( 3, 5 ) = 253 (6.2876e-05 seconds)
Ack( 4, 0 ) = 13 (2.78e-07 seconds)
Ack( 4, 1 ) = 65533 (5.27731 seconds)

C++11 code:

//
//  main.cpp
//  Ackermann
//

#include <iostream>
#include <cstdint>
#include <chrono>

uint64_t Ack( uint64_t m, uint64_t n )
{
    return (m == 0)
               ? n + 1
               : (n == 0)
                     ? Ack( m - 1, 1 )
                     : Ack( m - 1, Ack( m, n - 1 ) );
}

int main(int argc, const char * argv[])
{
    using hires_clock_t = std::chrono::high_resolution_clock;
    using timepoint_t   = std::chrono::time_point< hires_clock_t >;
    using duration_t    = std::chrono::duration< double >;

    for( uint64_t m = 0; m < 6; m++ )
        for( uint64_t n = 0; n < 6; n++ )
        {
            // Get Ack(m, n) along with timing info
            const timepoint_t start  = hires_clock_t::now();
            const uint64_t    answer = Ack(m, n);
            const timepoint_t end    = hires_clock_t::now();


            // Display output
            const duration_t duration = end - start;

            std::cout << "Ack( " << m << ", " << n << " ) = " << answer << " (" << duration.count() << " seconds)\n";
        }

    return 0;
}

[u/Paddy3118]

In 160 different programming languages on Rosetta Code

[u/Ono-Sendai]

The video is inaccurate. Anything that can be implemented with recursion, can also be implemented with for loops and an explicitly maintained stack data structure for the function 'stack frames'. If you replace his statement with 'not computable with for-loops and a fixed amount of space' (e.g. so you can't use a growable stack data structure) then it makes more sense

[u/metaconcept]

Gah! Use a tripod, and stop fiddling with the camera!

[u/aldo_reset]

Too bad he didn't mention memoization and its benefits, which are particularly evident with the Ackerman function.

[u/kafkakafkakafka]

Great vid, thanks.

[u/zyxzevn]

You can speed up the calculation dramatically by making a large table for each Ackermann(column,row)

The only problem is that you need a very large table for larger values of M. The table gets as large as the value you get.

This is my result in a spreadsheet with 10000 rows.

Ackermann(N,M)

M=0	M=1	M=2	M=3	M=4
1	2	3	5	13
2	3	5	13	2587
3	4	7	29	8136
4	5	9	61	X
5	6	11	125	X
6	7	13	253	X
7	8	15	509	X
8	9	17	1021	X
9	10	19	2045	X
10	11	21	4093	X

Calculation time: very fast < 0.5 seconds for 10000 rows. But one needs a lot of memory for much larger values.