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?
Professor Brailsford's code and further reading: bit.ly/busybeaver
Turing Machine Primer: • Turing Machine Primer ...
Busy Beaver Code: • Busy Beaver Code - Com...
Ackermann Follow Up: • Ackermann Follow Up - ...
Original 'Ackermann' Film (Most Difficult Program to Compute): • The Most Difficult Pro...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...

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

[@theking94hm]

+Facey Neck Yes please, we need this.

[@ratgr]

lets start a request for this podcast to exist

[@AaronHollander314]

sounds a bit like Winnie the Pooh

[@Hagop64]

Pretty sure he could in front of a freshly painted wall, describing the paint drying and I would still be captivated.

[@rubenb8653]

Isnt he a teacher also? Bet hes one of those acrually great and memorable ones

[@KasranFox]

I don't know about you, but "faster than any computable function" sends a chill up my spine.

[@jeffcarroll1990shock]

No it does not. There are no busybeavers, there are just electrical signals switching from a on state to an off state.

[@renomado8616]

@@jeffcarroll1990shock ?

[@jeffcarroll1990shock]

@@renomado8616 zeros and ones.

[@MABfan11]

i wonder if there is a function that is faster than any computable function, period.... Busy Beavers are only faster than all computable functions *eventually*, so they don't qualify

[@KasranFox]

@@MABfan11 i mean, any function we think of as faster than another function is typically only faster eventually, for some value of eventually. like, x! grows faster than x^2 "only" for x > 3

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

[@General12th]

+Vecht Our Universe is just a G64-card Busy Beaver program.

[@jetison333]

+Vecht lets hope it doesnt halt. and really if you want to think that way it will loop eventually, when entropy runs out.

[@jeremiahglover7562]

Sounds like something Douglas Adams would say.

[@Zebra_M]

The year is 2020, the machine is slowly approaching its halt state

[@geraldine-211]

@Vecht haha

[@nandeeshgupta7606]

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

[@piguy314159]

More specifically, 47176870 is the maximum number of steps that a 5-state machine can run before halting; the number of 1s produced is the 4098 mentioned in the video. Also BB(6) was shown in 2022 to be at least 10 ↑↑ 15 (i.e. 10^10^10^…^10, with 15 10s)

[@ahmoin]

Yesterday people were celebrating Independence day. People should've been celebrating BB(5) being proven.

[@lame_lexem]

i hope computerphile or numberphile would make a video report and interview some of the folks who were proving it

[@GursimarSinghMiglani-ym7nu]

Yes

[@brycemw]

BB(6) may never be solved because we’ve already found machines that would require solving a version of the Collatz conjecture to determine if they halt or not

[@Philosoph8]

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

[@Triantalex]

false.

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

[@redjr242]

It turns out that if you can compute all Busy Beaver numbers, you can solve the Halting problem. Proof: Suppose that M is a machine such that for any n, M can compute BB(n). Let's now show that M can solve the halting problem. Suppose that T is Turing machine with n instructions. All M has to do is run T for BB(n) steps. If T halts before then, then T of course halts. If T does not halt in that time, then T doesn't halt at all, because, by definition, BB(n) is the longest running halting Turing machine with n instructions. Therefore M solves the halting problem. Since no Turing machine can solve the Halting problem, no Turing machine can compute BB(n) for arbitrary n. Since computable functions are exactly those that Turing machines can compute, BB(n) grows faster than any computable function. Note that we can always build a sufficiently complex Turing machine to compute a particular Busy Beaver number. But no fixed Turing machine can compute all Busy Beaver numbers.

[@emilioar7337]

@@redjr242 An inmortal, sufficiently smart computer scientist with inifinite time is just a sofisticated Turing machine, isn't it? Couldn't it compute all BB(n) in increasing order?

[@awesomegamedev]

