The Most Difficult Program to Compute? - Computerphile

The story of recursion continues as Professor Brailsford explains one of the most difficult programs to compute: Ackermann's function.
Professor Brailsford's programs: bit.ly/1nhKtW4
Follow Up Film from the Prof in response to this film: • Ackermann Follow Up - ...
What on Earth is Recursion?: • What on Earth is Recur...
Fibonacci Programming: • Fibonacci Programming ...
Heartbleed, Running the Code: • Heartbleed, Running th...
VR Series: COMING SOON!
Please note, Ackermann is spelled incorrectly with one "n" on the title plate - Apologies
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels

[@steveskidude]

He's could be the David Attenborough of computer science. "...And here, we observe the C++, in its natural habitat..."

[@rykehuss3435]

Nailed it

[@xplinux22]

"As you can see, this young male stack frame is prowling through the forest of dense, tangled registers calling for a mate. Alas, with the stack currently empty, his efforts are unfortunately futile." *cue safari music*

[@TampaCEO]

That's who he reminds me of!

[@douwehuysmans5959]

"but alas, the buffer overflowed and as you see can see the instruction pointer makes a miraculous jump towards the kernel"

[@JamesSpeiser]

hahaha

[@christianherrera4729]

Absolutely fascinating. I can only imagine how much more fascinating it would be if i knew what he was talking about.

[@Firestar-rm8df]

basically it's interesting if you like studying theoretical software. It's some interesting concepts, but it's utterly useless for actually writing software. This would do essentially the same thing: #include . . . double time; increase(time, time); sleep( time ); . . . double increase( double time, double temp_time) { time = pow(2, increase(time, temp_time-1); return time; } it's clunky but I'm not going to bother optimizeing and cleaning it up. it basically sleeps for 2^time!, or two raised to time factorial. Edit: at least as far as wasting cycles it would behave simularly

[@SteveUrlz]

lol, same

[@sidharthcs2110]

Christian Herrera So I'm not alone

[@Confucius_76]

yes! loved it though

[@Ligma_Male-ub1ud]

Low key just copied and pasted this into an ide I’m in CS1 , but changing my degree plan after this semester

[@harrynewton4786]

i don't alwys use recursion...but when i use recursion i don't always use recursion.

[@RKBock]

to understand recursion, you must first understand recursion

[@shadowagent3]

@@RKBock to write a recursive function you must first write a recursive function to write a recursive function

[@nandkishorenangre3541]

@@shadowagent3 To write a recursive comment some one else must add up the next recursive comment

[@JamesSpeiser]

holds beer

[@mohamedb737]

the only way to understand recursive function is to do it recursively

[@keistzenon9593]

I once tried to compute just a slightly bigger ackerman call like ack(3,3) computed in an instance and I tried ack(3,4) i think, but it exhausted the call stack. So I wrote the expansion to disk, to parse the deferred chain. The whole computation, even though it was just text, created a 10gb textfile while the slightly smaller call ack(3,3) just needed about 15lines of deferred chains. gives you a feeling of how insanely fast the output grows. This is due to the ackerman function actually abstracting hyperoperation. Where ack(3,3) was exponentiation, ack(3,4) was tetration. To put it simply: it is rasing exponentiation itself to a power. Then ack(3,5) would be even more extreme, a pentation - rasing the rasing of exponentation to a power, or just rasing tetration to a power.

[@brandenjames2408]

Keist Zenon just to blow your mind even more, pentation isnt raising tetration to a power, its raising tetration to a tetration

[@oliviapalmu5585]

So it acts like Graham's number?

[@carbrickscity]

Similar, but Graham is kinda one level above Ackermann.

[@DenisovichDev]

I wrote 3, 4 in C and it was actually instantaneous. Although 4, 4 caused a buffer overflow

[@macchiato_1881]

@@DenisovichDev he was parsing the deferred chains. You didn't so that why yours was instant.

[@d_9696]

Ack(-1, -1); ... The thread running this code has never been seen again.

[@lukitree]

Herp Derpington haha, yeah gotta add error checking in there ... #include ... assert (m >= 0 && n >= 0); ...

[@321671999]

lukitree don't use tho, use

[@OverSoft]

Herp Derpington Define the int's as uint and it'll protect you from this nonsense. :P

[@MrMiljaker]

+Herp Derpington Actually, I still think it would terminate, because once m and n get small enough, the sign bit will flip and suddenly we're back at a positive number.

[@jakubcislo8029]

Nah, it just produces StackOverflowError.

[@nathansmith3608]

I checked the size of 3 * 2 ** 65333 in python the number itself is 280 lines in windows powershell

[@EmptyKingdoms]

And it probably just filled the final lines with a bunch of zeroes because it cannot compute that large an integer.

[@dramforever]

@@EmptyKingdoms Python can

[@EmptyKingdoms]

@@dramforever using what tools?

[@dramforever]

