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

8 жыл бұрын

+Facey Neck Yes please, we need this.

@ratgr

7 жыл бұрын

lets start a request for this podcast to exist

@AaronHollander314

5 жыл бұрын

sounds a bit like Winnie the Pooh

@Hagop64

5 жыл бұрын

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

@rubenb8653

4 жыл бұрын

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

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

@jeffcarroll1990shock

2 жыл бұрын

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

@renomado8616

2 жыл бұрын

@@jeffcarroll1990shock ?

@jeffcarroll1990shock

2 жыл бұрын

@@renomado8616 zeros and ones.

@MABfan11

2 жыл бұрын

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

2 жыл бұрын

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

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

8 жыл бұрын

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

@jetison333

8 жыл бұрын

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

@jeremiahglover7562

4 жыл бұрын

Sounds like something Douglas Adams would say.

@Zebra_M

3 жыл бұрын

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

@geraldine-211

3 жыл бұрын

@Vecht haha

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

@shortcat

2 жыл бұрын

not the most effective algorithm

@boiledham

2 жыл бұрын

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

@legendgames128

2 жыл бұрын

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

2 жыл бұрын

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

The David Attenborough of Computer Science!

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

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

4 жыл бұрын

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

4 жыл бұрын

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

3 жыл бұрын

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

3 жыл бұрын

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

3 жыл бұрын

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

What's fascinating is that this function grows faster than even TREE(n) and SCG(n) eventually.

@carbrickscity

6 жыл бұрын

Computerphile/Busy Beaver are underrated compared to Numberphile/TREE. What's funny is that in the TREE(3) video they talked about how you can keep iterating the TREE function to make it bigger, but it is still computable. Thus it will never surpass the Busy Beaver.

@carbrickscity

5 жыл бұрын

In the world of big numbers I don't think we should even mention the number of atoms in the universe lol

@shotgun6X

5 жыл бұрын

@@carbrickscity agreed. It's such a small number in comparison. Like, unbelievably small

@want-diversecontent3887

5 жыл бұрын

CarBricksCity What even is SCG?

@nowonmetube

5 жыл бұрын

@@want-diversecontent3887 it's a mathematical function like Tree but it grows much faster.

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.

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

5 ай бұрын

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

4 ай бұрын

Lol

At 2 mins the video proves he is a hologram.

@antivanti

9 жыл бұрын

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

@Borednesss

9 жыл бұрын

Anders Öhlund That was scary

@asdf30111

9 жыл бұрын

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

3 жыл бұрын

@@asdf30111 it looks like you have waited.

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

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

3 жыл бұрын

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

@gazeboist4535

3 жыл бұрын

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

3 жыл бұрын

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

6 ай бұрын

the bound has been lowered to BB(748)

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

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

Channel is so deeply into Turings work which is really helpful

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.

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

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

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

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.

He needs a roll of Brady's brown paper.

@Computerphile

9 жыл бұрын

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

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

7 жыл бұрын

But can they run crysis? XD

@Hagop64

3 жыл бұрын

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

3 жыл бұрын

@@jrg3213 The number isn't computing power tho

@Gimodon

2 жыл бұрын

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

2 жыл бұрын

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

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

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

9 жыл бұрын

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.

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

9 ай бұрын

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.

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

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

Arghh missed some compression glitches at 2mins in 😠

@NNOTM

9 жыл бұрын

It looks kind of cool, though.

@Faxter313

9 жыл бұрын

almost thought it was intended.

@antivanti

9 жыл бұрын

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

@seanski44

9 жыл бұрын

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

@antivanti

9 жыл бұрын

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

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

@JacksonBockus

3 жыл бұрын

They can’t; that’s rather the point

I could listen to David all day!

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

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

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.

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

@mandeepvayeda8029

3 жыл бұрын

me

@kpuwal2010

3 жыл бұрын

me too :D

@josephs.7960

3 жыл бұрын

same

@frommelow

3 жыл бұрын

Before about to watch :D

@paulklein4096

3 жыл бұрын

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

Yay, Professor Brailsford! More of this please ;)

Absolutely Glorious.

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

14 күн бұрын

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

@PaulFurber

14 күн бұрын

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

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

8 жыл бұрын

+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

8 жыл бұрын

+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

8 жыл бұрын

+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

8 жыл бұрын

+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

8 жыл бұрын

+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?

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

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

This man could make drying paint entertaining.

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

that was fascinating! great vid.

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

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

@watcher314159

8 жыл бұрын

+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

8 жыл бұрын

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

@watcher314159