@@redjr242 It's very interesting, but where did you get this proof? It seems incorrect here: > by definition, BB(n) is the longest running halting Turing machine with n instructions No, by definition, BB(n) is the biggest number of 1s produced by the Turing machine with n instructions. It might take much longer than BB(n) steps to produce such a number of 1s. > Note that we can always build a sufficiently complex Turing machine to compute a particular Busy Beaver number. But no fixed Turing machine can compute all Busy Beaver numbers. If we were able to make Turing machine to compute a particular busy beaver number, then (it seems like, needs more thought) we would also be able to make Turing machine "builder" - a Turing machine that builds a Turing machine that computes a particular busy beaver number and then executes it, and thus be able to compute all busy beaver numbers.

[@rykehuss3435]

Chris Brenan at what value of n does BB outpace the TREE function? Considering TREE(3) is already unfathomably large while BB by comparison hasnt even left the starting line at 3. Or 6. Or 7.

[@unexpectedTrajectory]

Sorry for a slow reply. No clue. But early values of functions can be very misleading. I believe it is generally agreed that Loader's Number is much greater than TREE(3) (or, for that matter, TREE(TREE(3))), and is achieved using a 512 character C program. Obviously that could be written as a Turing machine with some odd thousands of states. To circle back to your question, the exact point at which BB(a) overtakes TREE(a) is probably beyond our determining at present, but it isnt too difficult to wrap your head around the proof of why it has to happen. The fact that the very first few BB numbers are unimpressive only reflects the fact that tiny computers cant do much. But, to use an analogy, the fact that X^2 < X for X

[@JohnGillett554]

The David Attenborough of Computer Science!

[@Triantalex]

false.

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

[@GursimarSinghMiglani-ym7nu]

It’s been 9 years.. are u over your crush?

[@LuizBHMG]

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

[@shortcat]

not the most effective algorithm

[@boiledham]

Unfortunately that would be an invalid configuration; the Turing machine is required to halt.

[@legendgames128]

BoiledHam woah, you didn't have to do him like that. But he is a 1-state machine that writes 1s to the right each time he doesn't understand.

[@yanivrubin4166]

Make sure you watch "turing machine primer" in the description :)

[@Triantalex]

ok?

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

[@Triantalex]

false.

[@heyheyjj]

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

[@kennethcarvalho3684]

Channel is so deeply into Turings work which is really helpful

[@culwin]

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

[@asdf30111]

At 2 mins the video proves he is a hologram.

[@antivanti]

At 14:30 it would appear he is a T1000 =P

[@Borednesss]

Anders Öhlund That was scary

[@asdf30111]

Anders Öhlund That can only mean one thing he is the worlds 1st transhuman. (can't wait for hate comments because I said 1st.)

[@imadhamaidi]

@@asdf30111 it looks like you have waited.

[@Triantalex]

false.

[@eternaldoorman5228]

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

[@magnusnilsson6217]

Thid lectures are really nice! They are, in their own kind, masterpieces. Thank you all involved!

[@gazeboist4535]

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.

[@imadhamaidi]

now that's an interesting thing to know, is the proof less than 50 pages of invented symbols and obfsucated predicate logic?

[@gazeboist4535]

@@imadhamaidi Probably? I don't know about the page count, but Yedidia didn't hand write with the TMs himself or do any sort of weird indirect existence proof; instead he designed variant of a programming language that compiled to TM specifications for an existing academic TM simulator, with optimizations focused on reducing the number of states used.* Then he wrote programs with the basic logic of "if [interesting unprovable/unproved statement], return true, else loop forever." I would guess that the papers mostly focus on discussing his compiler, which is the real meat of his work, although I know that the TMs produced were published and I think checked somehow. I got this info from Scott Aaronson's blog, where he posted about it around when Yedidia (at the time one of Aaronson's grad students / post docs, IIRC) was publishing; you should check those posts out yourself if you're curious. * A fun lesson in tradeoffs, and the dangers of code golf: the TMs Yedidia's compiler produces are crazily slow. Aaronson talks about their test program, which checked that 3^3 = 27. If I remember right, the resulting TM took something like three days to return a result. Thus, while I believe Aaronson did say they had one of those TMs running, I wouldn't hold out hope for an answer on either of those two conjectures from this quarter.

[@imadhamaidi]