​@@EmptyKingdoms For the purpose of explaining, consider this: In principle, you can represent a large number by its digits, and turn the multiplication with pencil and paper method ('schoolbook multiplication') into a program. It can handle anything that your computer can store. (280 lines of characters is like *nothing* compared to GBs of RAM) It won't be fast, but it shouldn't be too slow either. Now you can just start from 3 and keep multiplying by 2, which is again slow but shouldn't be unbearable. (You can even specialize and just write a 'multiply by single digit number' function) There are faster ways to do multiplication (google 'integer multiplication algorithm'), and also for exponentiation, but I'm not really familiar with those, but they are pretty well researched by others so maybe just consult what others already wrote. But actually, big integer implementations, or arbitrary precision integer implementations (look ma, no precision loss for final digits) use binary internally (bytes and words are just chunks of binary bits). 3 * 2**65533 is really neat in binary, so the real deal is converting it to decimal. Again, someone else already figured it out like ages ago. Just google 'radix conversion algorithm'. But why computers sometimes can't handle large numbers? Because really they just can't handle them *fast*. Like *real* fast. Your CPU has dedicated *hardware* circuitry to handle not too large integers and not too wild floats, so that if your program does not need 'weird' computation like computing a very large number it ends up blazingly fast, and most programs actually do just need normal numbers.

[@EmptyKingdoms]

@@dramforever thank you.

[@christophernugent8492]

Sir, thank you for this. From app engineers to web developers, I’ve always felt that it is vitally important for programmers to study the mathematical properties that make our projects work. To do otherwise, to me, is like trying to be a materials engineer without having an understanding of the physical and chemical properties of your raw materials.

[@polygonofficial1143]

this dude's voice is absolutely soothing.

[@DrZale]

Hi Professor Brailsford! I've really enjoyed all your videos, thank you for taking the time to make them. It has been a couple years for me since graduating, and I miss my senior level computer science classes. Your lectures remind me of why I got in to and love the field... and not for a day job

[@jonorion5095]

Man I sure love Professor Brailsford, I hang on every word he says. Such a great lecturing voice! Such a wise old wizard.

[@kazikmajster5650]

You know you're a true mathematician when you get scared by how big a number can get. Also makes you appreciate how big infinity actually is. It's bigger than any ack out there.

[@leeustadh2735]

any ack out there is finite, regardless of how big it is. Infinity on the other hand literally means not finite.

[@JordanMetroidManiac]

Well, infinity isn’t bigger than any number. Infinity is an undefined value, so it cannot be compared to numbers. For example, you may be tempted to say that 1/0 is infinity because division by a value extremely close to zero results in an extremely huge number, but it’s technically undefined. The reason why it’s crazy to try to comprehend the “hugeness” of infinity is only because that for any number you come up with, you can always add one to it (or do some crazy operation) and it’s even bigger. It goes from incomprehensible to even more incomprehensible. Just wanted to say that infinity isn’t comparable to numbers, but more just an undefined thing that *does not exist in the set of real numbers.* (That’s an obvious fact, but with that in mind, it should also be obvious that saying infinity is bigger than a number is just as senseless as saying infinity is smaller than a number, because they’re apples and oranges.) Moreover, since 1/x has the limit of “positive” and “negative” infinity as x approaches zero from the right and left side respectively, that should clearly indicate that there is only one infinity, and that is the state of being undefined, not existing within the set of real numbers. When 1/x shoots down toward “negative” infinity from the left and comes back down from “positive” infinity after x passes through zero, that’s the function 1/x escaping the set of real numbers to a single place, called undefined, and returning to the set of real numbers in the same direction in which it exited. That said, infinity seems like it exists on either “end” of the real number line, so that would mean it’s just as correct to say that infinity is smaller than every single number you can think of. But if that was true, then it’s a contradiction. Infinity cannot be both bigger than and smaller than every real number, and hence it does not exist on either end of the real number line. The existence of infinity is entirely outside of the set of real numbers. So, finally, infinity cannot be compared to real numbers. It’s not bigger than any ack out there. It’s just that you can construct a number arbitrarily large enough to be bigger than any ack out there, and that’s what is mind-boggling. :)

[@charlesmurtaugh3771]

“It’s longer than you think, dad!”

[@NemosChannel]

"and within that VILE second argument.." This is too funny! I like this guy.

[@jonorion5095]

Computerphile is such a wonderful treat for me, thank you so much Brady and all of your interviewees for the time and effort putting this together (numberphile as well!). You are doing a service to all mankind, you deserve a trophy!

[@robbybobby6464]

I'd love to go to any of Professor Brailford's lectures. I love his passion and knowledge!

[@paulfletcher4613]

This is amazing. I have been in computers and programming a long time, (1972) and this is new ground for me. Thanks for sharing it.

[@GanerRL]

I'm confused, you can simulate a turing machine using for loops and thus can implement ack within that?

[@elias551]

