What happens at the Boundary of Computation?

Published: 21 August 2023
on channel: Mutual Information
69,618
3.7k

The machine learning consultancy: https://truetheta.io
Join my email list to get educational and useful articles (and nothing else!): https://mailchi.mp/truetheta/true-the...

In this video, we look inside the bizarre busy beaver function.

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  

REFERENCE NOTES

As mentioned, [1] was the primary source. The first video and this one were originally inspired by reading [1], so many of the ideas can be traced to that point. Anyone still interested should continue their search there. Sources [3]-[4] were essential for understanding the exact nature of the busy beaver and champion machines. In fact, I should have also thanks Pascal Michel in the video. He has maintained a detailed recorded of which machines were champions at which points and I found myself referencing it regularly. Sources [5]-[7] plus some conversations with the author were essential for my understanding of the Collatz-like behavior.

REFERENCES

[1] S. Aaronson, "The Busy Beaver Frontier", https://www.scottaaronson.com/papers/...

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

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

[4] P. Michel. "Problems in Number Theory from the Busy Beaver Competition". Logical Methods in Computer Science
Vol. 11(4:10), pp. 1–35, 2015

[5] S. Ligocki, "BB(6, 2) is greater than 10^10...^10", 2022, https://www.sligocki.com/2022/06/21/b...

[6] S. Ligocki, "Collatz-like behavior of Busy Beavers", 2021, https://www.sligocki.com/2021/07/17/b...

[7] S. Ligocki, "BBB Complex Collatz-like Behavior", 2021, https://www.sligocki.com/2022/02/22/c...

TIME CODES
0:00 Introduction
0:42 Reviewing the Basics
2:11 How does it grow faster than anything computable?
2:58 Using Collatz for Absurd Growth
3:59 Collatz in the 5-state machine
7:31 Exponential Collatz in the 6-state machine
9:05 The Busy Beavers answer famous open problems
11:23 The Busy Beavers are unknowable by any mathematical system
14:10 The Conjectures
14:26 Thank You's


Watch video What happens at the Boundary of Computation? online without registration, duration hours minute second in high quality. This video was added by user Mutual Information 21 August 2023, don't forget to share it with your friends and acquaintances, it has been viewed on our site 69,618 once and liked it 3.7 thousand people.