@@gazeboist4535 just checked the blog post out and i'm blown away, so if you could find BB(7198) you can literally check the consistency of ZFC axioms, only if we had some magical way to do so

[@MABfan11]

the bound has been lowered to BB(748)

[@bepisman297]

7918 to 1919 to 748 to 745 and now 643 as of september 1st 2024

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

[@Caracazz2]

Those machines could never halt even if they're not in a loop. Something equivalent to computing π, for example.

[@ben_spiller]

Watching this video in 2022, the new record for BB(6) is 10↑↑15.

[@micfiend5986]

47 176 870 is the number of steps, not the number of 1's. The n = 5 record is still 4098 1's (I think).

[@SuperChooser123]

Lol

[@Triantalex]

ok?

[@johnclark8359]

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

[@HYBRID_BEING]

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

[@schelsullivan]

He needs a roll of Brady's brown paper.

[@Computerphile]

schel sullivan that's just for Numberphile, Sean has his computer printer paper! >Brady

[@Triantalex]

false.

[@GideonMaina]

"Get yourself a super computer"- hmmm, I would love to, great insights Prof.

[@spendle]

For shits and giggles, I calculated the amount of 5-card Turing machines. It's 63,403,380,965,376 machines, or 6.34*10^13 if that floats your boat.

[@jrg3213]

But can they run crysis? XD

[@Hagop64]

6-card is 232,218,265,089,212,416 machines 7-card is 1,180,591,620,717,411,303,424 machines 8-card is 7,958,661,109,946,400,884,391,936 machines Can't imagine how the large the "best" machine is from any of those considering the growth rate.

[@tonylee1667]

@@jrg3213 The number isn't computing power tho

[@Gimodon]

So if you had a supercomputer than can run a million Turing machines a second, it would take about 2 years (I'm not sure how fast they can really do it.)

[@yanivrubin4166]

That number is so large, there is no way my boat will stay afloat after it boards

[@coopergates9680]

So to get that 10^10500 number for a score estimate for the 6-card machine case, you had to evaluate a computable function, otherwise you would not have had an answer. It sounds like you can estimate how fast the busy beaver function grows, but it will always be faster than the estimate and you will never know exactly how fast it grows because you can't compute it.

[@jamesdavis3851]

+Cooper Gates The bb function is perfectly computable for any particular value, in the same sense way that it's perfectly reasonable to determine if a particular program will halt. It's non-computable in the sense that no algorithm can output the correct bb number for an *arbitrary* input.

[@coopergates9680]

+James Davis Yes, though calculating 10^18500 (I think the bound has been raised already!) directly by running all those turing machines until the highest halting score is found would be very impractical, so that wasn't what was used to find the result.

[@coopergates9680]

+James Davis A polynomial versus an exponential is a much less painstaking problem, such as if you wanted to know when 2^x overtakes x^45, you just set them equal to each other and solve for x, and you know that the solution is greater than 45 in this case because 2^45 < 45^45.

[@jamesdavis3851]

+Cooper Gates The solution is a transcendental that's arguably non-trivial to compute, but my point was that you don't have to compute where 2^x overtakes *every* polynomial to know that it eventually will overtake *any* polynomial. That's what defines the rate of growth of a function, not where it overtakes another class of functions, but the fact that it does at some point. The proof that bb overtakes any computable function is extremely easy, even finding an upper bound like you did in your example is very easy. But yes, the exact point at which bb overtakes a particular computable function isn't easy.

[@coopergates9680]

+James Davis I said that I found a *lower* bound because 45 for x gives 2^45 for the exponential and 45^45 for the polynomial. Anyway, what about comparing the growth rates of the Xi, Rayo, and FOOT functions?

[@imacds]

Finally I comprehend what the fuss is about the halting problem.

[@Triantalex]

ok?

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

[@Triantalex]

false.

[@seanski44]

Arghh missed some compression glitches at 2mins in 😠

[@NNOTM]

It looks kind of cool, though.

[@Faxter313]

almost thought it was intended.

[@antivanti]

There's something really funky at 14:30 as well =P

[@seanski44]

Anders Öhlund ah yes, but that was 'by design' :)