8 жыл бұрын

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

@NeonsStyleHD

8 жыл бұрын

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

@Quasarbooster

5 жыл бұрын

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.

Another excellent video!

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?

Great vid, thank you so much!!!

This is one charismatic prof.

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

What did his face do at 14:30? ._.

@HEHEHEIAMASUPAHSTARSAGA

8 жыл бұрын

+ImagineBaggins Pretty sure that was a concealed cut in editing

@rzrx1337

8 жыл бұрын

+ImagineBaggins he's a reptilian like Obama. all these numbers and beavers must have interrupted his shape-shifting abilities.

@TruKave

7 жыл бұрын

I know how many jokes people are making here, but the real answer is a transition.

@FplusETVChannel

3 жыл бұрын

2:03 is even worse

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

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

In the instruction layout, for the 2-card case, how can the final column represent 3 possibilities -- 0 to halt, 1 to repeat the instruction on the current card, and 2 to go to the other card -- when a single bit can only represent two states?

@gedstrom

7 жыл бұрын

There is no requirement that that final column be a single bit wide. For the 2 or 3 card cases, you would need a 2-bit wide field. for 4-7 cards, you would need a 3-bit wide field.

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

9 ай бұрын

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

@diegoparedes-vincent8910

9 ай бұрын

Same

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.

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

Is there a more slowly growing incommutable function?

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.

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.

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

9 жыл бұрын

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

9 жыл бұрын

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

9 жыл бұрын

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

@Kram1032

9 жыл бұрын

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

@unvergebeneid

9 жыл бұрын

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.

Sweet. Thank you for the video.

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

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

@ramone.chacon5084

3 жыл бұрын

Mmmhn, not really

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

@htmlguy88

8 жыл бұрын

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

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

5 жыл бұрын

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

LOL. This prof is awesome!

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

Hah at 2 mins the prof goes pro robot

Can someone explain the multi card turing machine please?

Is this concept similar to finite automata?

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

Can't we take integral or some other operation to calculate directly without need of turing machine?

@softwarelivre2389

Жыл бұрын

Integrals are usually used on continuous functions, due to the need of multiplying differencials with the value of the original function at infinite points. BB(n) is a step function, so I don't think it would work. But you might be able to use other forms of infinite sums.

how would one express the time complexity of this function?

@imadhamaidi

3 жыл бұрын

BB(n), remember that it's been proven that it is not computable so there's no formula for it that you can plug into a computer. besides, all algorithms are O(BB(n))

if numbers get too big exponentially do you not get buffer over flow or out of range error>?

@dannygjk

6 жыл бұрын

Not if the tape is infinite.

@dannygjk

6 жыл бұрын

Oh I see what you mean on a real computer. No you can write a program which extends the size of numbers which can be dealt with. You are not limited by the limits of the MPU or operating system.

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

Fascinating

was this filmed in Mexico?

I’d be interested to know if a compute problem is actual following a Mandelbrot/fractal compute when it goes on forever. We have a situation of self modifying code (which is what a Turing machine is) and if you change the program, you can in essence, setup a chain of events which can recursively become the original program (or become a form of cyclic code such as a CRC algorithm).

@pentachronic

6 жыл бұрын

Shift left and right and change to a ‘1’or ‘0’ can be thought of as a logic function. If ‘1’ change to a ‘0’/If ‘0’ change to a ‘1’ is an XOR. Shifting is how a cyclic redundancy code (or LFSR) works. So surely a program can be broken down to logical and LFSR instructions and recompiled to figure out the order of LFSR.

this video is underrated

16:31 What's the smallest value of n for which that happens?

@nowonmetube

5 жыл бұрын

5

@imadhamaidi

3 жыл бұрын

@@nowonmetube proof?

@nowonmetube

3 жыл бұрын

@@imadhamaidi you mean like mathematical proof or "math is the proof"? Which answer do you prefer?

@imadhamaidi

3 жыл бұрын

@@nowonmetube i don't need you to paste a full proof here, just cite where the proof is and if it's too complicated you can just cite the experts that verified it

What is super exponential functions? Is that like 2^x?

@FerroNeoBoron

9 жыл бұрын

A function, f, is superexponential if it grows faster than all exponential functions. So it would satisfy (x>=n therefore f(x) > k*c^x) for all combinations of k and c and at least one n for a given combination of k and c. x! is a superexponential function since after x==c since c^x grows at a rate of c but x! grows at a rate of x. This will obviously make the k irrelevant very quickly. But the value of the busy beaver function grows even faster than the factorial function since because it's been proven that the busy beaver function grows faster than any computable function, of which factorial is one.

