The Boundary of Computation

The machine learning consultancy: https://truetheta.io
Want to work together? See here: https://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: https://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: https://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", https://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, https://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.) https://plato.stanford.edu/archives/s...

[6] Wikipedia contributors. "Busy beaver" Wikipedia, 2023, https://en.wikipedia.org/wiki/Busy_be...

[7] P. Michel. "The Busy Beaver competition: a historical survey". 2019. https://arxiv.org/abs/0906.
3749

[8] Wythagoras (Username), "The nineteenth Busy Beaver number is greater than Graham's Number!", googology.fandom.com, 2016, https://googology.fandom.com/wiki/Use...!

[9] S. Ligocki, "BB(6, 2) is greater than 10^10...^10", 2022, https://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