[@antivanti]

You're just trying to hide the fact that he's a T1000 or a hologram :-P

[@SyntekkTeam]

Really cool video. It reminds me a little of langstons ant. A video about that would be cool too.

[@rykehuss3435]

The proof for why BB function eventually grows faster than any computable function is beautiful in its simplicity. Its because of the infinite tape. Because the beaver has infinite tape, it can create any computable function on the tape. It can create anything on the tape that can be expressed in binary code, like the works of Shakespeare.

[@PaulFurber]

Someone once explained to me that BB(768) is such an unimaginably huge number that if we dedicated all the atoms in the universe to computing it, we still wouldn't be able to - and yet it is a finite integer. That boggled my mind. Such a short description of such a gargantuan quantity.

[@ben_spiller]

Don't even need to go that high. It was proved BB(18) > Graham's number.

[@PaulFurber]

@@ben_spiller Whoah. Didn't know that, thanks.

[@KungFucianist]

This man could make drying paint entertaining.

[@Skibbi198]

I would have killed to have him as my compsci professor.

[@johnno4127]

I love how the beaver teeth hang over the tape sometimes, a nice detail.

[@u06jo3vmp]

BB(5) was proven to be 47176870 this year

[@shortguy014]

I could listen to David all day!

[@gedstrom]

Another statistic that I think would be interesting would be for Turing machines that actually halt, what is the maximum excursion of the read/write pointer in both the positive and negative directions? In other words, how much tape was needed?

[@ChristianBrugger]

The wiki page on Busy beaver has a function S(n) for the maximum shifts. Its kind of close to what you have in mind.

[@Triantalex]

??

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

[@Triantalex]

ok?

[@RGC_animation]

The reason that at some points, BB numbers simply cannot be calculated with our current understanding of computers, even with infinite time, space, and ressources, is precisely because of the halting problem, where you cannot know wether any given turing machine will stop or not.

[@toast_recon]

Does this have to do with the fact that turing machines can run any algorithm? So the busy beaver problem is essentially "what is the largest number of 1s that can come out of an algorithm that only requires n cards", therefore after a point the busy beaver can always exceed a given algorithm, because it will at least include that algorithm (and every one that exceeds it).

[@mightyNosewings]

The proof that the busy beaver function is incomputable is actually quite straightforward. Let _BB_ denote the busy beaver function; _BB(n)_ is the busy beaver for _n_ states. Now assume _BB_ is a computable function. In this case, we have a computable function _BBT_ which computes the maximum number of transitions that a *halting* Turing machine with _n_ states can go through. This gives us a solution to the Halting Problem. Given a Turing machine with _n_ states, simply run it until either: * it halts; or * it has gone through _BBT(n)_ transitions. If it is not in a halting state by the end of _BBT(n)_ transitions, then it will never halt, because _BBT(n)_ is the upper bound on the number of transitions that a *halting* Turing machine of _n_ states can go through. But the Halting Problem has been proven to have no solution. Thus, by contradiction, the busy beaver function is not computable.

[@Triantalex]

??

[@saber1epee0]

Absolutely Glorious.

[@aplcc323]

" join the Beaver club! Get your own super computer! "

[@Triantalex]

??

[@DaelinZeppiTheComputerGamer]

Remember watching this for my A-level studies. I graduated from university 2 years ago and remember learning about the term busy beaver all them years ago. Came back to this video after all this time, after coming across the term "busy beaver" again but not quite remembering what it was about. Suffice to say this video jogged my memory.

[@OblivionFalls]

14:30 I love that you can see how many people pressed replay for this part XD

[@MogaTange]

Some beavers are actually putting in a lot of work, but others are just repeating the same thing pretending they’re working every time the boss comes past.

Love the Busy Beaver Problem - a close relative to the Halting Problem. However when he says the machine head moves to the right on the tape, that was actually in the animation the Beaver's left so I was confused when he said "right" - was it our - the viewer's right - or the Beaver's right - I think he meant our right, but it was confusing lol.

[@javierborda8684]

I suspect I could be mind-blown by this if I understood.

[@ramone.chacon5084]

