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.

What is a Turing Machine?

Prerequisites: Minimal

In your time in the BBChallenge collaboration, the single most important object that you will encounter is the Turing machine; it is the focus of our study. To put it simply, a Turing machine (also abbreviated to "TM"), is a hypothetical computer which has been proven to be able to simulate any computer algorithm. Consider a sequence of infinitely many zeroes in both directions, we call this to tape. We also need a machine head which is capable of traversing along the tape, which can be thought of as an integer index. When we first run the machine, it reads the value directly under the head, and also starts in a specific internal state (we denote these states alphabetically, with the machine starting in state A), and will reference a set of rules given the state and read-value. The rule will then tell it to write a certain value to the tape under the head, move either left or right, and switch to a specific new state. There may also be instructions which tell the machine to stop running entirely, and the question of whether or not the machine can halt is a foundational one.

Suggested Readings:

• Blog Post on BBChallenge TM Formatting
  • We use a very specific notation for our TMs, this is crucial information

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]