BB(3,3)

The 3-state, 3-symbol Busy Beaver problem BB(3,3) is unsolved. With the discovery of Bigfoot in 2023, we now know that we must solve a Collatz-like problem in order to solve BB(3,3) and thus BB(3,3) is Hard.

The current BB(3,3) champion 0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC (bbch) was discovered by Terry and Shawn Ligocki in 2007, proving the lower bounds:

$${\begin{array}{lcrl}S(3,3)&\geq &119{,}112{,}334{,}170{,}342{,}541&>10^{17}\\\Sigma (3,3)&\geq &374{,}676{,}383&>10^{8}\\\end{array}}$$

On bbchallenge.org Discord we have reduced the unofficial holdouts list to 22 TMs. One of these, 1RB2LC1RC_2LC---2RB_2LA0LB0RA (bbch), is under very active exploration in channel #bb3x3 and believed to be a probviously halting TM by some members. If it halts, it will be the new champion.

Cryptids

Known BB(3,3) Cryptids:

• 1RB2RA1LC_2LC1RB2RB_---2LA1LA (bbch), known as Bigfoot

Possibly probviously halting Cryptid:

• 1RB2LC1RC_2LC---2RB_2LA0LB0RA (bbch)

Top Halters

The current top 10 BB(3,3) halters (known by Shawn Ligocki) are

0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC Halt 119112334170342541 374676383
1RB2LA1LC_0LA2RB1LB_1RZ1RA1RC Halt 119112334170342540 374676383
1RB2RC1LA_2LA1RB1RZ_2RB2RA1LC Halt 4345166620336565 95524079
1RB1LA2LC_2LA2RB1RB_1RZ0LB0RC Halt 452196003014837 21264944
1RB1RZ2LC_1LC2RB1LB_1LA2RC2LA Halt 4144465135614 2950149
1RB2LA1RA_1RC2RB0RC_1LA1RZ1LA Halt 987522842126 1525688
1RB1RZ2RB_1LC0LB1RA_1RA2LC1RC Halt 4939345068 107900
1RB2LA1RA_1LB1LA2RC_1RZ1LC2RB Halt 1808669066 43925
1RB2LA1RA_1LC1LA2RC_1RZ1LA2RB Halt 1808669046 43925
1RB2LA1RA_1LB1LA2RC_1RZ1LA2RB Halt 1808669046 43925

Numbers listed are step count and sigma score for each TM. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3. For historical perspective see Pascal Michel's Historical survey of Busy Beavers.

Holdouts

@Justin Blanchard's informal holdouts list is down to 22 TMs as of 9 Jun 2024. @Andrew Ducharme has categorized them as follows:

Cryptids

• 829: Bigfoot: 1RB2RA1LC_2LC1RB2RB_---2LA1LA (bbch)

Unsolved:

• Group 2
  • 1RB0LB0RC_2LC2LA1RA_1RA1LC--- (bbch) (153, equivalent to 758)
  • 1RB2LC1RC_2LC---2RB_2LA0LB0RA (bbch) (758, equivalent to 153)
• Group 3
  • 1RB2LA1LA_2LA0RA2RC_---0LC2RA (bbch) (531, equivalent to 532)
  • 1RB2LA1LA_2LA0RA2RC_---1RB2RA (bbch) (532, equivalent to 531)
• 1RB1LB2LC_1LA2RB1RB_---0LA2LA (bbch) (397)

Non-halting TMs with a less rigorous solution/proof:

• Group 1 (Discord summary of proofs)
  • 1RB---0LC_2LC2RC1LB_0RA2RB0LB (bbch) (21, equivalent to 92 and 818)
  • 1RB---1RB_2LC2RC1LB_0RA2RB0LB (bbch) (92, equivalent to 21 and 818)
  • 1RB2LC---_0LA0RC1LC_1RB2RC1LB (bbch) (683)
  • 1RB2RA1LB_0LC0RA1LA_---2LA--- (bbch) (816)
  • 1RB2RA1LB_0LC0RA1LA_---2RB2LA (bbch) (817)
  • 1RB2RA1LB_0LC0RA1LA_2LA0RB--- (bbch) (818, equivalent to 21 and 92)
• 1RB2LA1LC_1LA2RB1RB_---2LB0LC (bbch) (543)
• 1RB1LC1LC_1LA2RB0RB_2LB---0LA (bbch) (412) (cosearch)
• 1RB2LB0LC_2LA2RA1RB_---2LA1LC (bbch) (650) (cosearch)

Non-halting TMs that are fully proven by a human or computer, but have not yet received a certificate:

• 1RB0RC---_2RC0LB1LB_2LC2RA2RB (bbch) (279)
• 1RB1LC---_0LC2RB1LB_2LA0RC1RC (bbch) (400, equivalent to 494)
• 1RB2LA2RA_1LC1LB0RA_2RA0LB--- (bbch) (637)
• 1RB2RB---_1LC2LB1RC_0RA0LB1RB (bbch) (834, related to Group 1)
• 1RB2RB1LC_1LA2RB0RB_2LB---0LA (bbch) (867)

Non-halting TMs that are fully proven and received a certificate:

• 1RB2LA0LA_2LC---2RA_0RA2RC1LC (bbch) (494, equivalent to 400)
• 1RB2LB---_1RC2RB1LC_0LA0RB1LB (bbch) (642, related to Group 1) (cosearch)