Escuro

The Most Difficult Program to Compute? - Computerphile

Computerphile
Inscrever-se
Visualizações 1 072 313
98% 17 414 209

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: brvid.net/video/video-uNACwX-O5lk.html
What on Earth is Recursion?: brvid.net/video/video-Mv9NEXX1VHc.html
Fibonacci Programming: brvid.net/video/video-7t_pTlH9HwA.html
Heartbleed, Running the Code: brvid.net/video/video-1dOCHwf8zVQ.html
VR Series: COMING SOON!
Please note, Ackermann is spelled incorrectly with one "n" on the title plate - Apologies
facebook.com/computerphile
twitter.com/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

Publicado em

 

1 Jul 2014

Compartilhar:

Compartilhar:

Baixar vídeos:

Carregando o link.....

Adicionar a:

Minha playlist
Assista mais tarde
Comentários 1 900
Samuel Ferrer
Samuel Ferrer 6 dias atrás
Yes, you can do it iteratively by using a stack ... explicitly ...
AsBi
AsBi 12 dias atrás
That's why I love mathematics
sneekmatrix
sneekmatrix 12 dias atrás
Can quantum computers scale the problem to being resolved within a reasonable time?
Tanner Barcelos
Tanner Barcelos 13 dias atrás
Gotta order a new Computer after trying this one
Cyber23Analyzer579
Cyber23Analyzer579 15 dias atrás
I like Mr. Brailsford. Very sympathetic.
Faustin Gashakamba
Faustin Gashakamba 18 dias atrás
Computer scientists before computers were invented?
Y2K38
Y2K38 21 dia atrás
Counted the number of recursions required to calculate ack(4, 1) and the result was 2, 862, 984, 010. Mind boggling...
Michael Baron
Michael Baron 23 dias atrás
I think it's called Ackermann function because it grows almost as fast as the debts of the "Deutsche Bank" 😂😂😂
Arun Sasi
Arun Sasi 23 dias atrás
why not return n+2 for a faster result?
Ahmed Azhad
Ahmed Azhad 24 dias atrás
65533 is suspiciously close to a power of 2 - 65535 . hmm. is it a program error / overflow already?
thinbox dictator
thinbox dictator 21 dia atrás
when m == 3, result = 2^(m+n) - m ack(4,1) = 65533 ack(4,2) = ack(3,ack(4,1)) = ack(3,65533) = 2^(3+65533)-3
Jamien
Jamien 24 dias atrás
2^65536 minutes is close enough to 10^19000 years. Unfortunately, that's long enough that all the protons in existence will have decayed and that poor CPU will cease to exist.
Sander Bouwhuis
Sander Bouwhuis 26 dias atrás
At 11:50 you say that the number of seconds since the big bang is about 2^500. What?!? log2(13800000000 * 365.2425 * 24 * 60 * 60) ≈ 58.595
Борис
Борис 29 dias atrás
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!
Arcsecant
Arcsecant Mês atrás
You can speed things up considerably if you relax the condition of correctness.
Anonimo Oculto
Anonimo Oculto Mês atrás
4:25 OpenSUSE. Great distro. I use it, version 13.2 , perfectly working nowadays, 01-15-2020, since its release; with firefox 72.0.1 manually installed.
thinbox dictator
thinbox dictator Mês atrás
linux FTW btw I use arch :p
Noneof Yourbeeswax
Noneof Yourbeeswax Mês atrás
9:20 It would be faster to put the printf statement inside the function if you want to test it. That way you avoid wasting computations by taking advantage of the fact that computaions of ackermanns fuunction include computations of ackermanns function with lower arguments.
thinbox dictator
thinbox dictator Mês atrás
ok. I have solution for ack(4,2) I tried paste here the number, but youtube for some reason doesn't like that simple python function (modified ack) : def ack(m,n): if m < 2: return n + m + 1 if m == 3: return 2**(3+n) - 3 if n == 0: return ack(m-1,1) return ack(m-1,ack(m,n-1)) ### yes, if m == 2 ,then return 2*(n +1) +1 is possible to hardcode too, but 2 isn't problematic here :p so, for nonprogrammers: I noticed that when m == 3, result = 2^(m+n) - m we know ack(4,1) = 65533 and we know ack(4,2) = ack(3,ack(4,1)) so ack(4,2) = ack(3,65533) now m == 3 and we know equation for it ack(3,65533) = 2^(3+65533) - 3 *ack(4,2) = ack(3,65533) = 2^65536 - 3* 19729 digits I can tell you it starts 2003529930406846464979072351560255750447825475569751419265016.... and ends ...39445587895905719156733 but unfortunately,as I said, youtube doesn't want you to know all digits. edit : when I tried to ask my PC what 2^(2^65536) -3 is (that should be ack(4,3) ), it stopped talking to me.... but it looks like there is another pattern :p when m = 4
thinbox dictator
thinbox dictator Mês atrás
nevermind, I just checked wikipedia... this is no big deal
thinbox dictator
thinbox dictator Mês atrás
you can follow all ack when m == 4 from it :)
Arthur O'Brien
Arthur O'Brien Mês atrás
Me: This sounds like Gödel. Professor: Gödel! Me: Ha, I was onto you the whole time!
Poornapragna Vadiraj
r/iamverysmart
DJRosted
DJRosted Mês atrás
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.
Komagb
Komagb Mês atrás
But his computer is "slow", so is this computable on the fastest super computer on earth? Or on some huge network?
Aged P
Aged P Mês atrás
It's not an algorithm that you can set up in parallel. The supercomputer might turn the 3 minutes into 1 minute but you're not going to alter the factor of 2**65333 term that takes the time so high.
Jaekoff
Jaekoff Mês atrás
So what’s recursion?
sp10sn
sp10sn Mês atrás
Greatest, undecidable problem: "what's in my pocket?"
MW
MW 2 meses atrás
Before he explained the nature of the algorithm, I paused the video and ran it myself. I was fascinated to discover that ack(4,2) resolves not to a number but to several dozen pages of the phrase "Stack Overflow Error".
thinbox dictator
thinbox dictator Mês atrás
I just solved it :p bit of cheating (didn't use default ack), but done I know, cheating is bad, but I wanted to know that value of ack(4,2) .
appletime101
appletime101 2 meses atrás
Do you know of any papers illustrating the power of representing recursion interactively with stacks like modern programming languages do
Roach DoggJR
Roach DoggJR 2 meses atrás
The answer to the universe is the result of ack(g64, g64).
lorecast162
lorecast162 2 meses atrás
After a while after it did ack(4,1) it just threw a segmentation fault. Ran it on a 4690K OCed to about 4.2GHz
Temm
Temm 2 meses atrás
Hackerman
OK BOOMER
OK BOOMER 2 meses atrás
now, that's content!
Yoo Won-Hye
Yoo Won-Hye 2 meses atrás
When you're born with intelligence and a talent in speech.
Simon Newman
Simon Newman 3 meses atrás
Some things are just easier to work out with pen and paper. Took me a while and got through quite a lot of paper and pens, but the answer to ack(4, 2) is 378163771, which if you type in on a calculator and turn upside down spells 'ILLEGIBLE'. Probably have a crack at ack(4,3) later if Staples deliver my order in time.
FalcoGer
FalcoGer 3 meses atrás
Have you ever heard of indentation?
Trevor Reed Studios
Trevor Reed Studios 3 meses atrás
This is gripping.
GiM
GiM 3 meses atrás
ack(ack(tree(g64), tree(g64)), ack(tree(g64), tree(g64))
Xnoob Speakable
Xnoob Speakable 3 meses atrás
14:02 well... i gues my calculations were pointless
Xnoob Speakable
Xnoob Speakable 3 meses atrás
Around 10^19722 years to figure out the ackermann(4,2)
Xnoob Speakable
Xnoob Speakable Mês atrás
@Sareth r/technicallythetruth
thinbox dictator
thinbox dictator Mês atrás
done aaaand done. thank you :p
Sareth
Sareth Mês atrás
Blimey, that's over three days!
Xnoob Speakable
Xnoob Speakable 3 meses atrás
3×2^65533 = 7.513237×10^19727
brinbrin62 62200
brinbrin62 62200 3 meses atrás
Let's go with tree() and Graham numbers.
Hermann Fegelein
Hermann Fegelein 3 meses atrás
Doesn't this disagree with the Universal Approximation Theorem? According to that, there is a neural net that can approximate the Ackerman function, and neural nets are not recursive
Torres.etechprog
Torres.etechprog 3 meses atrás
Had to restart my phone because i tried to run this program on my Sololearn compiler
Omar Morales Rivera
Omar Morales Rivera 3 meses atrás
Time to try this on python and run it on a friend's cellphone :v Sounds like a great way to push the processor to the limit and basically fry it
Charr
Charr 3 meses atrás
Ack(g64, g64), oh please. TREE(Ack(g64, g64)). How's THAT for gigantic numbers!
Mark W
Mark W 3 meses atrás
Have you tried his program?
Rob L
Rob L 4 meses atrás
Wrote multi-threaded version in C# on x64 Windows i9 3.6GHz (16 simultaneous threads, was at 99% CPU, now dropped to 79%... now 70% as I type this??). Got 5,0 and 4,1 in parallel after 23 seconds. There are just somethings you gotta do. I'll leave it overnight. At least it will warm up my lounge ;)
Daniel Martinez Bonilla
For this type of functions dynamic programing comes really handy, so you stop recalculating stuff over and over again, my dynamic ackerman implementation managed to solve arguments of double digits quite easy.
illusions77
illusions77 4 meses atrás
Sum functions are meant to be recursive in nature till the plug is pulled and death 💀.
Ion CASU
Ion CASU 4 meses atrás
while(!bigCrunch)
J. Az. Woods
J. Az. Woods 5 meses atrás
Simplest Recursively innumerable function: Function Jfunc(n): while True: pass return n Where do I get my fields medal?
Pokemoneuro
Pokemoneuro 5 meses atrás
I want this type of function done on a quantum computer,
John von Horn
John von Horn 5 meses atrás
Could we turbo Ackermann by using a lookup table of previously computed results?
John von Horn
John von Horn 5 meses atrás
Bet von Neumann could calculate Ackermann(100,100) in his head
This Is a name
This Is a name 5 meses atrás
So what would happen if you did this on a quantum computer?
CR Anish Chelliah
CR Anish Chelliah 5 meses atrás
Techically speaking all recursion is carried out by implementing a recursion stack hence you could use a for loop to implement any kind of recursion. Hence Ackermann's function too could be return using only for looops.
Pratik Maitra
Pratik Maitra 5 meses atrás
If my understanding is correct he is not talking about a for loop in the general sense but rather the inability to get a random ackerman number given a set of previously solved ackerman numbers in a reasonable timeframe as we do not know how long to run the for loop. In other words we cannot get a n upper bound for ackerman numbers. For eg we can get fibonacci number to get the 1000th fibonacci we can use a for loop that runs for 1000 iterations but otoh for ackerman numbers we are unsure what iterations ack(1000,2) will take.
jeffreyfuhz
jeffreyfuhz 5 meses atrás
i'm struggling to understand the program texts he printed out.
D Scheme
D Scheme 6 meses atrás
Fascinating
Zac Meyers
Zac Meyers 6 meses atrás
I'd be interested in you view of divide by 0 and the phenom that follows
TheRubyMoon
TheRubyMoon 6 meses atrás
Welcome to the Million View Club!
donotoperatewhileangryisagainstracist
can you use decimal answers in ackermans function to reduce the calculation and get an estimate of what it would normally be or does that actually make it harder or could you at least add a zero to the code so it subtracts 10 instead of 1 and write the code normally but I guess that wouldnt reduce the complexity of the code.
Ram Prasath
Ram Prasath 6 meses atrás
If a *quantum computer* comes in future will it be able to solve? (At least in a few thousand years 🤔 Who knows!!)
bandie9101
bandie9101 6 meses atrás
many top processes are running as root...
REX [Entertainment]
REX [Entertainment] 6 meses atrás
2019: Now with my ROG laptop I can get ackerman (4, 1) in about 5 seconds. It's amazing how computing power escalates through time.
Proxy
Proxy 6 meses atrás
I cannot get above (4,0) my program just crashes :c
Próximos vídeos
Top Powerful Computers Ever
10:21
Visualizações 110
How A Blind Person Uses A Computer
2:39