The Boundary of Computation

There is a limit to how much work algorithms can do.

SOCIAL MEDIA

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

REFERENCES

[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

[4] T. Radó. "On non-computable functions". Bell System Technical Journal. 41 (3): 877–884, 1962

3749

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

[Mutual_Information]

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.

[maxturgeon]

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

[ujovmp]

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

[MogaTange]

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

[JSorngard]

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.

[Cxntrxl]

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

[etatauri]

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

[tuskiomisham]

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

[andie_pants]

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

[nUrnxvmhTEuU]

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.

[evanhagen]

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.

[NoNameAtAll]

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

[YOUnoobGER]

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!

[Niohimself]

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.

[PureZOOKS]

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

[moeboe]

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.

[tasheuathauc]

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 Scott Aaronson briefly mentions it as well in blog post 7388.

[thegamerfromjuipiter]

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

[kasai]

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.

[mgostIH]

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!