The Boundary of Computation

Подписаться 65 тыс.

Просмотров 921 тыс.

50% 1

The machine learning consultancy: truetheta.io
Want to work together? See here: truetheta.io/about/#want-to-w...
There is a limit to how much work algorithms can do.
SOCIAL MEDIA
LinkedIn : / dj-rich-90b91753
Twitter : / duanejrich
Github: github.com/Duane321
Enjoy learning this way? Want me to make more videos? Consider supporting me on Patreon: / mutualinformation
THE BUSY BEAVER WORLD
In my opinion, the best place to start is Aaronson's "The Busy Beaver Frontier" paper (ref [1]). It's accessible, well written and provides a comprehensive view of the BB-world. Also, Googology represents the community in their efforts/excitement well (e.g. see ref [8]).
NOTES
[1] When describing how Sigma(4) is computed, I say "whittle to a small group that halt and ran to produce the max count of 1's". It has been pointed out to me that this isn't an accurate description. It's more accurate to say we whittle down to a small group that *don't halt*. What's done is, many machines are run, some halt and some continue to run. The hard work is in proving that the machines still running will in fact run forever. Once that is proved, the busy beaver number is the max count of ones written by all machines that halted so far.
REFERENCE NOTES
As mentioned, I mainly read Scott Aaronson's work for this (ref [1], [3]) and his blog: scottaaronson.blog/, where he posts BB related updates. Second to this was the wikipedia page (ref [6]). Also, [2] and [7] were useful for understanding how people pursue bounds and values for Sigma(n). The original paper (ref [4]) was useful to understand why Sigma(n) was invented in the first place (to provide a well defined non-computable function) and to understand the original format of the BB competition. The bounds related to Graham's sequence were found in [6] and [8].
REFERENCES
[1] S. Aaronson, "The Busy Beaver Frontier", www.scottaaronson.com/papers/...
[2] A. H. Brady. "The determination of the value of Rado’s noncomputable function Σ(k) for
four-state Turing machines". Mathematics of Computation, 1983.
[3] A. Yedidia and S. Aaronson. "A relatively small Turing machine whose behavior is independent
of set theory." Complex Systems, (25):4, 2016, arxiv.org/abs/1605.04343
[4] T. Radó. "On non-computable functions". Bell System Technical Journal. 41 (3): 877-884, 1962
[5] Copeland, B. Jack, "The Church-Turing Thesis", The Stanford Encyclopedia of Philosophy (Summer 2020 Edition), Edward N. Zalta (ed.) plato.stanford.edu/archives/s...
[6] Wikipedia contributors. "Busy beaver" Wikipedia, 2023, en.wikipedia.org/wiki/Busy_be...
[7] P. Michel. "The Busy Beaver competition: a historical survey". 2019. arxiv.org/abs/0906.
3749
[8] Wythagoras (Username), "The nineteenth Busy Beaver number is greater than Graham's Number!", googology.fandom.com, 2016, googology.fandom.com/wiki/Use...!
[9] S. Ligocki, "BB(6, 2) is greater than 10^10...^10", 2022, www.sligocki.com/2022/06/21/b...
TIME CODES
0:00 Introduction
1:21 A Binary Turing Machine
2:42 Two Things to Know about Turing Machines
3:54 What is the Busy Beaver Function?
5:40 Why is it hard to calculate?
6:28 Computability
7:41 A Shot at the King
10:36 The Busy Beavers reference open problems
11:39 Its values cannot be proven in some systems
12:08 The Busy Beaver World

Опубликовано:

25 май 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 1,2 тыс.

@Mutual_Information 10 месяцев назад

FYI, this topic is much bigger than what a 13 minute video can represent, so I'm planning a follow up video. That'll address the natural questions that follow from this one. And second, I'd like to say that this isn't a normal video for me. I'm not a complexity theory expert by any standard (in fact, I recruited an expert to help on this one), so I'll be getting back to machine learning topics in the future.

@antaries778 10 месяцев назад

