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.

VR Series: COMING SOON!

Please note, Ackermann is spelled incorrectly with one "n" on the title plate - Apologies

This video was filmed and edited by Sean Riley.

[steveskidude]

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

[christianherrera]

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

[keistzenon]

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.

[harrynewton]

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

[christophernugent]

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.

[d_]

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

[elias]

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

[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

[nathansmith]

I checked the size of 3 * 2 ** 65333 in python

the number itself is 280 lines in windows powershell

[NemosChannel]

"and within that VILE second argument.."

This is too funny! I like this guy.

[dalerobertson]

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

[jonorion]

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!

[Rob-Herrera]

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

[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!

[paulfletcher]

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.

[sth]

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

[polygonofficial]

this dude's voice is absolutely soothing.

[jonorion]

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

[BetrayedEnemy]

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

[nikolaglushkov]

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!