Busy Beaver Turing Machines - Computerphile

Computerphile
Computerphile
398,697
0
Published 2014-09-02
The Busy Beaver game, pointless? Or a lesson in the problems of computability? - How do you decide if something can be computed or not?

Professor Brailsford's code and further reading: bit.ly/busybeaver

Turing Machine Primer:    • Turing Machine Primer - Computerphile  
Busy Beaver Code:    • Busy Beaver Code - Computerphile  
Ackermann Follow Up:    • Ackermann Follow Up - Computerphile  
Original 'Ackermann' Film (Most Difficult Program to Compute):    • The Most Difficult Program to Compute...  

www.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
All Comments (21)
  • @VechtMalthos
    As it turns out, the universe is just a Busy Beaver program running on an extra-dimensional supercomputer and the higher-ups don't know whether or not it will halt yet.
  • @TheRealFaceyNeck
    It is always so amazing to me, that Prof. Brailsford is not only immensely brilliant academically, but even moreso brilliant at story telling. I could listen to him on podcast daily.
  • @KasranFox
    I don't know about you, but "faster than any computable function" sends a chill up my spine.
  • @LuizBHMG
    I'm the new busy beaver: I'm gonna replay this video until I understand it.
  • @unexpectedTrajectory
    to explain why the bus beaver numbers ultimately outpace any computable function: for any computable function some sufficiently complex busy beaver with a finite number of cards can be programmed to calculate any arbitrary value of that function, then print "that many +1" 1s and halt.
  • @97MrOmar
    I really enjoy seeing someone who talks so passionately about their subject. It really motivates you to want to learn more.
  • @carbrickscity
    What's fascinating is that this function grows faster than even TREE(n) and SCG(n) eventually.
  • @Mnemo85
    Professor Brailsford has such a pleasant voice.. I could listen to him talk for hours. He should record some audio books or pick up voice acting.
  • @asdf30111
    At 2 mins the video proves he is a hologram. 
  • @justinbieber9656
    watching this video in 2020 makes me feel as if I am from the future. The record for n = 6 is 10^2879. For n = 5 the current record is 47 176 870, but it is not known about some machines whether they are in a loop, so that record could still be broken.
  • @thomasreglar2410
    I saw this and just said to myself "well it would loop forever", but when he said you have to find a finite number of 1's, I thought " well how the f**k am I supposed to do that?" I'm still smiling about it now
  • @aplcc323
    " join the Beaver club! Get your own super computer! "
  • @PeterWalkerHP16c
    Oh look, the ground is opening up beneath me. And there is Godel, Cantor, Turing, Conway, Mandelbrot, Heisenberg, Chaitin et al already falling, all screaming as they descend.
  • @imacds
    Finally I comprehend what the fuss is about the halting problem.
  • @iLoMs012
    This man is so charismatic. More videos with him, please. Not many people can explain something with so much enthusiasm that it translates to you. Other guys are good too but he is definitely ahead of many.
  • @culwin
    University of Nottingham has the best professors. I could listen to this guy all day.