The topic of non computable numbers is absolutely fascinating and is really well explored here. (There doesn't seem to be a huge amount on the topic across the internet, given its profundity) I'd be keen to learn more about how certain state machines map onto things like the Goldbach and Riemann hypotheses.

@pabloagsutinnavavieyra2308 10 месяцев назад

Hope you tackle some weird ideas like this one from time to time. I have never heard of the implications of the BB that you mention and it really made for me a new perspective in the topic.

@pedroivog.s.6870 10 месяцев назад

the duration was on purpose, wasn't it?

@yuan-jiafan9998 10 месяцев назад

Great video. But I would like to point out that you pronounced Alan Turing wrongly. It should sound like "Tu-ring", not "Tur-ring".

@Mutual_Information 10 месяцев назад

@@yuan-jiafan9998 oh wow I didn't know that, I appreciate the note

@maxturgeon89 10 месяцев назад

I've found an elegant proof of Goldbach's Conjecture, but this binary Turing machine is too small to contain it.

@orik737 10 месяцев назад

This is some serious math humor

@Malex21 10 месяцев назад

This hits too close to home

@Mutual_Information 10 месяцев назад

lol

@darealpoopster 10 месяцев назад

@@orik737ah, Fermat’s last theorem in unknown to people outside of math

@mikip3242 10 месяцев назад

Pierre not again!

@u06jo3vmp 8 месяцев назад

I actually think the name Busy Beaver is great. Because for most of us regular folks, we ran into this number when looking for something that beats the TREE function. Beavers chomp down trees. Perfectly fitting

@user-vs2jx1rf9y 2 месяца назад

Genius

@MogaTange 10 месяцев назад

I always thought Graham’s number was a really underwhelming name, but busy beavers so massively understates what it’s describing.

@condor6222 10 месяцев назад

I find it oddly fitting

@MogaTange 10 месяцев назад

@@condor6222 I was picturing something more like THE COMPUTABILITY BOUNDARY instead of 🌲🐿

@condor6222 10 месяцев назад

@@MogaTange with only 1 tree, that beavers clearly not busy enough

@MogaTange 10 месяцев назад

@@condor6222 are you suggesting I add my backups, tree 2 and tree 3

@Sealedaway 10 месяцев назад

Language and math as we know it is insufficient to describe just how busy those beavers are

@JSorngard 10 месяцев назад

Fun fact: there is a finite number of states in the observable universe. You can estimate an upper bound of the number of states of a system as e^S, where S is the entropy of a black hole with the same size as the system. For our universe this ends up being around S=10^123. This means that we could only ever hope to compute up to BusyBeaver(e^10^123), as later busy beaver numbers need computations that our observable universe is too small to contain.

@ksalarang 9 месяцев назад

🤯

@alexeyvlasenko6622 8 месяцев назад

Then, the question is, if the entire Universe is your Turing machine, what are you going to use as tape?

@hb-robo 8 месяцев назад

For some reason, I find this really unsettling...

@ksalarang 8 месяцев назад

@@alexeyvlasenko6622 the universe is the tape according to op. the question then is what will be the computer

@FaridTaba 8 месяцев назад

@@ksalarangStephen Wolfram has entered the chat.

@Cxntrxl 10 месяцев назад

When he started explaining Goldbach's conj. I thought to myself "that can't possibly be true" and started with even numbers less than 10 and then started having an existential crisis as I realised every even number I tried could be made up of two prime numbers

@adonaihilario1006 10 месяцев назад

I think it has been tested for numbers up to 4x10^14

@AlaiMacErc 10 месяцев назад

@@adonaihilario1006 But imagine the fame and glory to the person who thinks up the 20-digit number that's the counterexample! :D

@sinekonata 10 месяцев назад

@@AlaiMacErc If we're going to dream about crazy shit like that, imagine the person who finally finds we need to nuance the statement 1+1=2.

@franko8572 10 месяцев назад

My mind got blown when I read this and didn’t know what a prime number was.

@onionman8160 10 месяцев назад

I thought the opposite. It is such a frustrating conjecture to me because it seems to be obviously true. As you get larger, there are more and more ways that you can construct a number with 2 primes, like how 4 can only be written as 2+2, but 16 can be written as both 11+5 and 13+3. And since it's been proven that there are an infinite amount of primes, it would be extremely strange for the conjecture to be false.

@etatauri 10 месяцев назад

The most amazing thing about this is the human brain that has the ability to even describe the unimaginable in just a few symbols.

@imcpan2590 10 месяцев назад

It's rather pointing at something, than giving description.

@sudowtf 9 месяцев назад

If it’s unimaginable then we can, by definition, not describe it. We might have a rough concept of it but that’s just describing the concept of something we know exists but can not fully understand, or in this case, imagine. We have a symbol for infinity but there is no person on earth able to fully understand actual infinity because our brained are not wired that way. The easiest thought experiment I can give you is the following: Tell me the number separated by exactly the smallest possible number that preceeds ♾️. So basically the number that comes before you reach infinity. Now, you’ll figure out very quickly that you just can’t do it because you’ll always be able to add something to it which means you are never going to reach infinity. But we do have the concept of infinity. To know something is there and be able to fully understand it are two different things.

@alexeyvlasenko6622 8 месяцев назад

@@sudowtf You are not thinking about this correctly. Infinity is not a number at all, so the words "the smallest possible number that precedes infinity" are nonsense. These words don't mean anything. However, "infinity" expresses precisely the concept that one can always add something to a number to make it larger. There is no upper limit. How is a statement about the absence of a limit impossible to understand?

@sudowtf 8 месяцев назад

@@alexeyvlasenko6622 Infinity can not be expressed by a number, and numbers are by definition not infinite. There is always a limit. You can not just keep adding +1 to any number because eventually you’ll run out of storage, in whatever form it may be, to store your new number. So again, what is that number right before you reach infinity? There must be a point where infinity is reached. A sort of switch. So think of that, but then add +1 to that number and keep doing that. My thought experiment merely shows that we can not imagine, express or think of the unimaginable. If you want to dive deep into the mathematics then we can, but it’s a different topic really.

@sudowtf 8 месяцев назад

@@alexeyvlasenko6622 And infinity doesn’t exist in a finite universe. Nothing is infinite. You could say the universe itself is infinite because it’s expanding but there is no proof that it’ll keep expanding forever. Since “forever” isn’t even defined here. If we go by the normal definition then forever itself is an expression of infinity and again, we don’t know if the universe will expand forever.

@andie_pants 10 месяцев назад

Layperson here. Thank you for illustrating the idea down to its simple basic tables. I _finally_ understamd Turing machines and states!

@Mutual_Information 10 месяцев назад

There we go!

@nUrnxvmhTEuU 10 месяцев назад

My favorite mind-blowing fact is that the sum of 2^-BB(k) from k=1 to infinity definitely converges and we know what it's equal to up to an insane number of digits, but there is some precision which we will never be able achieve. The result of that sum is uncomputable. And since the vast majority of reals are uncomputable (the computable numbers have lebesgue measure zero), this weird number is somehow more typical than any other real number you've ever used.

@pedroivog.s.6870 10 месяцев назад

doesn't it converge to 0?

@zhg4485 10 месяцев назад

@@pedroivog.s.6870 The limit of the sequence itself converges to 0, but we’re talking about the summation of the sequence here.

@pedroivog.s.6870 10 месяцев назад

@@zhg4485 sorry, misread

@eig5203 10 месяцев назад

@@artemdown6609 Yeah, I guess we could say that there is some precision which we will never be able to achieve with e, but this seems even less achievable, since there is no computable algorithm which approaches it. I guess if it had a finite amount of digits, then it would be technically computable by hardcoding the digits into the states, so it should have infinite digits.

@danielm.6476 10 месяцев назад

@@artemdown6609OP is talking about something else. e is a computable number since there is an algorithm which approximates it to arbitrary precision. This BB-Sum however is uncomputable - there is no Algorithm for even approximating it beyond a certain degree. Huge difference

@evanhagen7084 10 месяцев назад

I have not had my mind blown to this scale ever. Quantum mechanics used to be the biggest mindfuck for me but this definitely takes the cake now. I swear we must be doing math wrong.

@Mutual_Information 10 месяцев назад

Lol yea complexity theory is an absolute brain buster. Though so is QM..

@BosonCollider 10 месяцев назад

Going back to quantum mechanics AFTER having learned complexity theory and looking at how it changes in quantum information is also a major mindfuck

@shadamethyst1258 10 месяцев назад

We're not doinɡ math wronɡ, it's just that our fields of math are vulnerable to ɡoedel attacks

@yash1152 10 месяцев назад

@bosoncolider quantum information and complexity oh lolol, on point... stunning thought

@blar2112 10 месяцев назад

Busy Beaver is not math, its meth

@mgostIH 10 месяцев назад

On the topic of computability, I personally suggest you to also take a look at Kolmogorov's Complexity, which has strong links to learning theory and AI via Solomonoff Induction and AIXI. It clarifies a lot on what learning actually means, even if Kolmogorov Complexity is uncomputable you still obtain a framework that works well if you have a computable approximator, like a large language model calculating entropy!

@Mutual_Information 10 месяцев назад

You have me figured out - Kolmogorov Complexity is on my list. I haven't refined my perspective on it yet though.. sounds like you have an interesting angle. I may message you on Twitter when the time comes to create the vid

@mgostIH 10 месяцев назад

@@Mutual_Information Sure! Would be happy to help you back, your RL playlist was really useful!

@Xnoob545 10 месяцев назад

@@mgostIH yo are you the geometry dash hacker person

@mrosskne 7 дней назад

why should he take a look at it?

@BryanLu0 6 дней назад

@@mrosskneHis other videos are about machine learning; that's why

@MusicEngineeer 10 месяцев назад

Whoa - this is mind-blowing! Up to now, I used to think about making up algorithms for producing insanely big numbers (like in the Numberphile videos mentioned at the start) as rather boring child's play - like: who can name the biggest number (always the child who answers last, of course - so what's the point, I thought). But I would not have thought that there is so much more depth to that. Like the existence of non-computable numbers and their connections to famous unsolved problems like the Riemann hypothesis.

