User:Autumn-Pan/Busy-Beaver-Resource-Guide
This page collects reading materials and learning resources, ranging from beginner-friendly texts to more cutting-edge research. It is highly recommended to look through this page as a beginner, since introductory texts are curated here. Commentary and original documentation will also be provided. Every outside link, including citations, is chosen carefully to not only cite sources, but serve as links to outside resources. The primary purpose for this article is to summarize parts of Busy Beaver research, and to generously append links to outside resources and readings to act as a starting point for learners.
Getting Oriented
This is a collection of general background knowledge on the Busy Beaver challenge and essential information for all niches. All resources linked here are considered beginner level and require minimal background knowledge to understand.
Background
Prerequisites: Turing Machines
To begin our work with the Busy Beaver function, we must first understand what it is about. The Busy Beaver Function BB(n) measures the maximum runtime of an n-state, 2-symbol Turing machine. It is a famous example of an uncomputable function, meaning no general algorithm can compute arbitrary values of BB(n). The general methodology for computing values of BB(n) requires us to decide whether or not all n-state 2-symbol Turing machines halt in search for the one with the longest runtime. We call unsolved machines Holdouts, and we solve holdouts with a variety of methods. Automated computer programs called Deciders, manually solving holdouts, and simulating holdouts, have all been critical to this project.
Suggested Readings:
- Official Story page for BBChallenge
- This page was created while BB(5) was the main focus of BBChallenge, and is currently outdated. Nevertheless, it acts as a solid introduction to understanding this community.
- Quanta Magazine Blog about BB(n)
- Writes about research efforts, and attempts to simplify some relevant concepts and explain them with analogies.
In addition to the official story, a number of YouTube videos have also been published on the Busy Beaver problem.[1][2]
We study the Busy Beaver function because it is uncomputable [3]. That is, no algorithm can determine any given value of BB(n) in a finite number of steps. In fact, many formal systems that we use to study mathematics, like Peano arithmetic and Zermelo-Fraenkel set theory[4], fall short of being able to decide all values of BB(n).
- We're actually having ongoing discussions about its independence from Peano arithmetic, which is open to new contributors. [5]
First Steps
The majority of our discussions happen on our discord server [6]. Furthermore, we now have a subreddit which is also open to everyone [7]. If you have any specific questions, feel free to ask them in our "beginners" channel [8]