Busy Beaver Turing Machines - Computerphile

The Busy Beaver game, pointless? Or a lesson in the problems of computability? - How do you decide if something can be computed or not?

This video was filmed and edited by Sean Riley.

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

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

[nandeeshgupta]

Busy Beaver (5) is 47, 176, 870. Was verified recently in the busy beaver challenge.

[Philosoph]

I really enjoy seeing someone who talks so passionately about their subject. It really motivates you to want to learn more.

[chris_brenan]

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.

[LuizBHMG]

I'm the new busy beaver: I'm gonna replay this video until I understand it.

[iLoMs]

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.

[JohnGillett]

The David Attenborough of Computer Science!

[heyheyjj]

Hello from the year of Busy Beaver 5!!! super excited :D

[gazeboist]

BB(7198) is independent from ZFC, proven in 2016 by Adam Yedidia. BB(4888) depends on Goldbach's Conjecture; BB(5372) depends on the Riemann Hypothesis.

[Kingoftheclockend]

I'm not a computer or maths student at all, but I love listening to someone who is so infinitely smarter than me talk about the thing they're passionate about.

[Mnemo]

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.

[eternaldoorman]

In primitive recursive functions you have a set of building blocks where you can compute the arguments to functions lower down in the hierarchy to produce the values of functions higher up. Something similar happens once you have enough cards in Rado's scheme to define parameterised machines like "take a computable function f and a busy beaver b of n-c cards and use c extra cards to compute f(b) and write that many ones onto the tape and then halt. This is potentially a busy beaver for n cards and these are higher-order recursive functions that are being computed. These higher order recursive functions have been studied by William Tait, I think, and the logical (intuitionistic) consequences of their existence are explored by Girard _et al_ in an infuriatingly obtuse book called "Proofs and Types". I would love to see a video about that!.

[culwin]

University of Nottingham has the best professors.
I could listen to this guy all day.

[johnclark]

If this isn't the best science video on YouTube it's certainly in the top five. I've never seen Turing machines described more clearly.

John K Clark

[kennethcarvalho]

Channel is so deeply into Turings work which is really helpful

[justinbieber]

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.

[HYBRID_BEING]

7:01 "Wow, bound to win an award."
Oh man, this is priceless.

[vpelss]

That's what I needed to see how the turing machine runs.
1st bit : see if there is a 0 or 1 on tape
2nd bit write a 0 or one on the tape
3rd bit go left or right 0/1 L/R
last bits : jump to next card state