It's been 15 years I'm working professionally in computer science, writing code and doing something useful with it, thinking that I'm kind of understanding how it all works, from the theory of electronics, to the end user using it, I'm mind blown that some mathematician from the early 20s have already thought of all of this. Plus kudos to mr Brallsford explaining it like it's some basic course by its concise explaination. Love from France

[@themennissvids]

g64 is graham's number (see one of Brady's other videos). I first saw Ack(g64, g64) in an xkcd comic though. So you're looking at a number created through superexponential means, fed into a function that has a super exponential time complexity.

[@MrKastle09]

Graham's number is insane. But the most amazing thing is that the only thing bigger than Graham's Number ... is yo momma XD

[@Garbaz]

Thats gonna be fun :D It will stop calculating even before you really startet the ackerman part...

[@themennissvids]

Krisna Siv Nope, there's a thread on the xkcd forums called "My Number is Bigger!", they've found numbers that make my mother look negligible.

[@hexagonist23]

What about Ack(TREE(g64),TREE(g64))

[@shiraj2597]

Just ran into this function while going through SICP, this really helped shed some light on the topic. Thanks!

[@nikolaglushkov93]

This is so so interesting... as a computing and business student, I am really amazed and I can actually admire and appreciate all these programs and contributions made!!!! AMAZING!

[@BetrayedEnemy]

I just love that you can look at his face an see how much he loves this topic

[@billruddock]

It seems that some reductions can be made in the levels of recursion by adding cases for the following: ack(1, n) = n + 2 ack(2, n) = 2*n + 3 ack(3, n) = 1

[@KnakuanaRka]

Yeah, that’s one way to improve it.

[@Rudxain]

Another optimization is to convert one of the tail-calls into a loop, that leaves us with just 1 recursive call. But thanks to your comment I realized there's a simpler way to optimize the A function, define it in terms of a single Hyper-Operation call: A(m, n) = HyperOP(m, 2, n + 3) - 3 Where the 0th argument of HP is the degree or "order" of the HyperOP we want to use, 1st arg is what we want to hyper-operate, and 2nd arg is the number of times to apply the "sub-HP". To implement HP efficiently, define it like so: HP(0, a, b) = b++ //add 1 HP(1, a, b) = a + b HP(2, a, b) = a × b HP(3, a, b) = a ^ b //a ** b The general case HP(n, a, b) requires recursion, it can be an implicit or explicit stack. It's essentially HP(n - 1, a, HP(n - 1, a, ...)), with b copies of HP calls, IIRC. HP(4, a, b) is tetration, HP(5, a, b) is pentation, etc... Before I realized this optimization, I just used the Wikipedia table with all closed-form expressions that didn't require recursion, and used a memoization hash table when recursion was needed. After implementing the HP optimization I realized Wikipedia already mentioned that in the "Definition" section, but I didn't understand the notation before... *bruh*

[@UNKNOWNKINGTHEGAMER]

try 4,4

[@TheALPHA1550]

Ah, nothing like theoretical computer science.

[@bangpaf2328]

9:45 I reproduced the function in Python and believe I got it right as it gives me the same results, except for ack(4, 1): _"RecursionError: maximum recursion depth exceeded while calling a Python object"_ lulz at Python

[@tombeaudry3143]

Python, please.

[@SonnyGhosh]

use like Java, c#, c++, etc

[@kraemer-raimund]

You can change the recursion limit in Python.

[@bangpaf2328]

Thanks for the replies. I guess I should have known, I'm still pretty wet behind the ears when it comes to programming.

[@thomaspappas8946]

+Raimund yes but how?

[@sth128]

It'd be funny if the program returned -1/12.

[@CircusBamse]

unfortunately it has to be an integer and -1/12 is not so something would've gone wrong, but I do like your thinking though.

[@son-tchori7085]

Minox sta Some would argue that summing natural integers to infinity would be integer as well... : kzbin.info/www/bejne/rV6sZ4uKi7-Lrdk

[@kevinmichelet91]

Minox sta summing positive integers is not supposed to be negative. But 1 + 2 + 3 + 4 + 5 + ... = -1/12 (see numberphile) So if string theory can incorporate that, why not ?

[@Falcrist]

You only get -1/12 if you go all the way to infinity. Whatever stupendous number it puts out will be just as far from infinity as 1.

[@cemerson]

Minox sta But adding all the natural numbers must be an integer, right?

[@loupax]

All the cores in the world won't help you since this C code will run in a single thread. Also the first thing I thought was "wouldn't memoisation help improve performance?" After a quick google search, I discovered that "When a software developer learns about the Ackermann function, he will try to see how much of improvement function memoisation does if any". LOL

[@HebaruSan]

How much is it?

[@lagduck2209]

HebaruSan probably at least some, if any

[@SwissSareth]

Funnily true ...

[@sayven]

can confirm lol

[@suave319]

I want Professor Brailsford as my lecturer. He's awesome :D

[@hamza3838]

Suave Atore wait is that his name? THATS SUCH A COOL NAME