Mmmhn, not really

[@BB-zp8lu]

Who is here after watching George Hotz's busy beaver stream?

[@mandeepvayeda8029]

me

[@kpuwal2010]

me too :D

[@josephs.7960]

same

[@frommelow]

Before about to watch :D

[@paulklein4096]

I have no way of computing whether I got here by that method

[@shiinondogewalker2809]

so if busy beaver is a function, say b(n), that grows faster than any computable function, it also should grow faster than f(n) = b(b(n)). how? edit - I found out my error, appearently b(n) wouldn't be a computable function so f(n) is clearly faster but there's no problem about that. I find it really hard to see that b overtakes TREE, not that I really understand how big of a number such as TREE(3) is anyways.

[@DavenH]

This is one charismatic prof.

[@njclondon2009]

i watched this then built one of these things in R at work. great video, fascinating problem

[@Calvinatorzcraft]

People have their pc's cracking hashes all day. We need them to be finding busy beavers!

[@JacksonBockus]

They can’t; that’s rather the point

[@Triantalex]

false.

[@Kleinnnn]

this video is underrated

[@StevePagetWorld]

I wish this guy had been my tutor at Uni. What fun!

[@adamkimberley2575]

Is there an equivalent problem that can be stated in terms of the lambda calculus instead of a Turing machine?

[@chriscurtis8597]

Another excellent video!

[@adamkatav9752]

So the longest thing to compute and print is Busy Beaver with the input as Busy Beaver output starting from 1

[@gsg9704]

Consider Σ(n); where n= ackermann(g64,g64)

[@NeonsStyleHD]

Given that this races up faster than any other computable process, could it be used for something other than as a curiosity?

[@watcher314159]

+NeonsStyle Assuming all the laws of physics are Turing computable, which seems like a safe bet, then learning the size of the program our physics runs on lets us derive the size of the multiverse, and potentially even simulate ourselves. Granted, that would be of somewhat limited value for the most part, but it would still be an awesome datum of which to claim possession.

[@jetison333]

+eodguy83 you can write a program for a turing machine that calculates primes. it would just be horribly inefficient.

[@watcher314159]

jetison333 Actually, over on Numberphile it was mentioned that fairly recently there was discovered a computationally efficient perfect test for primality.

[@NeonsStyleHD]

***** Well that's as clear as mud!

[@Quasarbooster]

eodguy83 I believe Tor Diryc'Goyust is referring to an efficient primality test that only works for Mersenne primes (numbers of the form 2^p-1 where p is prime). I'm not sure if these kinds of primes are used in cryptography, but I would suspect not.

[@Jacob011]

LOL. This prof is awesome!

[@gedstrom]

Are there any online groups dealing with the busy beaver problem? This video was made 8 years ago and at that time, he said that there were 40 five-card busy beaver machines still running. I was wondering if any of those machines had been resolved in these past 8 years.

[@liam.28]

leaving this here in case someone answers so i get a notification

[@diegoparedes-vincent8910]

Same

[@asagiai4965]

Yes there is he mentioned the club. I just forget the time stamp. There's also T Rado's group if you search for it. There are other independent researchers too. Then there's also you and I which can create busy beaver programs.

[@gedstrom]

@@asagiai4965 Thank You!

[@ZXGuesser]

Yay, Professor Brailsford! More of this please ;)

[@Mrayis100]

Great vid, thank you so much!!!

[@justahker3988]

The Wikipedia entry for Busy Beaver has a (very weak) lower bound. It uses arrow notation, of course.

[@MABfan11]

sounds like someone needs to create a function that grows so fast it puts the Busy Beaver to shame

[@functional-tim]

There already exist a couple of functions that grow faster than Busy Beaver. The Busy Beaver is only the biggest function for a Turing machine and with that also for a computer. But functions like Rayo's number are not even possible to calculate with any tool. We just know they exist because of formal logic.

[@njclondon2009]

that was fascinating! great vid.

[@samuelwoods6648]

Is there a more slowly growing incommutable function?

[@Canuckish]

The David Attenborough of CS

[@jmp01a24]