@toast_recon

9 жыл бұрын

If you haven't seen them, look up the numberphile videos on graham's number and the computerphile videos on ackermann's function. Super exponential (i.e tetration) includes two Knuth up-arrows, so 2↑↑x. It's like this: a times b is just a + a + a.... + a, with b copies of a. a^b is a*a*a...*a, with b copies of a. a↑↑b is a^a^a...^a with b copies of a. So the same incredible difference in growth we see when we compare a linear function to exponential one is seen when we compare a exponential function to a super exponential one. Instead of just growing incomprehensibly quickly (like an exponential), superexponential functions are uselessly uncomputable for very small values of x. The first few points of 2↑↑x: (2, 4): 2↑↑2=2^2=4 (3, 16): 2↑↑3= 2^2^2 =2^4=16 (4, 65536): 2↑↑4= 2^2^2^2 = 2^(2^4) = 2^16=65536 (5, ~2 x 10^19728)

@imnotrich12321

9 жыл бұрын

Ferroneoboran gave the answer. As a simple example, x! or x^x are both superexponential.

@jamez6398

9 жыл бұрын

toast_recon I know what tetration and Knuth's up arrow notation is, I just didn't know it was called a super exponential function...

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

@MrCmon113

5 жыл бұрын

It's fun. Welcome to mathematics.

@imadhamaidi

3 жыл бұрын

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

try to program them in piet

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

2 жыл бұрын

yeah he must have misspoke

Ths channel is an infinite time sink thanks

Where does this problem lie in the P-NP space?

@lukeinvictus69

6 жыл бұрын

you take the next left, go a 2 blocks and then go into the nearest corner store. If you look in the aisle containing toilet paper, remove the third one in the fourth column. The problem will be waiting for you there.

@marcthatcher

6 жыл бұрын

P = problems computable in polynomial time. NP = checkable in poly time or computable in non-deterministic poly time. BB is not computable so does not live in any set of computable functions.

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

So, would higher busy beavers eventually overtake something like TREE(TREE(TREE(TREE(TREE(...(X))))))?

@joebloggs3551

2 жыл бұрын

Yeah easily. SCG is vastly bigger than TREE, Loader is vastly, vastly bigger than SCG, Busy Beaver is a whole other ballpark to Loader.

What's with the glitchyness at 2:04?

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

9 жыл бұрын

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

@matsv201

9 жыл бұрын

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

9 жыл бұрын

***** 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

9 жыл бұрын

***** 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

9 жыл бұрын

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

Take a shot every time he says Busy Beaver

Why cant the head stay still, what will happen if the head stayed still? Can all move left, move right and stay still exists in busy beaver game?

@nowonmetube

5 жыл бұрын

What?

@TheUglyGnome

4 жыл бұрын

In Turing machine head can't stay still, because that would be redundant. You can simulate still head with other sequences of instructions. And because Turing machine is guaranteed to be simplest example of machine capable of computing all computable functions, you can't have redundancy.

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

5 жыл бұрын

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

@Peter_Schluss-Mit-Lustig

5 жыл бұрын

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

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

I am new to all of this, I am interested but what is the point of having a turing machine with the highest number of 1s

@the_peacemaker002

22 күн бұрын

There is no practical purpose, it's just a fun problem to solve

I'm confused. If it were noncomputable then how are we able to get results for some inputs?

@kaishang6406

2 жыл бұрын

I think it means that you can't compute it directly without simulating all possible cases.

@zachb1706

9 ай бұрын

Noncomputable because you don't know if any single busy beaver will halt. So you must manually determine which ones halt and then you can finally compute the input. I've seen this described as the "edge of computability"

@pmcate2

9 ай бұрын

@@zachb1706 I don't think that's completely correct bc what do you mean by manually determine? By the CT thesis that's just going to be something a TM can do. The issue is I forgot the word 'all' is key. There's no TM that can compute BB for ALL inputs.

@the_peacemaker002

22 күн бұрын

You can solve specific cases, but a general algorithm to solve any case is impossible.

The David Attenborough of CS

I wonder if this is the sort of thing you'd give to a super-intellect AI to keep it busy. Since we're running into trouble at 5 cards in, and there's no set cap on how many cards could be involved. Though I suppose there's potentially a way to develop some rule to figure out the answers without doing all the computing necessary and we just don't have the mental capacity to stumble upon that.

@imadhamaidi

3 жыл бұрын

if you mean by rule a computable algorithm, then no, that's proven to not exist.