[@dalerobertson4662]

The only regret I have in my life is learning this late in my life, from Professor Brailsford's and rightly so, and so lucky I am. What an honor to stand on the shoulders of the masters of the computer coding & math sciences resident in my grandfather's home country. Thank you all at Computerphile. Cheers... Dale Robertson professional student. College of Marin

[@NikolajLepka]

You could try writing a memoized version of this code, where it remembers the result of a previous computation, and just plops that result in so it won't have to spend time working that out, cuz it seems to me that that's what's slowing it down so much; that it has to go through the same set of computations again and again EDIT: PEOPLE before commenting on why it wouldn't work; please read the other comments! THEY MAY ALREADY HAVE COME TO THE SAME CONCLUSION! Please don't waste precious keystrokes on repeated information, thank you

[@Poldovico]

But I wanted to know why they didn't, and the comments you refer to aren't on the first page anymore D:

[@greenya84]

This i called "Dynamic programming" :)

[@NikolajLepka]

Yuriy Grinevich do your research, memoization has its differences

[@MartinFracker]

Yuriy Grinevich Memoization is a technique that can be involved in dynamic programming.

[@hdpasd123lol]

Nikolaj Lepka As far as I know your approach is known as " backtracking " , so for the people saying it wont work , it will. It will indeed make it faster.

[@WorldOfDeepThought]

Would ack(m-1,ack(m-1,ack(m,n-1))) still be superexponential or would it have an even bigger growth?

[@dplameras]

I love listening to Professor Brailsford because it makes me realise, that I'm not that smart and there are so many more interesting things to learn.

[@Omarbistami]

i wish i had professor like that in morocco... the passion you talk about the subject give motivation and make me love more computer science :)

[@repairtech9717]

Most of us in the UK where he teaches wish we had a professor like this as well. He comes from a very elite university that most dont have the money to pay for. A quote from the wikipedia for the UON says "Nottingham has about 45,500 students and 7,000 staff, and had an income of £694 million in 2021"

[@herp_derpingson]

Ackerman(4,2) is equal to 42 :)

[@TH3MIN3R3000]

Herp Derpingson if only, if only...

[@themodernshoe2466]

This guy has great personality!

[@MisterFanwank]

Is there any significance behind 65533 almost being 2^16? Or is that just a coincidence?

This was mindblowingly amazing, thanks!

[@nand3kudasai]

the result will probably be 42

[@fuppetti]

Jerónimo Barraco Mármol ack(ack(life, universe),ack(everything, douglasadams))

[@truthseeker7497]

+Jerónimo Barraco Mármol A distinct possibility. What was the question?

[@nand3kudasai]

+Dan Overlin To know the question we would need a computer and an algorithm far more complicated. It would probably take ten million years to know.

[@truthseeker7497]

Another 5 minutes and we would have had the answer . . . damn the Vagons! The best laid plans of mice . . .

[@blinky840]

I would give you an upvote but you are already at 42 and I would hate to ruin that.

[@SteveGouldinSpain]

I've been jobbing business focused programmer for over thirty years. I was at college recursion was kind of worshiped by my tutors 'oh look at the elegant code' they would say. When I got in to the business world the number of times recursion was the best solution was about twice in thirty years!

[@BlackMambo]

Brilliant...!

[@djdedan]

u guys never sorted anything? i would assume most sort functions are recursive (of course i could be totally wrong - but then again i could be totally right!)? Or do you mean you never had to write any recursive code?

[@SteveGouldinSpain]

Strangely no because whenever I've had data it's been inside a database, so you get the database to sort the data before you get the data out. Or if you get it into a webpage then use methods from a library like jQuery datatables to handle the sorting for you. I've never needed to get my hands dirty sorting. Infact I remeber doing all that sorting stuff at college level and pretty much never having to use it like I never used truth tables or Karnough maps!

[@djdedan]

Steve Gould haha yeah - it's the curse (?) of software engineering, learn the nuts and bolts but unless you plan to be an expert on, say sorting, you are better off using someone else's sorting routines - so why learn the nuts and bolts in the 1st place. My answer would be: for job interviews! lol! cheers!

[@SteveGouldinSpain]

Spot on DjDedan and in fact some the most successful 'programmers' I know hardly write a line of code. They are just very good a cobbling together solutions from other people's work.

[@samre3006]

Such a nice voice to listen to. And extremely interesting topics.

[@Cross31415]

I have barely the slightest idea of what is going on in the "guts" of this, but i just really enjoy professor Brailsford talking about it. So thanks, professor!

[@philronan6929]

His computer's a bit slow. I compiled his function pretty much verbatim, and it calculates ack(4,1) in 27 seconds. With optimized compilation, it only takes 5.7 seconds. I don't think I'll bother calculating ack(4,2) though...

[@Computerphile]

***** suggest you watch the follow-on video :) >Sean

[@philronan6929]

***** Ah. That explains it!

[@idanguttsait]

