Can AI Solve the Busy Beaver Problem? Exploring Computational Approaches and the Limits of Intelligence

Introduction

Since Rado introduced the Busy Beaver problem in 1962 [1], many scholars have sought to solve this fun game [2,3,4,5]. This problem, created by Rado, uses Turing Machines to demonstrate the halting problem. The halting problem aims to solve whether a given Turing machine’s initial state will eventually halt[6]. In his paper, Turing himself proved that no general algorithm can solve such a problem, meaning each case must be handled separately [7]. Busy Beaver is one such case. The Busy Beaver problem goes as follows: There exists an infinite tape binary Turing Machine whose task is to print the maximum number of 1’s(marks) and then halt[8]. Busy Beaver 1, can be denoted by BB(1), representing a 1-state Turing machine; BB(2) would then represent a 2-state Turing machine. The first three busy beavers were solved by Rado and Lin[9]. BB(1) having one 1’s, BB(2) with four 1’s, and BB(3) six 1’s. BB(4) wouldn’t be solved until 1964 by Brady, who discovered there were thirteen 1s [9]. Since then, many scholars have been trying to solve BB(5) and higher [10, 11, 12]. For example, [13] had reached 4,098 marks for BB(5) in 1990. 

The Busy Beaver problem doesn't extend to just papers; in recent years, interest in the game has spread to online spaces and forums. Like [14], sharing ideas in 2022 on potential angles to take the Busy Beaver problem. With the help of spaces that foster online collaboration, in 2025, almost 40 years after a new BB(5) was announced, BB(5) was finally solved and proved using the Coq proof assistant[15]. This BB(5) contains a maximum of 47,176,870 marks. Now, BB(6) is the current target, but research suggests that the empirical lower bounds exceed 10^36,534 and, as a result, will be more challenging to find than its predecessors[15]. 

AI has advanced significantly in recent years[16, 17]. Specifically, in the field of LLM-based generative models like ChatGPT. With growing interest in this space, academics have been exploring its capabilities for solving math-based problems[18, 19].  In [20], they explored how MathGPT.org, Math-GPT.ai, and StudyX.ai perform in solving Olympiad-style, Python-based questions. Results indicate that these models not only managed to solve said questions but also provided a step-by-step guided explanation on the approaches used, making it a formidable tool for learning. [21] took a similar approach, looking at ChatGPT-3.5, ChatGPT-4, and Google Bard. The paper challenged these LLMs to solve a range of mathematical problems. These LLMs succeed in simpler mathematical and logical problems, but they become less reliable as the difficulty of these problems increases. 

With AI only continuing to advance, could such tools become a beacon in assisting the search for BB(6)? This Literary Review aims to answer: RQ1: What are some ways in which the Busy Beaver problem is being solved, and how are people thinking about computing it? RQ2: Is it possible for AI to reach a place where it can solve such complex problems? Through these questions, the aim is to understand the scope of BB(6), what sort of current techniques are implemented and if AI can assist in this process.