BusyBeaverWiki - User contributions [en]

User:Autumn-Pan

2026-02-27T23:22:33Z

Autumn-Pan:

Hi, I'm Autumn

==== About Me ====
Discord: dihedralgroup
Email: pan662607@gmail.com

Number theorist, C/ASM Programmer

I work on BB(6), I design deciders. Please send me an email or DM for any and all inquiries

==== My Works ====

* [https://wiki.bbchallenge.org/wiki/User:Autumn-Pan/Further-Reading Further Reading for Beginners]

* [https://wiki.bbchallenge.org/wiki/1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB--- 1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---]

*[https://wiki.bbchallenge.org/wiki/User:Autumn-Pan/Busy-Beaver-Resource-Guide Further Reading (Replacement)]

*Retrograde Analysis of Turing Machines: An extension of Backwards Reasoning using invariants (Mathematical results complete, Manuscript in progress)

User:Autumn-Pan/Busy-Beaver-Resource-Guide

2026-02-27T21:46:21Z

Autumn-Pan: /* Getting Oriented */ add some stuff

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: '''
* [https://bbchallenge.org/story#the-busy-beaver-function-bb 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.
* [https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/ 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.[https://www.youtube.com/watch?v=CE8UhcyJS0I][https://www.youtube.com/watch?v=rmx3FBPzDuk]

We study the Busy Beaver function because it is uncomputable [https://www.comap.com/blog/blog-2/item/what-does-uncomputable-mean-busy-beaver-problem]. 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[https://arxiv.org/abs/1605.04343], 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. [https://discord.com/channels/960643023006490684/1466652214247559198]

=== First Steps ===
The majority of our discussions happen on our discord server [https://discord.gg/nJRPHFQwFQ]. Furthermore, we now have a subreddit which is also open to everyone [https://www.reddit.com/r/BBChallenge/]. If you have any specific questions, feel free to ask them in our "beginners" channel [https://discord.com/channels/960643023006490684/1448375857046360094]

User:Autumn-Pan

2026-02-27T21:20:31Z

Autumn-Pan:

User:Autumn-Pan/Head-Position-Reachability

2026-02-27T02:13:43Z

Autumn-Pan:

Head-position reachability is a proposed framework based on [[Backward Reasoning]] that aims to decide non-halting Turing machines.

== History ==
* In January 2026, a [[BB(6)]] holdout was informally solved with concepts based on Backward Reasoning
* By March 2026, the ideas explored in January were formalized by Autumn Pan and RobinCodes

== Disclaimer ==
Information on this framework is limited and delayed due to the paper being actively written and unpublished

User:Autumn-Pan/Busy-Beaver-Resource-Guide

2026-02-24T18:53:07Z

Autumn-Pan: /* Getting Oriented */

User:Autumn-Pan/Busy-Beaver-Resource-Guide

2026-02-24T18:36:12Z

Autumn-Pan: /* Getting Oriented */

User:Autumn-Pan/Busy-Beaver-Resource-Guide

2026-02-24T15:18:02Z

Autumn-Pan: Create page content

User:Autumn-Pan/Further-Reading

2026-02-24T15:01:57Z

Autumn-Pan: /* Note */ add note on retirement

This article is a maintained list of resources for beginners to read. It's highly recommended to join the [https://discord.gg/Gph5X2hX discord server].

For deciders:
* See [https://arxiv.org/abs/2509.12337v1 our arXiv preprint]
* [https://wiki.bbchallenge.org/wiki/Decider Wiki page on deciders]
* [https://www.arxiv.org/abs/2504.20563 Turing machines deciders, part I (arXiv)]

For Analysis:
* See Shawn Ligocki's [https://www.sligocki.com/ blog]
* For analysis in particular, see his post [https://www.sligocki.com/2021/07/17/bb-collatz.html here]
* [https://wiki.bbchallenge.org/wiki/Analysis_Tools_and_Techniques Analysis Tools and Techniques]

Visualizers:
* https://fiery.pages.dev/turing/
* https://bbchallenge.org
* https://azertywastaken.github.io/TuringMachinesSimulator/tm_simulator

Misc.
* Try sending a message in [https://discord.com/channels/960643023006490684/1448375857046360094 our Discord server]
* [https://wiki.bbchallenge.org/wiki/Turing_machine#Standard_text_format Standard Text Notation for Turing Machines]

== Note ==
This page is being overhauled starting 24 Feb. 2026. A replacement page will be linked soon, and this page will be retired.

User:Autumn-Pan/Further-Reading

2026-02-24T15:01:07Z

Autumn-Pan:

This article is a maintained list of resources for beginners to read. It's highly recommended to join the [https://discord.gg/Gph5X2hX discord server].

For deciders:
* See [https://arxiv.org/abs/2509.12337v1 our arXiv preprint]
* [https://wiki.bbchallenge.org/wiki/Decider Wiki page on deciders]
* [https://www.arxiv.org/abs/2504.20563 Turing machines deciders, part I (arXiv)]

For Analysis:
* See Shawn Ligocki's [https://www.sligocki.com/ blog]
* For analysis in particular, see his post [https://www.sligocki.com/2021/07/17/bb-collatz.html here]
* [https://wiki.bbchallenge.org/wiki/Analysis_Tools_and_Techniques Analysis Tools and Techniques]

Visualizers:
* https://fiery.pages.dev/turing/
* https://bbchallenge.org
* https://azertywastaken.github.io/TuringMachinesSimulator/tm_simulator

Misc.
* Try sending a message in [https://discord.com/channels/960643023006490684/1448375857046360094 our Discord server]
* [https://wiki.bbchallenge.org/wiki/Turing_machine#Standard_text_format Standard Text Notation for Turing Machines]

== Note ==
Full disclosure: this page is being overhauled starting 24 Feb. 2026.

User:Autumn-Pan/Busy-Beaver-Resource-Guide

2026-02-24T15:00:05Z

Autumn-Pan: Created page with ""

User:Autumn-Pan

2026-02-24T14:56:01Z

Autumn-Pan: /* About Me */

User:Autumn-Pan/Head-Position-Reachability

2026-02-23T15:53:43Z

Autumn-Pan: add history

User:Autumn-Pan/Head-Position-Reachability

2026-01-23T03:16:17Z

Autumn-Pan: Created page with "Head-Position Reachability is a variant of backwards reasoning that seeks to decide nonhalting Turing machines."

Head-Position Reachability is a variant of backwards reasoning that seeks to decide nonhalting Turing machines.

User:Autumn-Pan/Further-Reading

2026-01-05T14:59:19Z

Autumn-Pan: add azerty visualizer

User:Autumn-Pan/Further-Reading

2025-12-29T02:08:48Z

Autumn-Pan: add Turing machines deciders, part I

This article is a maintained list of resources for beginners to read. It's highly recommended to join the [https://discord.gg/Gph5X2hX discord server].

For deciders:
* See [https://arxiv.org/abs/2509.12337v1 our arXiv preprint]
* [https://wiki.bbchallenge.org/wiki/Decider Wiki page on deciders]
* [https://www.arxiv.org/abs/2504.20563 Turing machines deciders, part I (arXiv)]

For Analysis:
* See Shawn Ligocki's [https://www.sligocki.com/ blog]
* For analysis in particular, see his post [https://www.sligocki.com/2021/07/17/bb-collatz.html here]
* [https://wiki.bbchallenge.org/wiki/Analysis_Tools_and_Techniques Analysis Tools and Techniques]

Visualizers:
* https://fiery.pages.dev/turing/
* https://bbchallenge.org

Misc.
* Try sending a message in [https://discord.com/channels/960643023006490684/1448375857046360094 our Discord server]
* [https://wiki.bbchallenge.org/wiki/Turing_machine#Standard_text_format Standard Text Notation for Turing Machines]

User:Autumn-Pan

2025-12-28T23:32:11Z

Autumn-Pan: Added works section

Hi, I'm Autumn

==== About Me ====
Discord: dihedralgroup (always feel free to dm or ping)
Email: pan662607@gmail.com

Number theorist, C/ASM Programmer

I work on BB(6), performing analysis on higher level rules of holdouts and writing optimized simulators of various types. I've also worked on BB variants and derivative projects, including those in IUTT.

==== My Works ====

* [https://wiki.bbchallenge.org/wiki/User:Autumn-Pan/Further-Reading Further Reading for Beginners]

* [https://wiki.bbchallenge.org/wiki/1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB--- 1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---]

User:Autumn-Pan

2025-12-28T23:27:29Z

Autumn-Pan: rewrite bio

Hi, I'm Autumn

Discord: dihedralgroup (always feel free to dm or ping)
Email: pan662607@gmail.com

Number theorist, C/ASM Programmer

I work on BB(6), performing analysis on higher level rules of holdouts and writing optimized simulators of various types. I've also worked on BB variants and derivative projects, including those in IUTT.

TMBR: December 2025

2025-12-12T13:21:35Z

Autumn-Pan: add news article: Brennan, J. 14 July 2025

{{TMBRnav|November 2025|January 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

This is the last edition of TMBR this year. 2025 was a very productive year for [[Busy Beaver Challenge|BBChallenge]]: about 60% of the next domain, [[BB(6)]], was solved. Furthermore, new champions were discovered for BB(6), [[BB(7)]] and [[BB(4,3)]]. Many models of computation other than Turing Machines were also explored - most notably [[Fractran]] and [[Instruction-Limited Busy Beaver]]. Some new methods were developed, such as [https://discord.com/channels/960643023006490684/1028746861395316776/1442964185599447152 mxdys's new version of FAR.]

== This Year in Beaver Research <small><sub>(TYBR - "Thank You Beaver Researchers!")</sub></small> ==

=== Holdouts Reductions. ===

* [[BB(6)]] - Reduced from '''3571''' to '''1416''' holdouts. Hence, 2155 machines were solved this year. This is a '''60% reduction.'''
* [[BB(7)]] - '''Enumeration was completed''', the number of holdouts was reduced from an initial 85,853,789 to '''20,405,295''' machines, a 76.23% reduction.
* [[BB(4,3)]] - Reduced from 460,916,384 to 9,401,447 holdouts, a '''97.96% reduction.'''
* [[BB(3,4)]] - Reduced from 434,787,751 to 15,136,283 holdouts, a '''96.52% reduction.'''
* [[BB(2,5)]] - Reduced from '''217''' to '''75,''' a '''65.43% reduction.'''
* [[BB(2,7)]] - '''Enumeration started''', 50K of the 1M subtasks have been enumerated ('''5%''').

=== Champions. ===
* [[BB(6)]] - On 16 June 2025, mxdys discovered {{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB|halt}}, running for 10 ↑↑ 11010000 steps. This was surpassed on 25 June when mxdys discovered {{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}, a TM which runs for <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8.10237</math> steps.
* [[BB(7)]] - Within three days of the start of the enumeration of BB(7), three champions were discovered. The first two were discovered by [[User:Sligocki|Shawn Ligocki]]: {{TM|1RB0RF_1LC0RE_1RD1LB_1LA1LD_0RA0LE_1RG0LB_1RZ1RB|halt}} with a sigma score of about 10 ↑↑ 22 and {{TM|1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC|halt}} with a sigma score of about 10 ↑↑ 35. This was followed by the discovery of {{TM|1RB0LG_1RC0RF_1LD1RZ_1LF0LE_1RA1LD_1LG1RE_0LB0LB|halt}}, achieving a sigma score of about 10 ↑↑ 46, by Terry Ligocki. On 10 May 2025, Pavel Kropitz discovered {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF|halt}}, a TM which runs for over <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> steps.
* [[BB(4,3)]] - [[User:Polygon|Polygon]] identified a new [[BB(4,3)]] champion with a score of over <math>10 \uparrow^{4} 4</math> ({{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD|halt}}). This TM was first proven to halt by Pavel Kropitz in May 2024, but its runtime was not known at the time.

=== New Methods. ===

* New FAR using DFA generator by mxdys.<sup>[https://discord.com/channels/960643023006490684/1028746861395316776/1442964185599447152 <nowiki>[1]</nowiki>][https://discord.com/channels/960643023006490684/1239205785913790465/1443990614483013632 <nowiki>[2]</nowiki>]</sup>

TODO

=== Meta. ===
TODO

=== BB Adjacent. ===
* [[Instruction-Limited Busy Beaver]] was introduced and calculated up to BBi(7).
* [[Reversible Turing Machine]] Busy Beaver values were calculated up to BB<sub>rev</sub>(5).
* [[Terminating Turmite]]s (Relative Movement Turing Machines) were introduced.
* John Tromp introduced the <math>BB \lambda _1(n)</math> function for [[Busy Beaver for lambda calculus#Oracle Busy Beaver|Busy Beaver for lambda calculus with an oracle]] and computed it up to <math>BB \lambda _1(22)</math>.
* Instruction-Limited Greedy Busy Beaver gBBi(n) and an [[Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants|Instruction-Limited variant]] of the [[Blanking Busy Beaver]] (BLBi(n)) were introduced. gBBi(n) was computed up to n = 13 and BLBi(n) was computed up to n = 7.
* @savask shared the [[Bug Game]] (and fast-growing <math>Bug(H,W)</math> function).
* [[Fractran|Busy Beaver for Fractan]] (BBf) was introduced on 1 Nov by Jason Yuen.<sup>[https://discord.com/channels/960643023006490684/1362008236118511758/1433148101170040924]</sup> Exact values have been proven up to BBf(19) = 370 and exhaustive enumeration has been run up to size 21 (with BBf(21) ≥ 31,957,632 and 587 holdouts).
* [[Cyclic Tree Busy Beaver]] (CTBB) was introduced by @Jack on 14 Nov.<sup>[https://discord.com/channels/960643023006490684/1438694294042181742]</sup> The exact value is known for CTBB(2) = 5 and lower bounds have been found up to size 7 with CTBB(7) > 4↑↑↑↑(4↑↑↑3).
TODO

=== In the News. ===
* 6 January 2025. It Boltwise. [https://www.it-boltwise.de/durchbruch-im-busy-beaver-problem-eine-neue-aera-der-mathematik.html Durchbruch im Busy Beaver Problem: Eine neue Ära der Mathematik] (German) (English: Breakthrough in the Busy Beaver problem: A new era of mathematics).
* 1 July 2025. The Quanta Podcast. [https://discord.com/channels/960643023006490684/1285212639399776256/1389643208811745310 How Amateurs Solved a Major Computer Science Puzzle].
* 2 July 2025. Manon Bischoff. Spektrum. [https://www.spektrum.de/news/mathematik-die-sechste-fleissige-biber-zahl-ist-gigantisch/2274249 Wie der sechste Fleißige Biber die Mathematik an ihre Grenzen bringt].
* 7 July 2025. Karmela Padavic-Callaghan. New Scientist. [https://www.newscientist.com/article/2487058-mathematicians-are-chasing-a-number-that-may-reveal-the-edge-of-maths/ Mathematicians are chasing a number that may reveal the edge of maths]. (Paywalled)
* 9 July 2025. David Roberts. [https://thehighergeometer.wordpress.com/2025/07/09/bb547176870-bb6-is-astronomically-larger/ BB(5)=47,176,870: BB(6) is … astronomically larger].
* 11 July 2025. New Scientist podcast [https://www.newscientist.com/podcasts/how-geoengineering-could-save-us-from-climate-disaster-have-we-broken-mathematics-why-exercise-reduces-cancer-risk/ episode 311]. Discusses mxdys's [[BB(6)]] pentation result "We’re brushing up against the edge of mathematics".
* 11 July 2025. Darren Orf. Popular Mechanics. [https://www.popularmechanics.com/science/math/a65357535/busy-beaver-six/ Mathematicians Say There’s a Number So Big, It’s Literally the Edge of Human Knowledge].
* 14 July 2025. Joe Brennan. Dario AS. [https://en.as.com/latest_news/meet-the-busy-beaver-number-a-number-so-huge-that-mathematicians-call-it-the-frontier-of-mathematical-knowledge-n/ Meet the Busy Beaver number, a number so huge that mathematicians call it the frontier of mathematical knowledge]
* 18 July 2025 https://francis.naukas.com/2025/07/18/espeluznante-nueva-cota-inferior-para-la-funcion-castor-afanoso-bb6/
* 22 Aug 2025. Ben Brubaker. Quanta Magazine. [https://www.quantamagazine.org/busy-beaver-hunters-reach-numbers-that-overwhelm-ordinary-math-20250822/ Busy Beaver Hunters Reach Numbers That Overwhelm Ordinary Math].
* 14 Sep 2025. Ben Brubaker. Wired. [https://www.wired.com/story/the-quest-to-find-the-longest-running-simple-computer-program/ The Quest to Find the Longest-Running Simple Computer Program]. (Reprint of Quanta article from last month).
* 17 Sep 2025. Hacker News. [https://news.ycombinator.com/item?id=45273999 Determination of the fifth Busy Beaver value].
* 18 Sep 2025. Tuomas Kangasniemi. Tekniikkatalous. [https://www.tekniikkatalous.fi/uutiset/a/85aafdaf-f506-4ce0-8035-a4dbe15ee4ff Iso matematiikan ongelma ratkesi 63 v jälkeen] (Finnish) (English: A big math problem solved after 63 years).
TODO

==BB Adjacent==
TODO. [[Register machine|Register machines]], [[General Recursive Function|General Recursive Functions]].

== [[General Recursive Function|Holdouts]] ==
* [[BB(6)|BB(6):]]
**There are 14 holdouts left to simulate up to 1e12 steps, and 312 to simulate up to 1e13 steps<sup>[https://discord.com/channels/960643023006490684/1239205785913790465/1447303829400846482 <nowiki>[1]</nowiki>]</sup>. The two lists can be found [https://docs.google.com/spreadsheets/d/10y2aMp9yZVLyN-nXAxgA25rw4EA_lJqn3Vxy2kB-m-U/edit?gid=806905077#gid=806905077 here].
* [[BB(3,4)|BB(3,4):]]
** TODO: Phase 2 stage 8.
* [[BB(2,7)|BB(2,7):]]
** Terry Ligocki enumerated 10K more subtasks, increasing the number of holdouts to 150,662,006 and making 50K of the 1 million subtasks enumerated or 5%.

[[Category:This Month in Beaver Research|2025-12]]

User:Autumn-Pan/Further-Reading

2025-12-12T13:18:11Z

Autumn-Pan: added TM visualizers

This article is a maintained list of resources for beginners to read. It's highly recommended to join the [https://discord.gg/Gph5X2hX discord server].

For deciders:
* See [https://arxiv.org/abs/2509.12337v1 our arXiv preprint]
* [https://wiki.bbchallenge.org/wiki/Decider Wiki page on deciders]

For Analysis:
* See Shawn Ligocki's [https://www.sligocki.com/ blog]
* For analysis in particular, see his post [https://www.sligocki.com/2021/07/17/bb-collatz.html here]
* [https://wiki.bbchallenge.org/wiki/Analysis_Tools_and_Techniques Analysis Tools and Techniques]

Visualizers:
* https://fiery.pages.dev/turing/
* https://bbchallenge.org

Misc.
* Try sending a message in [https://discord.com/channels/960643023006490684/1448375857046360094 our Discord server]
* [https://wiki.bbchallenge.org/wiki/Turing_machine#Standard_text_format Standard Text Notation for Turing Machines]

User:Autumn-Pan/Further-Reading

2025-12-12T13:12:00Z

Autumn-Pan: created page

User:Autumn-Pan

2025-12-08T15:18:49Z

Autumn-Pan: condensed readme

Hi, I'm Autumn Pan. Contact me through discord (@dihedralgroup); active on the official BBChallenge discord

amateur number theorist, c programmer. I work on BB6 and sometimes BB7.

1RB1LA 1RC1RE 1LD0RB 1LA0LC 0RF0RD 0RB---

2025-12-08T15:15:38Z

Autumn-Pan: elaborated on further analysis

{{machine|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---}}
{{TM|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---|undecided}} is a [[BB(6)]] holdout.

=Analysis by mxdys=
https://discord.com/channels/960643023006490684/1239205785913790465/1441124403801755730
<pre>
1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

start: S(18)

S(n) --> S((n+(3^i*6+i+4))/2), n mod 2 = i mod 2, 3^i*2-i-2 <= n <= 3^i*6-i-6
S(n) --> S(3^i*12-1), n mod 2 = (i+1) mod 2, 3^i*2-i <= n <= 3^i*6-i-10
</pre>

These rules are closed if <pre>(3^i*2+i+5)/(2^v2(3^i*2+i+5))>=2i+14 for all i>=50 </pre>
= Further Analysis (Pomme, Autumn Pan, et al.) =
Although it has not been proven in Rocq, it is known that the inequality holds. This has been proven informally by Pomme, though it references an external paper which makes it difficult to prove using computer proof assistants. Simulators written by Autumn Pan, Pomme, and vyx7 were used to verify the inequality for all <math>50\le i \le 10^{660}</math>.

[[Category:BB(6)]]

Beaver Math Olympiad

2025-12-08T15:10:17Z

Autumn-Pan: removed extra parenthesis from bmo6

'''Beaver Mathematical Olympiad''' (BMO) is an attempt to re-formulate the halting problem for some particular Turing machines as a mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of the BMO is twofold. First, statements where non-essential details (related to tape encoding, number of steps, etc.) are discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

== Unsolved problems ==

=== 1. {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (1, 2)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n-b_n, 4b_n+2) & \text{if }a_n \ge b_n \\
(2a_n+1, b_n-a_n) & \text{if }a_n < b_n
\end{cases}</math>

for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_i = b_i</math>?

The first 10 values of <math>(a_n, b_n)</math> are <math>(1, 2), (3, 1), (2, 6), (5, 4), (1, 18), (3, 17), (7, 14), (15, 7), (8, 30), (17, 22)</math>.

=== 2. [[Hydra]] and [[Antihydra]] ===

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_{n+1} = a_n+\left\lfloor\frac{a_n}{2}\right\rfloor</math> for all non-negative integers <math>n</math>.

# If <math>a_0=3</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many even numbers as odd numbers? ([[Hydra]])
# If <math>a_0=8</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many odd numbers as even numbers? ([[Antihydra]])

=== 5. {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (0, 5)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n+1, b_n-f(a_n)) & \text{if } b_n \ge f(a_n) \\
(a_n, 3b_n+a_n+5) & \text{if } b_n < f(a_n)
\end{cases}</math>

where <math>f(x)=10\cdot 2^x-1</math> for all non-negative integers <math>x</math>.

Does there exist a positive integer <math>i</math> such that <math>b_i = f(a_i)-1</math>?

=== 6. {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}} ===
Let <math>f(b) = b + k + 3a</math>, where <math>k</math> and <math>a</math> are non-negative integers satisfying <math>b = (2a+1)\cdot 2^k</math>.

Now consider the iterated application of the function <math>f^{n+1}(b) = f(f^n(b))</math>, <math>f^0(b)=b</math>. Does there exist a non-negative integer <math>n</math> such that <math>f^n(6)</math> equals a power of 2?

== Solved problems ==

=== 3. {{TM|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} and {{TM|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} ===

Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>. Let <math>(a_n)_{n \ge 0}</math> be a sequence such that

<math display="block">a_n = \begin{cases}
2 & \text{if } n=0 \\
a_{n-1}+2^{v_2(a_{n-1})+2}-1 & \text{if } n \ge 1
\end{cases}</math>

for all non-negative integers <math>n</math>. Is there an integer <math>n</math> such that <math>a_n=4^k</math> for some positive integer <math>k</math>?

Link to Discord discussion: https://discord.com/channels/960643023006490684/1084047886494470185/1252634913220591728

=== 4. {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB|non-halt}} ===

Bonnie the beaver was bored, so she tried to construct a sequence of integers <math>\{a_n\}_{n \ge 0}</math>. She first defined <math>a_0=2</math>, then defined <math>a_{n+1}</math> depending on <math>a_n</math> and <math>n</math> using the following rules:

* If <math>a_n \equiv 0\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n}{3}+2^n+1</math>.
* If <math>a_n \equiv 2\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n-2}{3}+2^n-1</math>.

With these two rules alone, Bonnie calculates the first few terms in the sequence: <math>2, 0, 3, 6, 11, 18, 39, 78, 155, 306, \dots</math>. At this point, Bonnie plans to continue writing terms until a term becomes <math>1\text{ (mod 3)}</math>. If Bonnie sticks to her plan, will she ever finish?

<div class="toccolours mw-collapsible mw-collapsed">'''Solution'''<div class="mw-collapsible-content">
How to guess the closed-form solution: Firstly, notice that <math>a_n \approx \frac{3}{5} \times 2^n</math>. Secondly, calculate the error term <math>a_n - \frac{3}{5} \times 2^n</math>. The error term appears to have a period of 4. This leads to the following guess:

<math display="block">a_n=\frac{3}{5}\begin{cases}
2^n+\frac{7}{3} &\text{if } n\equiv 0 \pmod{4}\\
2^n-2 &\text{if } n\equiv 1 \pmod{4}\\
2^n+1 &\text{if } n\equiv 2 \pmod{4}\\
2^n+2 &\text{if } n\equiv 3 \pmod{4}
\end{cases}</math>

This closed-form solution can be proven correct by induction. Unfortunately, the induction may require a lot of tedious calculations.

For all <math>k</math>, we have <math>a_{4k} \equiv 2\text{ (mod 3)}</math> and <math>a_{4k+1} \equiv a_{4k+2} \equiv a_{4k+3} \equiv 0\text{ (mod 3)}</math>. Therefore, Bonnie will never finish.
</div></div>

=== 7. {{TM|1RB1RF_1RC0RA_1LD1RC_1LE0LE_0RA0LD_0RB---|non-halt}} ===
Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>.

Let <math>f(n) = n+1+(v_2(n+1) \bmod 2)</math>.

Now consider the iterated application of the function <math>f^{n+1}(b) = f(f^n(b)))</math>, <math>f^0(b)=b</math>.

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_0=1</math> and <math>a_{n+1} = f^{n+2}\left(\left\lfloor\frac{a_n}{2}\right\rfloor\right)</math> for all non-negative integers <math>n</math>.

Does there exist a non-negative integer <math>k</math> such that <math>a_k</math> is even?

(for simplicity, this question is slightly stronger than the halting problem of this TM)

Link to Discord discussion: https://discord.com/channels/960643023006490684/1421782442213376000/1431483206208852001

== Practice Problems ==
Problems that are not BMO-level, but provide counter-examples to certain [[probvious]] intuition:

* {{TM|1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD}}
* {{TM|1RB0RD_0LC1RA_0RA1LB_1RE1LB_1LF1LB_---1LE}}

File:1RB1LA 1RC1RE 1LD0RB 1LA0LC 0RF0RD 0RB---Pomme.pdf

2025-11-29T22:36:56Z

Autumn-Pan: Pomme's proof of the rule closure of 1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

== Summary ==
Pomme's proof of the rule closure of 1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

1RB1LA 1RC1RE 1LD0RB 1LA0LC 0RF0RD 0RB---

2025-11-29T05:04:54Z

Autumn-Pan: fix typo "analyis", again

{{TM|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---|undecided}} is a [[BB(6)]] holdout.

=Analysis by mxdys=
https://discord.com/channels/960643023006490684/1239205785913790465/1441124403801755730
<pre>
1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

start: S(18)

S(n) --> S((n+(3^i*6+i+4))/2), n mod 2 = i mod 2, 3^i*2-i-2 <= n <= 3^i*6-i-6
S(n) --> S(3^i*12-1), n mod 2 = (i+1) mod 2, 3^i*2-i <= n <= 3^i*6-i-10
</pre>

These rules are closed if and only if <pre>(3^i*2+i+5)/(2^v2(3^i*2+i+5))>=2i+14 for all i>=50 </pre>
= Further Analysis (Pomme, Autumn Pan, et al.) =
Although it has not been proven in Rocq, it is known that the inequality holds. This has been proven informally by Pomme, and an alternative proof is underway by Autumn Pan.

1RB1LA 1RC1RE 1LD0RB 1LA0LC 0RF0RD 0RB---

2025-11-29T05:04:27Z

Autumn-Pan: fix typo "analyis"

{{TM|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---|undecided}} is a [[BB(6)]] holdout.

=Analysis by mxdys=
https://discord.com/channels/960643023006490684/1239205785913790465/1441124403801755730
<pre>
1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

start: S(18)

S(n) --> S((n+(3^i*6+i+4))/2), n mod 2 = i mod 2, 3^i*2-i-2 <= n <= 3^i*6-i-6
S(n) --> S(3^i*12-1), n mod 2 = (i+1) mod 2, 3^i*2-i <= n <= 3^i*6-i-10
</pre>

These rules are closed if and only if <pre>(3^i*2+i+5)/(2^v2(3^i*2+i+5))>=2i+14 for all i>=50 </pre>
= Further Analylis (Pomme, Autumn Pan, et al.) =
Although it has not been proven in Rocq, it is known that the inequality holds. This has been proven informally by Pomme, and an alternative proof is underway by Autumn Pan.

1RB1LA 1RC1RE 1LD0RB 1LA0LC 0RF0RD 0RB---

2025-11-29T05:03:44Z

Autumn-Pan: Added brief summary of work done, will be updated as more work comes out in the near future

{{TM|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---|undecided}} is a [[BB(6)]] holdout.

=Analysis by mxdys=
https://discord.com/channels/960643023006490684/1239205785913790465/1441124403801755730
<pre>
1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---

start: S(18)

S(n) --> S((n+(3^i*6+i+4))/2), n mod 2 = i mod 2, 3^i*2-i-2 <= n <= 3^i*6-i-6
S(n) --> S(3^i*12-1), n mod 2 = (i+1) mod 2, 3^i*2-i <= n <= 3^i*6-i-10
</pre>

These rules are closed if and only if <pre>(3^i*2+i+5)/(2^v2(3^i*2+i+5))>=2i+14 for all i>=50 </pre>
= Further Analyis (Pomme, Autumn Pan, et al.) =
Although it has not been proven in Rocq, it is known that the inequality holds. This has been proven informally by Pomme, and an alternative proof is underway by Autumn Pan.

User:Autumn-Pan

2025-11-03T23:38:34Z

Autumn-Pan: created personal user page describing work and contact information

Hi, I'm Autumn Pan. Contact me through discord (@dihedralgroup); active on the official BBChallenge discord

I code deciders, run simulations, as well as work on individual machines by hand. I focus my work on BB(6).

I computed the range of 1618 BB6 holdouts to 1 billion steps, the sorted list is [https://wiki.bbchallenge.org/w/images/5/5b/Least_cells_visited_2.txt here]. Notably, my computation left a majority of the holdouts without known ranges due to their tapes exceeding the scope of what my personal tools were capable of. I intend on revisiting these values when I have developed my simulator far enough to do so. Please contact me on discord if you have any questions or requests.