@tylisirn 10 месяцев назад

Almost every number that exists is a non-computable number. We do not know what they are, we can not name them, we can't construct them, we can't work with them, because our math tools are computation and algorithms (hence, non-computable), but we know they exist out there, beyond the boundary of computation and that their space is so much larger that it is as if all our computable numbers are mere footnotes relegated to a corner of a page in comparison...

@kburtsev 10 месяцев назад

@@tylisirn What does it mean for number to exist? If we "don't know" that number in what sense it exists?

@tylisirn 10 месяцев назад

@@kburtsev They exist because the number line is continuous, it has no gaps. However computable numbers leaves gaps in the number line, therefore there has to be non-computable numbers that fill those gaps. And with the numbers we can compute, there are more gaps left in the number line than there are filled points. We do know a few individual non-computable numbers and some properties of them, but obviously can't compute what the exact values are. (For instance Chaitin's constant, which is a set of non-computable constants from information theory.)

@flameofthephoenix8395 7 месяцев назад

@@tylisirn Given infinite bits all numbers even ones that aren't computable can be stored, but finding the non-computable numbers is tricky.

@thewhitefalcon8539 2 месяца назад

@@tylisirnluckily all the numbers that anyone actually cares about, except for the busy beavers, are computable

@Niohimself 10 месяцев назад

I find the Busy Beaver function fascinating because it shows that there is a whole world of mathematics that our current math is not yet able to comprehend, and every day our horizon of conceivability broadens a little bit more in this infinite sea of undiscovered knowledge.

@thomasb4422 10 месяцев назад

Mathematitions must have felt the same way thousands of years ago. Like when Pythagoreans learned about irrational numbers.

@Stryfe52 10 месяцев назад

@@thomasb44223.14159..26535… oh dear Neptune, *it just keeps going!!!* 🤯

@davegonz6016 10 месяцев назад

This comment is poetic in a way. Like daedalus and icarus looking out over the (to them, infinite) sea after escaping the massive and complex labyrinth daedalus himself had built, and seeing how much larger it is than his creation. How much more there was out there.

@nahometesfay1112 10 месяцев назад

"Not yet" is misleading there are things about math we cannot know and we will not know. It has been proven that not all theorems can be proven no matter how hard we try.

@Fire_Axus 10 месяцев назад

@@thomasb4422 there are no feelings in mathematics.

@NoNameAtAll2 10 месяцев назад

technically we don't know if BB(googol) is bigger than TREE(googol) we can't prove at what point BB overruns TREE only that it does that eventually

@mgostIH 10 месяцев назад

I think it's pretty easy to see BB(googol) > anything humans can come up with, since you can describe any human algorithm in less than googol amount of states of turing machines.

@Mutual_Information 10 месяцев назад

Interesting, yea we land in the same place. By my understanding, the tree sequence is computable. As you point out, we have no clue where the cross over happens. I'd be quite surprised if it was so high though.. then again, intuition is pretty useless here

@piguyalamode164 10 месяцев назад