+DaKnOb That is true. I had a StackOverflow on 4,1

[@moveaxebx]

+Giora Guttsait Try with any functional PL (supports tail call optimization)

[@drobilla]

+moveaxebx The Ackermann function is not tail recursive. That is essentially what the professor is explaining. Tail call optimization is, in a sense, converting a recursion into a for loop (making it iterative), and you can not do this for functions like ack.

[@slugfiller]

The thing that makes the Ackermann function irreducible is that the amount of unique (m,n) pairs you need to computer is actually greater than the Ackermann number at (m,n-1). So even if you were trying to compute bottom to top, while it might be more efficient than the naive implementation (no pair calculated twice), it would still require a very large run time, and also require a great deal of memory as well.

[@1JWL]

Lovely presentation. I really enjoyed the final part... great humour.

[@heroicalx786]

thanks! your way of explaining Ackermann's function is so clear and enthusiastic. great gift!

[@kenneth_romero]

I love computerphile, wish I found out about them when I was in middle or highschool to explore computer science sooner rather than in college.

[@weeeeee831]

I love this guy

[@oossgl]

That voice is really calming and confortable, ideal for teaching!!! :)

[@kimsung2384]

I love listening to this guy .... totally inspiring

[@HackingWithTheLeviathan]

You use openSUSE! Me too! ^_^ And I had the Ackermann function in a lecture at ETH Zürich! Keep on doing these videos! :D

[@yramagicman675]

I downloaded the program files and ran ack(6,6) on my quad core 3.2 ghz machine running Arch Linux. It used 100% of one of my cores, took 1 minute 45 seconds, and ended in a segmentation fault. ack(4,4) also segfaults. ack(3,3) returns in under a second.

[@TheThunderSpirit]

Hi... plz tell me the time complexity of this func. how can we even calculate that. what about space complexity.

[@fidalgoverde]

Beautiful Masterpiece

[@alaamroue]

ack(tree(3), graham's number)

[@ChristopherKing288]

7

[@pranamd1]

[@abcdefzhij]

The salad is strong in this one. You are already at the magnitude of TREE(3), doing an ackermann function (which is EXTREMELY weak by comparison) won't really do anything.

[@zokalyx]

42

[@carbrickscity]

The TREE function is way stronger than the Ackermann function. However, the follow-up video of this video was about a function even stronger than the TREE function - the Busy Beaver function.

[@Niosus]

Would caching make this function more computable? By remembering old results you do not need to recalculate them. Since it only calls the function with reduced arguments, it doesn't seem that hard to build your way up? I am probably missing something :P

[@ernhamDjinn]

ack(4,2) will access ack(3, 65k), value that was never computed before, which itself will access ack(2, insanely_large_value), and so on.

[@armoredmind-gr2298]

Nope . Thats memorization for recursion . That's not the problem in this case

[@mainmast8955]

ur onto something

[@evanamavrin5308]

OpenSUSE linux in the background! Love that distro.

[@williamwinner4234]

I had to use recursion on my sediment loading model. For my model it took a DEM and other layers and need to work up a river to measure sediment loss and sediment delivery. So I worked from the origin cell and looked for neighbor cells that fell upriver. So I had to look recursively at each cell until we were at the highest cells and then work downriver. I guess you could do it with a with loop and several for loops but it would take forever.

[@hzenilc]

The most important question remained unanswered! Why the Ackermann function cannot be put in for loops! A sketch of the proof would be fantastic for Prof. Brailsford to answer given his great teaching skills, maybe for a next Computerphile episode! For people it may look like you only need to write a program that keeps nesting for loops to calculate Ackermann's. Best and great series!

[@profdaveb6384]

Essentially, using recursion is a way of dynamically nesting "for" loops by virtue of your chosen programming language creating *dynamically* as many stack frames as are needed..There is in principle no limit except that, as the stack grows huge, you will eventually run out of memory, The problem with static for loops, explicitly written into your program, is that every compiler will put a compile-time limit on how deeply nested they may be.

[@paulpinecone2464]

Ok, so to go half way there, make a language structure that takes an array of triples which specify the set of nested loops and a pointer to a function to call inside that is passed a state array of the current values of all the loop variables. Several challenge levels: 1) The array is static, ie, it is just shorthand for writing out all the loops. The compiler or preprocessor can generate them. 2) The array is dynamic but contains constants. Ie, the loop system is known at the start of it and can be allocated as a static data structure. 3) The dynamic array can contain algebraic expressions which need to be evaluated to determine loop criteria. Ie, the structure is known at the start but the loop limited can vary. 4) The array is returned by a function which itself can contain functions to define what the substructure of loops will be at each level. I believe this is called recursion and is no longer a language feature.

[@kylek.3689]

Because of one of the definitions of the Ackerman function, where A(m+1,n+1) = A(m, A(m+1, n)) This means the loop depth of the Ackerman function relies on M, and you'd have to give one for loop to case m=1, two loops for case m=2, three for loops for case m=3, and so on. Though, this is without using a heap allocated stack to imitate a function call stack.