4:19 "...and it will never ever stop", he sys showing a card with defined amount of places. It will reach the end (or start, since you started from the middle), then it would obviously turn and whizz off to the other side until it reach the end. It's very poorly explained. This CARD that he shows is not infinite. It's defined by a given amount of spaces. So how can it be infinite. OMG this takes me back to school and math-classes, where the teacher draws on the board and the logic breaks down, yet he keeps on drawing until he finds a number and draws two lines under it then finishes: "this is the answer". Answer to what? When he clearly not followed the rules of logic or defined the term deeply enough, just a fragment of it. How do they expect a child to learn something when everything seems to be "just make up rules as we go along"?

[@ben_spiller]

Turing machines are idealized machines with infinite tape. Obviously, his paper and his diagram are not infinite.

[@frankheuser3045]

Ths channel is an infinite time sink thanks

[@andrerenault]

Take a shot every time he says Busy Beaver

[@Chalisque]

I find it amazing that ZFC cannot prove what the 745th BB number is.

[@nowonmetube]

Sure that it grows faster than Loader's number? Edit: Loader's number is computable, so it's answered right there. But what about Rayo's Number? What about the FOOT function?

[@Peter_Schluss-Mit-Lustig]

Slower than Rayo Foot is ill-defined btw and has no output

[@Peter_Schluss-Mit-Lustig]

That's because you can completely recreate the busy beaver game in rayo's function in like 2000 symbols so with like 3000 symbols you overtake every single bb number below

[@TheMajorpickle01]

Hah at 2 mins the prof goes pro robot

[@Triantalex]

??

[@TheMajorpickle01]

@@Triantalex 10 year necro got to respect that. At two minute the video of the prof gets glitchy.

[@Kram1032]

So are there Busy Beaver equivalents for other models of computing? Say, lambda calculus? Or process algebras? Or type theory? Or what ever other magical models there are out there? What about Conway's game of life, for instance? You could have something like "Which n by k pattern, which actually becomes static in finite time (after some finite n, it may only contain periodic patterns or static ones (although I guess, busy beavers completely rule out dynamics, so perhaps periodic patterns are not allowed either)), produces the largest number of life cells?

[@FerroNeoBoron]

I haven't heard of one. I think that for any calculus the tape would be the axioms, the program the inference rules, the 1s are the number of theorems it can output and the halt state is a fixed point. It would be a little weird for games of life. I think the board would be the tape, the program would be the ruleset, the 1s would be the live cells and the halt state ... I guess an idempotent board state like you said but that does seem a little arbitrary.

[@Kram1032]

Ferroneoboron san actually, a quick google search suggested that this idea indeed exists for cellular automata of sorts - namely those which are also 2D turing machines. Turmites. ( ***** please do a video on those too :) ) Though I was unable to find something for other computational models, at least not from a 5min search.

[@unvergebeneid]

Yep. en.wikipedia.org/wiki/Busy_beaver#Generalizations "For any model of computation there exist simple analogs of the busy beaver."

[@Kram1032]

Penny Lane damn, sometimes one should just try the obvious thing

[@unvergebeneid]

Kram1032 Oh yeah, hi! You should get yourself a profile pic, good for recognition value :) I guess they didn't go into detail because it's rather trivial to construct these things for any given model and the fundamental argument will be basically the same as for the original one.

[@eddiehazel1259]

love the glitching effect! how does one do that?!

[@Hurfdurfhurf]

The professors face at 14:30 scared me a bit

[@Tulanir1]

reptile shapeshifter conspiracy theorists incoming ( ͡° ͜ʖ ͡°)

[@Migger_29]

Go to red light district if you want to find the busiest beaver.

[@pjousma]

Math hell, take that Ackermann.

[@dukestt]

i get that the tape is infinite, i get that the head moves in either direction. I get that the number can be a 1 or 0, what i dont get is what the tape starts with. is it all 1's all 0's or is it a random mixture of the two??

[@gedstrom]

For the Busy Beaver problem, the tape starts with all zeros by definition.

[@PvblivsAelivs]