Mean, we can construct a good upper bound. Let us say we can make 3 turing machines: Turing machine 1 starts with a tape full of zeroes and makes Tree(google) encoded in binary at a specific known point on the tape(with the head some known relative distance x left of the first 1, say), and uses K states to do so Turing machine 2 shifts the tape x to the right. Can do anything else(should be doable with K_2

@rasmysamy2145 10 месяцев назад

We can prove it by creating a Turing machine which will write TREE(googol) ones with less than googol states, and this can trivially be done.

@Sgrunterundt 10 месяцев назад

The TREE sequence can be explained in a youtube video. A youtube video takes up much less than a googol bits. Thus a Turing machine producing the tree sequence can be coded with much less than a googol states. Thus BB beats Tree. And to say it is not even close would be an understatement. We can't compute the crossover point, but we can easily make upper limits.

@YOUnoobGER 10 месяцев назад

Formal Languages and Automata as well as first and second order logic was one of my favorite parts of my CS undergrad. Thanks for the nice video!

@kasai1575 10 месяцев назад

11:26 A closely related problem to the busy beavers is the maximum shifts function S, which counts the most shifts a turing machine of a certain size can make while still halting. If we calculated S(27) _without_ proving or disproving Goldbach's conjecture, we could actually (theoretically) use our result to prove or disprove Goldbach's conjecture. Simply run the turing machine that terminates if Goldbach's conjecture is false and see if the number of shifts surpasses S(27). If the machine terminates before making S(27) shifts, then obviously Goldbach's conjecture must be false. But if it terminates after making more than S(27) shifts, then Goldbach's conjecture must be true, because the machine has surpassed the largest number of finite steps a machine of that size can make. It must run forever, so there exists no counterexample for the conjecture.

@tcoren1 10 месяцев назад

Well, using it to prove goldbach conjecture wouldn't actually be possible though right, since probably like S(6) or something would already be bigger than the number of atom in our universe

@kasai1575 10 месяцев назад

@@tcoren1 True, that's why I said "theoretically." But this logic allows mathematicians to use busy beavers as an upper bound for how difficult a problem is to solve. The smaller the turing machine that halts upon disproving the problem, the "easier" the problem could possibly be.

@cara-setun 10 месяцев назад

But what if you determine S(27) and it’s a number that you would need to invent a new notation to even describe? How would you even run a machine that many steps to see if Goldbach was right?

@kasai1575 10 месяцев назад

@@cara-setun The shift function should always output an integer. Even if that integer is incomprehensibly large, and in reality would require special notation to represent, in _theory_ it is still just an integer. With enough space, time, and resources, you could theoretically represent this integer in a standard form. Whether this is actual possible in real life is a different story.

@tomblaise 10 месяцев назад

Perhaps in a trillion years there will still be people puzzling over how they might solve Goldbach's conjecture! Perhaps it is easier to just solve entropy and run a perfectly durable machine for an infinity-1 amount of time to calculate S(27).

@PureZOOKS 10 месяцев назад

This was the most clear and concise explanation of how turing machines work in relation to what a BB number is, thank you

@jorcyd 10 месяцев назад

Whoa ! This channel is such a Gem The 3b1b of Computer Science. First time seeing a turing machine in Manim. Grant yould be proud !

@Mutual_Information 10 месяцев назад

Thank you! That's quite a compliment! I'm happy to look as high quality as Manim. However, I'm not actually using Manim.. just an Altair-based personal library I've used. It's not nearly as a Manim

@tasheuathauc2723 10 месяцев назад

What's also really crazy is that a recent bachelor thesis reduced the bound of Busy Beaver to 745! One off from the Riemann Hypothesis machine! Meaning if we manage to reduce the bound by 1, we will have proven that RH is INDEPENDENT of our current understanding of mathematics; neither provable nor disprovable!! The name of the person is Johannes Riebel, the thesis is called "bachelor-thesis-undecidability-bb748". Scott Aaronson briefly mentions it as well in blog post 7388.

@Mutual_Information 10 месяцев назад

I'll check it out - thanks!

@schlega2 9 месяцев назад

This does not make sense. I assume the bound you are talking about is for BB(5) which is irrelevant to the RH machine. If you had an upper bound for BB(744) then that would decide the RH, not prove it undecidable. You just run that program and if it doesn't halt by the time it reaches your upper bound that would prove it doesn't halt.

@schlega2 8 месяцев назад

I've looked at the paper now. The bound is on the first value of the BB sequence that is uncomputable. I still don't see how lowering that bound would be relevant to RH. Showing that there exists an undecidable 744 state machine wouldn't say anything about the specific machine that's equivalent to RH.

@mrosskne 7 дней назад

which bound?

@moeboe6293 9 месяцев назад

Here's a fun (for some definition of "fun") exercise I did once: get a Turing machine simulator and initialize it with one of the leftover 5-state candidates of Busy Beaver TMs where people haven't figured out the long-term behavior yet. You can easily find such simulators and machine descriptions online. And then just run it and watch it. There is something fascinating about running these machines. Sometimes you think you see a pattern, but then you're still perplexed as to what they're doing with their 5 little states. And you wonder. Is this it? Am I already looking at the border between the computable and the noncomputable? Or more dramatically, as you watch the little 0s and 1s flash by, you wonder: am I now already standing at the abyss that separates what is fundamentally knowable from what is fundamentally unknowable? And you know you might already have plunged into, without knowing it. Because at some point, there is no knowing it.

@BananaNik 10 месяцев назад

One of the best videos I've seen on this topic. What a great, simple explanation without treating us like idiots.

@fynngilbert281 10 месяцев назад

Have you tried putting the Y-axis on a LOG-Scale tho?

@Mutual_Information 10 месяцев назад

haha oh duh

@treelight1707 10 месяцев назад

On your surprise of patrons. Your content is always great, and well presented. The topics are rarely presented elsewhere probably due to the scientific depth, other than basic information theory. What I enjoy the most, is the intuition you provide, such as with the probability distributions video, and the Fisher information video just to give a pair of examples. I would love to see this channel and its supporters grow.

@thegamerfromjuipiter7545 7 месяцев назад

Forget the busy beaver for a moment - this explained the halting problem better than most videos focused completely on that

@MelodiousThunk 10 месяцев назад

It's worth pointing out that other authors define the busy beaver as the maximum number of _steps_ that a halting n-state Turning machine can take, rather than the number of ones that it can write. E.g. Scott Aaronson uses the former in the paper you linked to, calling it "the most natural choice" (at the bottom of page 2).

@Mutual_Information 10 месяцев назад

Yea, this divide is unfortunate. I'll be introducing the shift function in the next video.

@PeterMeadows42 4 месяца назад

@@Mutual_Information Divide? Unfortunate? By 'divide' do you mean 'error'? Why don't you correct it?

@Mutual_Information 4 месяца назад

@@PeterMeadows42Because it's not an error. It's a preference which has people split. Some prefer to deal with the shift function and others prefer the ones function. They are both called Busy Beaver. I spoke with both people, so I just went with the historical version of "Busy Beaver', which is the one's function.

@mrosskne 7 дней назад

@@PeterMeadows42 Yes, it's an unfortunate divide. Are you slow?

@instagramsnapchat 10 месяцев назад

I'm not even into mathematics much (other than some youtube videos here and there) and found this relatively easy to follow and very interesting. Great job!

@nothayley 10 месяцев назад

What a fantastic video. I'm not really an expert in this, but I know a lot about it, and I didn't notice anything that was glaringly wrong, and your animation style and delivery are both excellent.

@TubeYou31415 10 месяцев назад

DJ, your video was both excellent and beatifully presented. I had seen the Numberphile video on the Busy Beaver and don't think I fully appreciated it. Your presentation was so clear -- especially with your rendering the the n-state Turing machine defintion! Thanks for sharing this content and I look forward to seeing more.

@Mutual_Information 10 месяцев назад

Thank you Greg, much appreciated. Plus good timing, since I'm currently working on the next one!

@elnekroxxiga 10 месяцев назад

This is the best explanation on Busy Beavers, hands down. Thanks

@jvthunder6548 10 месяцев назад

Im so excited when you posted!!! Your videos are truly one of a kind. Thx to u, I can grasp AI and RL concepts rly well!

@Mutual_Information 10 месяцев назад

thank you! And excellent, that's exactly my goal :)

@olbluelips 5 месяцев назад

I’ve had this in my watch later for a while. Great video! “A shot at the king” and onwards especially

@danielrhouck 10 месяцев назад

11:26 That’s why I prefer to think of the maximum shifts function S instead of busy beaver; it’s trivial (though computationally expensive) to go from S(27) to an answer on Goldbach. I think in theory you can do the same with busy beaver, but I’m not sure how.

@MeanSoybean 10 месяцев назад

that is an appreciably monstrous rate of growth

@Mutual_Information 10 месяцев назад

lol yea.. pretty much any description in words feel like an understatement.

@PeterJnicol 10 месяцев назад

This is very good. I am generally across this topic as as a spectator but I have never seen it put together as well as this, as well as learning a few new things. Looking forward to the follow-up.

@roddywishart4613 10 месяцев назад

I've seen a few videos on busy beavers but this video is the first one that I've actually understood what it's describing. Thanks for that

@ShakeyBox 10 месяцев назад

Morpheus : I've seen an agent punch through a concrete wall; men have emptied entire clips at them and hit nothing but air; yet, their strength, and their speed, are still based in a world that is built on rules. Because of that, they will never be as strong, or as fast, as you can be.

@tokajileo5928 10 месяцев назад

I loved this video for 2 reasons: nice clear explanation, and no background music.

@basimbaig 10 месяцев назад

What a delightfully wonderful piece of work! Thank you for this video. Keep up the impeccable work.

@Mutual_Information 10 месяцев назад

I'll keep the explanations up, but a topic like the Busy Beavers is hard to repeat..

@luiswi 10 месяцев назад

It's actually not too hard to get an intuition for why there can be no computable function that grows faster than bb. Let's consider the even more absurd function S(x) which counts the largest number of steps any halting turing machine with x states takes (instead of counting the number of 1s it produces). By definition S(x) has to grow faster than any computable function because if there was one that grows faster than S(x), we'd have an upper bound for how long we have to wait until we know that a turing machine can no longer possibly halt and the halting problem would be solved, which is impossible. Now this doesn't prove that bb(x) also grows this fast, but it would be very suprising if the growth rate of bb(x) and S(x) wasn't related in some way.

@BeC0o1 10 месяцев назад

Wow, am I glad to stumble upon your video. Thanks so much for making it, you fascinated the life out of me. The last 3 days I was reading and watching everything I could find about it. Haven't been so excited about math since my early 20s. A function that "breaks" math at

@Mutual_Information 10 месяцев назад

yes exactly! you feel how I feel

@jhoaopereyra 10 месяцев назад

this might be the definitive mind blower video of the BB topic I'll see ever. Now I can close this case in my mind to go find another conclusions in this awesome field.

@TheSalaho1 10 месяцев назад

That is a great video; the function you've created (the one like Knuth notation) is impressive. It's crazy to think about how the Busy Beaver sequence would outpace functions with a large number of arguments. We know that there's no limit to recursion arguments, and theoretically, you could dwarf the Ackermann function by adding just one argument alongside (a, b). Remarkably, Loader created a function that grows faster than TREE, using only one argument!

@tappetmanifolds7024 7 месяцев назад

Knuth up arrow involving single digit integers is a scary monster. Knuth up arrow involving n - digit integers is time for me to take a lie down.

@glass7923 9 месяцев назад

Watching this video not knowing what the hell a turing machine even is in this case is a wild ride.

@murmol444 10 месяцев назад

my favorite part of BB is that the mindblowing fact about its uncountability is incredibly easy to prove.

@KaewSaBa 10 месяцев назад

Such valuable content, please make more! I watch many Numberphile videos, and I love this as much.

@MTEXX 10 месяцев назад

Your explanation of a Turing machine is about the best I've ever seen.

@mgostIH 10 месяцев назад

Oh I saw your post on twitter some weeks ago, didn't expect you'd make a video out of this! Regarding 11:10, while it's true that in theory knowing about a specific BB number leads to us knowing what machines halt or not, this also requires actually running said machine for that many steps! So considering BB(27) is already larger than your question mark machinery, you don't really have any chance of accomplishing any of this even if an oracle told you the value.

@Mutual_Information 10 месяцев назад

ha yes totally true! For those reasons, yea, no open problems are gonna get cracked by working on computing BB of anything..

@tuures.5167 10 месяцев назад

Mind blowing - and extremely informative! You should consider submitting this to the Summer of Math Exposition 3, if you haven't already.

@crowman8905 10 месяцев назад

don't mind me, just gonna binge all your content over the next few days. love this vid

@Byron_Vega 10 месяцев назад

This was the first video I see on your channel and it was insanely cool, I can't wait to see more! I also appreciate the time you spent on the description of the video with the extra information and references.

@peterantonaros6461 9 месяцев назад

Awesome video, just turned me into a subscriber! From the aesthetics of the video, down to the content and calm presentation you deserve serious recognition. Nice work, this channel WILL blow up :)