[@robertkelleher1850]

Fantastic explanation. The bit about the big crunch didn't age well, but otherwise... just magic.

[@amihartz]

The reliability of the view that the expansion of the universe is speeding up is exaggerated. The Nobel Prize was awarded prior to their data being made public, and when it finally was made public recently there have been tons of papers criticizing it, both in methodology and by using more data from more modern telescopes.

[@ICoulntThinkofAUserNam547]

This guy is amazing, so fun to watch

[@creative-freedom]

@computerphile : Thanks for the awesome videos. I am a huge fan. Can you guys please do a video on Dynamics programming?

[@GrooveFederation]

God i wish we had teachers like you guys back when i was at school, i might have actually learned something more than whether tom crosses the road with sally or jill. I wanna go back and absorb all this glorious input, but since creating a time machine isn't on my to do list i think i'll just watch more of these videos. Imho this channel, your numberphile channel and the PBS space time channel are the best places for input on youtube, keep it up fellas it's well appreciated.

[@PhilipBlignaut]

Great choice of videos subs!!

[@mainmast8955]

it may be time for you/us numerical freaks to push forward.

[@WaterCrane]

The Ackermann function, while useless as a piece of software, it is very useful as a theoretical case study, especially in regards to writing compilers and optimizers. The Ackermann function is, by all standards, a pure function, in that its output is deterministic and relies only on its input arguments and nothing else. What that means is that if you call it with constant actual parameters, say, x = ack(4,1), in your code somewhere, the compiler can pre-compute the result and change it to x = 65533 internally so you don't have to execute it in the compiled program. The case study comes about where you decide at what point the compiler should give up trying to pre-compute it and just leave the function call as it is, otherwise the program will never compile.

[@brendawilliams8062]

Like 41666….↗️

[@TheShouldoos]

This channel is so awesome.

[@Manachtron]

Wow, that escalated quickly, Mr. Ackermann!

[@raditzan]

Ermagherd that lack of indentation is driving me crazy!!

[@eliatarasoff5872]

Agreed. That code would be sooo much easier to read if it were indented! This is like...Computers 101 stuff! ^^;

[@miciduve]

@@eliatarasoff5872 ermagherd someone learned with python didnt they

[@The2bdkid]

I compiled the same code and I'm getting different numbers.. then it crashes at ack(4,1).

[@DJRosted]

I think I have some vague idea what he's talking about but but probably I'm totally wrong. I love his dramaticness of code going wrong so that keeps me listening.

[@jiripodivin5409]

Simply beautiful.

[@Wouter10123]

I noticed that all those numbers are very close to a power of two, in fact, starting at ackerman(2,5) they're all 2^p - 3 for some p. Is there a pattern to this?

[@vekyll]

Yes. You should at least read Wikipedia. :-) If you want to know more, including the motivation for the original Ackermann function, just message me.

[@abhayshankar8762]

yeah. try doing it by hand - you wont get the exact numbers, obviously, but you will get those power tower representations of them.mind you, once you see it, you cant unsee it.

[@Ozzah]

That's not at all what superexponential means in the context of computational complexity. In the context of computational complexity theory, anything superexponential is anything with a time complexity (or space complexity) greater than O(c^n), where c is a constant and n is the problem size. For example, the factorial function is superexponential. There are a lot of problems that have factorial complexity, for example in combinatorial optimisation.

[@Lition98]

the time for computation blew my mind as same as the hanoi tower, this is astonishing

[@PauloAbreu]

Mind boggling! Great video!

[@stevepittman3770]

After breaking various online 'big number calculators' I found one that works, and it turns out 2^65533 * 3 minutes rounds out to, unless I've screwed up somewhere, about 1x10^19712 times the age of the universe. Not terribly helpful. (((((2^65533 * 3) / 60) / 24) / 365) / 13700000000) = 1.0434008320186794 × 10^19712

[@KnakuanaRka]

If you want help with big powers like that, try making logarithms of everything; multiplying and dividing stuff like that turns into adding and subtracting more manageable numbers.

[@xybersurfer]

i bet it can worked out in a loop with the use of some kind of list

[@seandavidniemann4563]

Fabulous video. Pretty interesting stuff

[@tceffect2353]