I think a difficulty I have with this video is that, when I hear "looping," I think of periodic behavior -- the machine returning to a previous state. What makes this so nasty is that it can turn out non-periodic. It might never repeat a state. If it got into a loop (as I think of loops) the condition could be detected. But if all programs that failed to halt periodically repeated their state, the halting problem would be solvable.

[@PvblivsAelivs]

eNSWE "I haven't ever really heard anyone referring to the tape as part of the machine's state," You have now. And the reasoning is simple. The contents of the tape can influence whether a Turing Machine halts or not and how long it takes, if it does halt. (It also influences the final "answer." "these are loops in the sense that the machine is in a certain state c, reads some input symbol a, and the transition function returns the same state and moves the head so that the same thing will keep happening over and over again." The problem with that analysis is the the machines that are still undecided don't quite do that. They only keep repeating their state number in the same sense as the decimal expansion of pi keeps repeating the digit '1'. Their behavior (as near as can be determined) is non-periodic. Even if you have a "partial state" that you know must return after n moves, you still determine a type of periodic behavior and can rule that it does not halt. If all Turing Machines either halted or exhibited periodic behavior, the halting problem would be decidable.

[@eNSWE]

look, I didn't make up the fact that what this video refers to as "cards" is actually what is referred to as "states" in the formal definition. of course I understand that the input can affect whether the TM halts or not (if it is a parital recursive function, otherwise it doesn't matter), but the "state" of the machine is explicitly defined as what "rules" the machine is operating under at the moment (and thus how the transition function behaves). it's just terminology. the transition function takes the current state and the next character on the tape as it's arguments.

[@PvblivsAelivs]

eNSWE What you said is that you had not previously encountered anyone who regarded the contents of the tape as part of the state. I took that at face value and simply told you that you have now. I also told you why I consider it part of the state. " it's just terminology." Language is just terminology. The point of my original comment is that it is evident that he is trying to convey some idea other than what the words used mean to me. That is a difficulty as I am not able to determine conclusively what he is really trying to say. Your apparent position is that it should be self-evident what he really means. That's the trouble with natural language. It doesn't always work that way.

[@PvblivsAelivs]

Mat M Well, there are a few "tricks." If you can identify a partial state that must repeat itself after some finite number of turns, you can prove non-halting. It was once believed that any set of shapes that could tile the plane could do so periodically. And then it was proven that that assumption would make the halting problem decidable.

[@Seegalgalguntijak]

I had a thought which went like: "Well, would a quantum computer here be much help? Could you program it to calculate the max number of 1's for a 10 card Turing machine, and it would take some time (but not like centuries) and give you the correct answer? Or if so, is there maybe just some mathematical trick to the busy beaver problem, so that it can be put into a rather simple formula like "beaver of x" (with x being the number of cards) equals to y (with y being the max number of 1's)? I think such a thing should be possible (for a mathematical genius like Turing it might not even have posed much of a problem, but unfortunately not many people like him are alive today, if any)...

[@MrCmon113]

Seegal Galguntijak You don't need a genius for that. Here BB(n). There is your mathematical formula. Thing is that you can write formulas for anything, but that doesn't make them computable. What you are looking for is an algorithm and because algorithms are just as powerful as TMs, you cannot construct a computable function growing faster than BB by definition.

[@matsv201]

Wishlist.... QUantum computer programming.... Basicly how to use a quantum computer for anything useful. A quantum computer is really powerful, but equally hard to program for.

[@daandekker6115]

Provided you get the hardware wouldn't it be like programming in base-3?

[@matsv201]