@Mutual_Information 9 месяцев назад

Thank you Peter, means a lot and I hope you're right!

@tielessin 10 месяцев назад

That was such a good video and I'm a new subscriber now. If you keep producing such good content your channel's growth might surpass the busy beaver's growth.

@Mutual_Information 10 месяцев назад

haha! Talk about high expectation!

@multicolourmadness2712 10 месяцев назад

@@Mutual_InformationA few subscribers today, enough to collapse the earth into a black hole via information density within a couple weeks.

@eriktempelman2097 10 месяцев назад

Rewatching this now for the 3rd time. This just keeps getting funnier. Insane topic, hilarious narration. 3? stars

@joshshou5292 10 месяцев назад

glad to see this video exploded in views! have always loved this channel and thought it deserved more viewers !

@Bubatu7 10 месяцев назад

The way you express the mathematical concepts is really entertaining!

@hellNo116 10 месяцев назад

I just had my computability course. If my roommate wasn't sleeping next door, I would be screaming. What do you mean that we can't make claims about Σ(1000)?? What 🤯🤯🤯🤯 I am in awe right now

@Mutual_Information 10 месяцев назад

Lol I was actually shouting with my brother when I read about this thing. We're not too far apart in our experience!

@hellNo116 10 месяцев назад

@@Mutual_Information i will send it to my brother now to see your video after work. he is a mechanical engineer though. I don't how much it will blow his mind. I know he will be impressed.