I noticed that they used K&R style C declarations in their code. They declared main as int main(argc, argv) int argc; char ** argv; { //code } K&R style C declarations used to be much more common before C89, but are mostly unused these days. Though they are only some declarations involving VLAs where only K&R style declarations are possible.

[@vakabus]

I think there is a rule. Results after ack(3,0) are always (as far as I know) powers of 2 minus 3. Is there a PROVED rule?

[@matthewsaulsbury3011]

I don't know. That's cool that they are powers of 2 minus 3! 👍 I like powers of 2. The Ack(4,1) value of 65,533 is 3 less than 2^16. 😀 These are amazing and intriguing things on this video!

[@TehBleuBelly]

Counted the number of recursions required to calculate ack(4, 1) and the result was 2, 862, 984, 010. Mind boggling...

[@KnakuanaRka]

Y2K38 How do you calculate that? Is that its own recursive function?

[@abhineetsingh1291]

In the recursive function create a static variable and increase every time for a recursive call

[@KnakuanaRka]

abhineet singh Makes sense.

[@ismailelgaabouri2016]

One's of the greatest professors if it isn't the great, even if the video topic is kind of hard to be comprehensible but within his abilities of clarifying, things can be well understood. Ps. We still want to know why we cannot use for loops for ackman function.

[@stefanobaghino]

Thanks for the video! How did you make the function stack-safe? From the implementation I could have imagined it to fill up the stack in a few thousand iterations.

[@zack3g]

it isn't, at least on python in linux. I found this and have been tinkering with it. recursion limit errors start showing up around 3,4. It's possible to increase these of course but 16 gigs of ram and 32 gigs of swap space wasn't enough to do 4,4. And this is with memoization...well, the functools cache decorator anyway. Poor man's memoization :D

[@zackinator1439]

I think the answer '42' from Hitchhiker's Guide to The Galaxy may be a result of a call of ackerman. Now the question is what were m and n?

[@furbyfubar]

That's an easy but not a very interesting call since: ack(0,41) = 42

[@Dmirtao]

If anyone remembers Knuth's arrow notation from Numberphile's video on Graham's number, it is worth noting that Ackermann's function can be represented in arrow notation as well. If we define an arrow operation: 2 {↑^m} n, then that is identical to ack(m+2,n-3) + 3 So, inversely, if we have ack(m,n) we can write its arrow notation as: 2 {↑^m-2} [n+3] - 3 So, as in the video, if we have ack(3,1) = 2{↑^1}4 - 3 Which is 2^4 - 3 = 16 - 3 = 13, same as in the video. (Note that this method only easily works, though, for m > 2, otherwise you have no arrow operator.) So really ack(4,2) may be *uncomputable*, but it can be mathematically represented as 2{↑^2}5 - 3 with these hyperexponentiation operators. If you want to know what ack(4,2) is exactly, well, the best estimates put it approximately at: 2*10^19728 OR 10^10^4.295 So, yes, far bigger than universal timescales or particle numbers. ^_^ en.wikipedia.org/wiki/Knuth's_up-arrow_notation has some more information. Love the videos!

[@sgipower]

by the way, really interesting, would love a video about dynamic programming by prof Brailsford

[@alejandrocantu1811]

This guy just makes me so happy

[@blingkid00]

i believe that for loops and recursion are only needed when working with indexes and such. but not when doing math... there is always an equation. that will do it next to instantly.

[@Ozzah]

steven johnston No. Elementary functions can be defined recursively and there is no closed for solution to them. Some functions are defined as infinite sums of basis functions. Most differential equations have no closed for solutions and must be solved numerically. In all these cases, loops or recursions are absolutely necessary. And it's definitely not true that it can be computed instantly. I currently have 3 computers working for almost a month on one problem ;)

[@jervey123]

wuuut? i disagree math is all about recursion... the simplest of elements in math revolve around recursion like say counting but before we can count we have to define natural numbers; how do you define a number? well a number is either zero or the increment of a number, so you can practically create a function called "number 5" which is just inc^5(zero), see? recursion

[@terjeoseberg990]

@7:05 he claims, "But what I would like to draw your attention to, because this is important, is that every time M and N are altered, they are reduced." This statement is wrong. @9:50, you can see that ackerman(m,n) is always greater than both m and n. Because the code contains, "ans = ack(m-1, ack(m,n-1))" whenever neither m nor n are 0, n in fact increases. It might be better to say m always either stays the same and n decreases, or whenever n increases m decreases. Eventually when m reaches 0, an answer is produced immediately.

[@KnakuanaRka]

Terje Oseberg Yeah, that’s a whoopsie.

[@pvic6959]

i see an issue in the second line as well if n=0, the answer is ack(m-1,1). The second argument (n) is back to 1 even if it was 0 before. whcih will make it keep going.

[@KnakuanaRka]

pvic However, m decreases during the call; basically, as you do recursive calls, n decreases to 0, then m decreases as n increases, then n runs down to 0 again, then m decreases again as n is reset, and so on, so m will become 0 eventually, causing the calls to stop recursing. It will take a VERY long time, since n will increase by a crazy amount each time m decreases, but it will run out eventually.

[@mohammadshahabrafiq]

Fantastic video. Professor Brailsford is awesome. ❤

[@BryonLape]

I realize this video is nearly 4 years old and the chances of comments not seen are great, but does anyone know about how the code was compiled and run? I wrote an ANSI C version of the code shown on an Ubuntu machine and within minutes it returns a segmentation fault when computing 4,2, let alone running it for how long is claimed in the video. This was compiled with gcc, but with all default values.

[@Ezechielpitau]

one question about this: when I wrote this in python I got an error that more than 1000 recursive calls is not possible. While this might be different in other programming languages I'm a bit baffled that this can run for four weeks on their computer and not lead to some memory problem... Cause isn't the thing about recursiveness that we need absurd amounts of memory?

[@MrPoutsesMple]

+Ezechielpitau I think you can override this python recursive call barrier somehow.

[@carnaedy]

+Ezechielpitau > " isn't the thing about recursiveness that we need absurd amounts of memory?" Tail-call optimization completely eliminates the memory problem, if the programmer makes an effort to lay out the function in a certain way.

[@Ezechielpitau]

+Paulina Jonušaitė ah ok thx, I'll have a look into how that works :)

[@techmage89]

+Paulina Jonušaitė I believe that will only work for primitive recursive functions. In this case, one branch has a recursive call that cannot be unrolled.

[@philipsalter934]

g64 is grahams number (MUUUCH bigger than a googleplex). see numberphiles video: Graham's Number - Numberphile

[@AaronHollander314]

TREE(3)

[@PrimusProductions]

Given a constant value for m or n, can we plot the Ackerman function on a graph (as discrete points)? what would it look like?

[@DahBlindNinja]

Well it's not an iteration function, so not really. But you could graph the results of all calls to the equation, but I don't think that's quite what you had in mind.

[@PrimusProductions]

On three axis, x y and z Do they form a coherent surface and like how factorial can be generalized with the gamma function, can Ackerman be extended?

[@JohnDlugosz]

My experience with that function is to exceed the stack space of the machine. Where did you get a compiler to take the antique C dialect?

[@pauljmorton]

Nice, I tried the function myself before he started showing his results and I thought I did something wrong because it seemed to get stuck at ack(4,1). But apparently it's just so tough to compute.

[@Boris99999]

I remember when in school we were making the program that solved the “Hanoi tower” problem and then we made a fractal tree that was moving in the wind - it was so beautiful! Since that day I fell in love with recursions and fractals!

[@darkangel2347]

For small specific values of m and variable n, we have ack(1, n) = n+2, ack(2,n) = 2n+3 and ack(3,n) = 2^(n+3)-3. We can see from this that ack(4,n) is extremely hard to compute.

[@ArthurBi]

What if we could just use smaller fuction results to skip some calculations? For example. if we use ack(200,200) and if ackerman (3,4) appears at some point, we just use already sorted answer?

[@greg55666]

I have a different idea--what if we remembered the results of every call, so we could look them up in a table rather than recalculating? Would that simplify the problem? Somewhat at least. We are calling ack with the same values over and over. But is it enough? Interesting. By remembering the previous values, my program is able to calculate ack(4,1) instantaneously as 65,533. So remembering the previous values does simplify the problem, but I still get a stack error before I get to ack(4,2). Here's a question. Since there is an obvious pattern to the answers, what if we just rewrite ack to return the value? Is that possible? Or is recursion still necessary in order to calculate the n^n . . . ^n . . . ^n?

[@jayeisenhardt1337]

Yeah I was thinking of turning this into a math problem to look for shortcuts for 10,10. Maybe if they understood the math it can be written easier. Then you only have a fraction of the work to do.

[@douplofigure]

As this problem is computable via µ-recursion, it is also computable by while-loops, this may speed your calculation up. For the problem of n^n^...^n^n (a power-tower) this can actualy be done with for-loops or primitive recursion, so the computational time is not that bad: In Python: def pt(x, y): n = x for i in range(y): n = x ** n return n The main problem here is that the numbers also become quite huge and may not fit into memory.

[@ianzen]

Nothing will help speed up the computation, the simple fact of reading and adding two intermediate values take too long.

[@aMulliganStew]

You've discussed algorithms that are necessarily recursive. Given that multi-cores and threads are now mainstream, I wonder if there are any algorithms that are necessarily parallel.

[@jirihavel9766]

+aMulliganStew No, you can always serialize it by interleaving instructions from different threads.

[@jonathanpark4619]

+Jiří Havel That's still parallelization.

[@jirihavel9766]

Jonathan Park I meant that you can always emulate a parallel machine on a serial one. This means that there are no problems that are solvable by parallel but not by serial one.

[@jonathanpark4619]

Unless you're executing the threads in a serial manner, that's still parallelization.

[@jirihavel9766]

Jonathan Park You can call it this way. I answered to "I wonder if there are any algorithms that are necessarily parallel." And since you can convert any parallel algorithm to a serial one (even if that means emulating some parallel machine), then parallel algorithms can't solve any problem that a serial algorithm can't.

[@LazZanZaz]

The program in the description (link) is missing a semicolon in the printf line... I learned how to detect those the hard way Great video as always prof!

[@Tsskyx]

I tried it by hand. This is another one of those problems with a simple setup but complex results. I know this is called P != NP or something like that, but idk what that means.