Daan Dekker No, thats the strange part. If it a 2 qbit system, it works like a base-4 system. But if it a 3qbit system it worke like a base-8 system, and so on. A other strange thing is that, well, how it is described today, a quantum computer can do only one instruction. Well, there is 7 different types of quantum computers, so in a way, if it were possible (that it might be, i don´t know) to make a quantum computer with multiple instruction, it could be only be a maximum of 7 instruction. A quantum compter works in now way like a Turing machine, or a ALU. A ALU normaly gets one binary number and combine it with a other to make a third. The turing machine use the ALU to do this in different order to make a computer program. Thats basically what all programs do, nothing less, nothing more. A quantum computer takes a string or matrix of number, than process it and put ot a other matrix of numbers. And a Q-compuiter (well, the way they are imagned to day) will always do that in one specific way. There is different way to do it, but every given Q-computer will always do it in the same way. One common instruction is that it factorize numbers. A other is to find the shortest distance in a matrix with a given set of points. This can also be seen with a soap bath quantum computer (that isn´t really a quantum computer, but often is confused with one, well, it gives a faulty answer most of the time). But its a nice way of showing how a quantum computer suppose to work

[@matsv201]

***** Yea, thats kind of the problem. The expert is quite agreable on how to build one. Well, there is a couple of different ways, but it similar in principle. Yea, they are great with crypto breaking, and they are great with traveling salesman problem. But how to do anything usefull. I actualy never hered someone say anything usefull you can do with a quantumcomputer.

[@Teth47]

***** More specifically, a quantum computer loads the program into the processor in its entirety, storing every bit of information and the program that is supposed to compute it simultaneously. It then works like a filter. The superimposed states are collapsed as they are measured into either a 1 or a 0, the result being dictated by the nature of the program layered on top of the data. The result after all states have been collapsed and measured is the answer to the problem. This is why it's so dangerous for hashing and encryption. If there are enough qubits in the processor to store the entire encryption key (Without superimposed states) it can be brute force decrypted in a single processor cycle, though that cycle would take longer than a traditional processor, operating at a speed of maybe tens of hertz rather than billions. You can kind of think of it like lithography. There is a substrate and a mask, or in this case, a pair of masks. The substrate is the quantum processor, one mask is the data, the other is the program, the two masks create an interference pattern which is etched into the substrate, the interference pattern is the answer to the problem.

[@matsv201]

Teth47 Great explination.. but then my question remains... what else can you do with a quantum computer (effectively

[@jms019]

I think my head is about to explode and I will halt

[@philipstuckey4922]

so ... If I have the busy beaver function BB(n) that for any n it calculates the maximum number of 1s writable by an n card halting Turing machine, would the function F(n) = BB(n)*n grow faster than the busy beaver function?

[@siprus]

I wanna know how long the longest running busy beaver machine of given amount of cards, runs?

[@htmlguy88]

siprus from wikipedia: 2-symbol621107≥ 47,176,870> 7.4 × 1036534 for number of steps

[@tabularasa0606]

@Marian Gherca You forgot to add: "in 24 bits" You can easily define a 48 bit RGB palette or a 12 bit one.

[@PplsChampion]

irl the programs that win the BB game are similar to ackermann functions

[@RyanT301]

Genius, see this is what should be taught in schools in America. China teaches their kids this in middle school for example

[@vfoster9000]

I would be interested to learn a little more about Bremermann's limit.

[@julkiewitz]

Well this function grows faster than any computable function, but it also means it's proven that it's uncomputable, correct?

[@FrostDirt]

Yes, it's uncomputable

[@joelthomastr]

There's gotta be some fractals in this

[@NickNackGus]

How much worse does this problem get if you include the 1's that we've erased? Pretty bad, I imagine.

[@JakeFace0]

are there any numbers of cards for which any finite number of 1s may be produced?

[@Macatho]

Correct me if I'm wrong but 256*10^8 is 25.6 billion in the short scale and 25.6 milliards in the long scale? Not 25.6 trillion...

[@canatronYT]

yeah he must have misspoke

[@oscarchivas3123]

I may have missed it in the video, but what is the point of solving the problem? What would it accomplish?

[@MrCmon113]

It's fun. Welcome to mathematics.

[@imadhamaidi]

maybe if we develop computers that are not turing machines we can calculate BB(n) and use that to solve the halting problem

[@juliasmith5267]

Sweet. Thank you for the video.

[@Yora21]

15:30 Never laughed at a math video before, but that did it.

[@Destrolll]

14:30 look at his face

[@TheApeMachine]

4:43 ... Now we're here...

[@brett1234-s7f]

Is this concept similar to finite automata?