@kinngrimm 10 месяцев назад

3 things to say 1. mind blown 2. are there any imaginatable suitable usecases should the BB of 5,6,7,... be found? 3. Would quantum computing be more suitable in these types of calculation than the current computers could handle them?

@modernkennnern 10 месяцев назад

I've seen Numberphile's video on BB a few times, but I didn't really get it until this video. Great video - first one of yours I've seen!

@miklov 10 месяцев назад

Very nice. I'm very curious about the 27 state machine. I hope to some day have time to read up on it. Thanks for cool content!

@konstantinsotov6251 5 месяцев назад

The reassuring thing is that "bad time complexity" does have a border for our normal computable problems, and if someone blames you for bad O(N) you can just say "not as bad as Busy Beaver"

@Mutual_Information 5 месяцев назад

Lol yea.. "Don't worry, my algo runs in O(BB(n))"

@iankrasnow5383 10 месяцев назад

I've binged the googology wiki years ago and had my mind blown by the fact that simple algorithms can generate numbers beyond any practical analogy in only 6 or 7 states. But what no one ever thinks to mention is, these massive numbers are actually islands of low entropy surrounded by many integers which can never be expressed by humans. Imagine you have a 10,000 state Turing machine. That's 10^10^4.96 possible configurations, which is much greater than the number of unique numbers which can be expressed, since many of these machines will be redundant or never halt. Imagine you covered the entire surface of the Earth (510,072,000 km^2) with hard drives, with areal storage capacities at today's benchmark of 1.1 terabytes (8.8 terabits) per sq inch, and instead of bits, each unit represents a single state on a Turing machine (up to 1.364*10^22 states in the algorithm). That's 10^10^23.79 possible configurations. So let's say 10^10^24 is a ridiculously high upper bound on unique numbers we can represent. This means that most of the numbers, for instance, between 10^10^26 and 10^10^27 cannot be represented without approximating them, in any shape or form even if we covered the whole planet with hard drives. And yet, we can describe Graham's number in only 19 symbols on a Turing machine.

@Mutual_Information 10 месяцев назад

Interesting! If I'm interpretting you correctly, something like BB(20) is describe simply (I just did it), but it's so ridiculously huge that virtually every number that might be considered 'close' to it.. can't be simply described.. because we don't have any machine.. or algorithm.. or anything that can describe it. Even doing things like BB(20) - BB(10) or any other combination of operations with familiar object won't work because it'll miss the vast, vast majority of numbers in that range.

@iankrasnow5383 10 месяцев назад

@@Mutual_Information Yeah, you said it much clearer than me!

@konstanty8094 10 месяцев назад

The video was both concise and entertaining. Just subscribed and bell'd. Your channel feel like it's gonna grow fast.

@carlod1605 10 месяцев назад

Just discovered your channel and I'm fascinated by your content

@robvdm 10 месяцев назад

Nice video! It’s worth noting that the existence of the Goldbachs conjecture Turing machine isn’t too surprising. I could write a rather simple computer program that simply goes through the even natural numbers in order exhaustively checking if I can write it as a sum of two primes, and halts when it arrives at a number that cannot be written as such. This program halts if and only if Goldbachs conjecture is false.

@3kelvinhong 10 месяцев назад

While it is true that Goldbachs conjecture trueness is not surprising with a BB halting, I think what's is more surprising is that both Goldbach and Riemann hypothesis can be equivalent to some n-states machine, which makes me thinking probably all unsolved mathematical conjectures are related to some n-state machines.

@robvdm 10 месяцев назад

@@3kelvinhong I agree that Reimann's Hypothesis is more interesting. Its a more complex conjecture, which I guess necessitates the ~1000 states necessary to disprove it. I didn't mean to suggest the video isn't interesting, if that's how my comment came across. Theoretically any conjecture that one could disprove by iterating through all possible counterexamples can be translated into a halting problem. Like much of mathematics, its a connection that one doesn't immediately think of, but once you hear it, it it seems very natural. The halting problem is hard because it basically gives you a shortcut to prove many (all?) conjectures.

@blacklistnr1 10 месяцев назад

Really interesting topic, thanks for making a video on it! Also, weird that there was no mention of compression since S(4) is the shortest way to express "make 13 ones" computationally.

@Mutual_Information 10 месяцев назад

Indeed.. Compression is another angle I'd love to cover.

@kiri101 10 месяцев назад

Cool video for someone like me who isn't in to complexity theory or math generally. I respect that you hired an expert to make sure you got it right.

@johnclark8359 10 месяцев назад

This is a great video, I'd love to learn more about the busy bee function. iI's fascinating!

@TabAtkinsJr 10 месяцев назад

I also prefer the s(n) definition of the busy beaver, where s(n) is the number of steps the longest-running machine takes before halting. This is more directly useful - if you have s(n), and an n-state machine, you can just run your machine for s(n) steps: if it halted, great; if it didn't, it'll never halt. The "max number of 1s" definition requires another level of indirection to actually be useful - many infinite-looping machines will produce less 1s than that, so you can't tell if *your* machine will infinite loop unless you're lucky enough to have it produce more than Σ(n) 1s. Instead you have to run *all* machines until every one that has produced Σ(n) or less 1s has either halted or been proven to infinite loop, then you can use that max number of steps to check *your* machine. That's a lot harder to work with! The two definitions are equivalent for the purpose of the proof, it's just that s(n) is more directly useful and clearer why it's uncomputable.

@Mutual_Information 10 месяцев назад

You're right and it took me awhile to realize this. Exactly, S(n) is useful because you know when to stop running the machine. I went with Sigma(n) honestly to avoid confusion. It's weird to compute the output of a computable function to the number of steps the TM ran for. I tried both and both of them brought a burden of extra explanation. In the follow up video, I'll discuss S(n).

@mrosskne 7 дней назад

No one actually builds turing machines so it doesn't matter

@zswu31416 10 месяцев назад

10:09 It likely overtakes the weird ? function at around 7 or 8. People have already proved that Σ(6)>15?, and I wouldn't be surprised that one extra state makes the number a lot bigger by adding extra recursion.

@MIKIBURGOS 10 месяцев назад

If I understood correctly, he was comparing Sigma(n) to n? with two dashes, not sure if you were also referring to that or just the simple question mark

@zswu31416 10 месяцев назад

@@MIKIBURGOS I was referring to that, because I said the "weird ? function" not the usual ?

@Cowtymsmiesznego 10 месяцев назад

@@zswu31416 There's ?, ? with a dash, and ? with two dashes

@christophhofer303 10 месяцев назад

very nice content! would love to see more about computability

@RomanNumural9 10 месяцев назад

You properly blew my mind. This is fascinating

@happypandaface710 10 месяцев назад

the only function larger than the busy beaver is the number of times my mind was blown after n seconds of this video

@sligocki 10 месяцев назад

Awesome overview. Thanks for the link to my blog post :) So exciting to see more people exploring Busy Beavers. Let me know if you want to collaborate on a future video. I'd be glad to chat about some of the stuff going on in the community :)

@Xnoob545 10 месяцев назад

you were the 256th comment I'd say that's a pretty cool number

@Mutual_Information 10 месяцев назад

Wow, great to hear from you! I'd love to chat for the follow up video. Reach me on LinkedIn? Searching "Duane Rich" should do the trick. Twitter DM works too (see description)

@hunternegron336 9 месяцев назад

12:02 I NEED that follow-up video! Great work!

@Mutual_Information 9 месяцев назад

It’s coming!!

@MathematicFanatic 10 месяцев назад

Fascinating and mind boggling stuff. I love the style of your Create()!

@bigcrazycarboy672 10 месяцев назад

I just took a class on computational theory last semester at ASU and it definitely blew my mind and most of my classmates. It would be absolutely terrible having to be the one to write the proof for some of these things! Was really cool to hear you talk about this stuff though, brought back some of the things I had forgotten about like church-Turing thesis.

@franciscopereira2993 10 месяцев назад

This was one if not the most interesting video on math i have ever seen.

@johnpearcey 10 месяцев назад

Excellent video. First time ever I've actually understood the Turing machine and it's significance. And one of my cats is named BB.

@mystifiedoni377 9 месяцев назад

I watched the numberphile/computerphile videos on busy beaver years ago and never really understood what it was until your explanation.

@nickr4957 10 месяцев назад

Surely if one can encode a brute force attack on the Goldbach Conjecture as a 27 state Turing machine so that halting means that it has found a counter example, then this is not that surprising.

@petergerdes1094 10 месяцев назад

Interestingly, the size of BB(8000) can't even be proved inside of ZFC (assuming ZFC is consistent). Roughly speaking, there is a Turing machine which searches for the existence of a proof of contradiction from ZFC + CON(ZFC) which will never be found if ZFC is genuinely truly consistent but since ZFC can't prove it's own consistency this fact can't be proved (so in particular, it's consistent with ZFC that BB(8000) is arbitrarily large...though technically it's a bit more complicated since if ZFC is actually consistent what you actually get are models where BB(8000) is non-standard).

@Mutual_Information 10 месяцев назад

Yea you're going deep!

@Adrian-me4qz 8 месяцев назад

This totally blew my mind, thanks for making this!

@Mutual_Information 8 месяцев назад

My pleasure!

@mecidgaliba2854 10 месяцев назад

Mind-blowing topic and excellent presentation. You got a subscriber!

@tuskiomisham 6 месяцев назад

"the solution is easy, if the computer does not halt within a reasonable time, i smash it with a large mallet" - Alan turing.

@nathanderhake839 10 месяцев назад

The busy beavers are on par with Rayo’s number they are crazy.

@alexeyvlasenko6622 8 месяцев назад

Seems like almost the same idea. Rayo's number is the largest finite number that can be defined in less than a certain number of symbols in a particular mathematical language, right? Busy beavers seem like the same thing, just using a different language to define the numbers.

@spencer1980 9 месяцев назад

I thought there were 50 states?

@patricktho6546 Месяц назад

It started with less and due to ppl it is only growing

@General12th 10 месяцев назад

This was an incredible video! I loved it!

@bariumselenided5152 8 месяцев назад

I love the name. It's kinda like the function is so much higher than us that it doesn't even understand our concepts of prestige and dignity. It's just toodling around, doing its thing

@Mutual_Information 8 месяцев назад

I can see the charm in it

@johnchessant3012 10 месяцев назад

The number 744 is prominent in the q-expansion of Klein's j-invariant, namely j(tau) = 1/q + 744 + 196884q + ... which manifests in Ramanujan's constant exp(pi*sqrt(163)) being approximately 640320^3 + 744. Coincidence?

@Mutual_Information 10 месяцев назад

"There are no coincidences in math!" - someone smart I think

@tonydai782 10 месяцев назад

I was going to say maybe, but after searching a tiny bit, the next term in the expansion is -196884/640320^3, which makes me a lot more inclined to believe that there is some connection there.

@godofrasiofernandez 10 месяцев назад

@@tonydai782i think it was related to representation of the monster group but i dont remember

@noel.friedrich 10 месяцев назад

could it be that BB(5) is in fact uncomputable since there may be one machine in there that never halts and we're unable to prove that it never halts because turing? If this is the case, this machine "layout" may be inside all BB(n) where n is larger or equal than 5, correct? Making all of them uncomputable?

@joshuahudson2170 10 месяцев назад

BB is outside the computable. There must be some BB(n) for which your idea holds.

@Cowtymsmiesznego 10 месяцев назад

I don't think that's true? BB(n) for a fixed n should easily be computable? It'll be a finite number of TMs on a single input (all 0s) - so there will be an upper bound on how many steps they can take before looping - and therefore we can just check all of them. Only BB as a function is uncomputable - i.e. there is no algorithm that can ingest n and calculate BB(n).

@joshuahudson2170 10 месяцев назад

@@Cowtymsmiesznego BB(27) requires solving a famous unsolved conjecture.

@Cowtymsmiesznego 10 месяцев назад

@@joshuahudson2170 Sure, but how does that make it uncomputable? Besides, as mentioned in the video, there could (theoretically) be a nonconstructive way of calculating BB(27) that doesn't solve Goldbach's conjecture. Edit: nvm I think I'm wrong and you're right - there must exist n where BB(n) becomes uncomputable?

@franciscoabusleme9085 10 месяцев назад

Glad that I found this channel, quality content

@xMartyZz 5 месяцев назад

I don't know how I wondered into math RU-vid but you do an excellent job presenting such complex information in a way that I, whose mathematical knowledge ends with calculus 101, is able to comprehend the beauty/insanity of the concept. Great video, thank you!

@Mutual_Information 5 месяцев назад

Awesome Marty - exactly what I'm hoping for

@user-un1fq7uz7z 10 месяцев назад

very good video. do we have some Busy Beavers that could have proven some theories if only we managed to “compute” them?

@Mutual_Information 10 месяцев назад

Aaronson discusses this. He says.. if we're given the value of Shift(27) (this is the shift function, which is the total number of steps taken by the machine, rather than the count of 1's written), then that reduces Goldbach to a finite procedure. You just run the GoldBach machine for Shift(27)-steps. If it hasn't halted by then, you know GoldBach is true! But this is not a practical route at all

@user-un1fq7uz7z 10 месяцев назад

@@Mutual_Information Wow... Still it is crazy that it hypothetically would work

@tyzonemusic 10 месяцев назад

Very cool video, but I'm not getting the "There exists a 27-state machine that halts iff..." part; in that case, can't you just construct a trivial machine that halts on each internal state no matter the input obtained from the tape? EDIT: nvm I think I got it; there's a SPECIFIC 27-state machine, which halts iff Goldbach's Conjecture is false

@steffenbendel6031 10 месяцев назад

Exactly, it just tests all numbers and holds if it finds a counter example.

@andreas.soderlund 10 месяцев назад

Nicely explained, really. The subject is fascinating, like a science fiction movie can be, but when it goes towards "if we can compute something than cannot be computed, we disprove the Riemann hypothesis", then I think it's worth taking a step back so things doesn't turn into navel-gazing, like any area when something gets more and more theoretical (string theory for example) and less connected to what I hope is the actual point of science, especially in times like these - applying its knowledge to improve society and people's lives, not just "do something because we can". This has been a realization of mine after spending a lot of time on things like this. It's interesting, satisfying, comfortable, but in the end rather pointless, as a few world champions have described after their pursuit have ended. We need the connection to reality, so we can see the ever-increasing questions and lack of answers as a hint, instead of pushing forward in vain hope.

@ihebbendebba2978 3 месяца назад

I just discovered your channel and it is truly awesome

@azophi 10 месяцев назад

I’m am so confused, why can’t you just multiply f(x) = BB(n)* n ? My mind is just blown lol

@Mutual_Information 10 месяцев назад

Well then f(x) wouldn't be computable. It's about BB(n) vs computable functions - there are rules to the game!

@azophi 10 месяцев назад

@@Mutual_Information but you can totally compute it though 🤔 just multiply busy beaver by n Sorry I’m not trying to be argumentative I just don’t get it lol

@Mutual_Information 10 месяцев назад

@@azophi not argumentative at all :). Let's say you wanted to start computing f(n) = BB(n) * n, starting with n = 1, n=2, etc.. Before you can compute BB(n) * n, you'll need to compute BB(n). And that's the problem. There's no finite procedure that will produce the BB(n) number.. because the halting problem is basically blocking you. And so the difficulty is eased by adding the multiply-by-n step.

@azophi 10 месяцев назад

@@Mutual_Information i see that does actually make sense Busy beavers is not (generically) computable just because it requires the halting problem to be solved generically to compute it So we can compute simple BBs 1-4 , but it is impossible to make a generalized algorithm to calculate busy beaver .

@arduous222 Месяц назад

You know, studying astrophysics sometimes really drives you insane and makes you question the meaning of existence. Whenever I feel that way, math has been a haven, it has been simple playground in abstract space. But now I feel the same existential dread from math as well. Thank you very much!

@Erotemic 10 месяцев назад

That was the best Turning Machine explanation I've seen.

@froyocrew 10 месяцев назад

why can't we prove sigma(1000) is some natural number k. If the number of ones on a tape of any turing machine is discrete then it must be a natural number, ergo sigma (1000) = k. The only way this falls apart is if there are no 1000 state turing machines that halt which seems like you could simply design a trivial example

@Mutual_Information 10 месяцев назад

I'll cover that in an upcoming video.. it's a bit of a head bender.

@lydianlights 10 месяцев назад

So I think what you are saying is correct -- some natural number k exists that satisfies S(1000) = k. That is true and provable. But, I think the point being made is that for some _specific_ value of k, there is a true statement: S(1000) = k. This is a true statement that must exist, and yet it cannot ever be proven to be true (assuming S(1000) is not computable).

@froyocrew 10 месяцев назад

@@Mutual_Information awesome I'm excited to see it, subbed!

@froyocrew 10 месяцев назад

@@lydianlights but the statement is "there exists". That's the issue, you are using a logical quantifier and thus if it must exist by definition then the statement has been proved true. I think it's more along the lines of not being able to determine what the value is, not proving its existence which is trivial due to the function's range (natural numbers)

@lydianlights 10 месяцев назад

@@froyocrew Yes I think what you're saying is right, but there is another layer to it. Think of it like this -- there is an infinite list of statements: S(1000) = 1 : False S(1000) = 2 : False S(1000) = 3 : False ... S(1000) = 10000 : False S(1000) = 10001 : False S(1000) = 10002 : False ... S(1000) = - 1: False S(1000) = : True S(1000) = + 1 : False S(1000) = + 2: False ... We can prove that exactly one of these statements must be true. However, we can never prove the individual statement S(1000) = to be true. Even if we happen to pick the correct statement to try to prove. Put another way, even if we "accidentally" pick the right statement S(1000) = 9999999999999... that is in fact true, It will still be impossible to prove that it is true. Basically this means that there are true mathematical statements that are impossible to prove. It's related to Godel incompleteness.