OFFSET
0,3
COMMENTS
This sequence is uncomputable.
No halting instruction is required, as a Turing machine halts whenever the current state/tape symbol combination does not have a corresponding instruction. However, a halting instruction can be implemented by transitioning to a state which has no instructions. For example, the 2-state 2-symbol busy beaver can be given as A0:1RB, A1:1LB, B0:1LA, B1:1RC, where "C" effectively substitutes for "H".
This sequence effectively combines the various Symbols Busy Beaver functions Sigma(states,symbols) into a single sequence defined only by number of allowable instructions Sigma_i(inst). It is very interesting to observe the number of states and symbols associated with the champion machine for each number of instructions.
a(6)=14 confirmed by Shawn Ligocki on bbchallenge Discord on Jul 12 2025.
a(7)=2050 confirmed and announced on Discord on Jul 23 2025. Two different Turing machines - one a 2-state, 4-symbol machine, and the other a 3-state, 3-symbol machine - each take 3232963 steps, writing 2050 non-blank symbols to tape.
A new champion machine for a(8) was discovered by Nick Drozd and confirmed by Shawn Ligocki on Jul 26 2025. This machine writes around 1.355*10^783 non-blank symbols to tape before halting.
LINKS
bbchallenge Wiki, Instruction-Limited Busy Beaver.
Discord, Announcement of BBi(7).
N. Drozd, New BBi(8) champion machine found.
N. Drozd, The Shape of a Turing Machine.
S. Ligocki, BBi(8) steps value confirmed.
S. Ligocki, BB(3,3) is Hard (Bigfoot).
Pascal Michel, The Busy Beaver Competitions.
EXAMPLE
a(0)=0. No instructions means machine instantly halts, writing no symbols.
a(1)=1. A0:1RB
a(2)=2. A0:1RB, B0:1LA - One of 8 2-instruction machines writing 2 non-blank symbols.
a(3)=4. A0:0RB, A1:1LB, B0:1LA - One of 5 3-instruction machines writing 4 non-blank symbols.
a(4)=5. A0:1RB, A1:0LB, B0:1LA, B1:2RA - One of 41 4-instruction machines writing 5 non-blank symbols.
a(5)=9. A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB
a(6)=14. A0:1RB, A1:3LA, A2:1RA, A3:0LA, B0:2LA, B3:3RA
a(7)=2050. A0:1RB, A1:2LA, A2:1RA, A3:1RA, B0:1LB, B1:1LA, B2:3RB - BB(2,4) minus the halt instruction for B3, and A0:1RB, A1:2LA, A2:1RA, B0:1LC, B1:1LA, B2:2RB, C1:1LA - A 3-state, 3-symbol Turing machine with two empty instructions.
a(8)>=1.355*10^783. Must be at least the number of non-blank symbols written by the following 3-state, 4-symbol machine discovered by Nick Drozd: A0:1RB, A1:1LA, B0:1RC, B1:3LB, B2:1RB, C0:2LA, C1:2LC, C3:0LC. a(8) will not easily be proven because a 3-state, 3-symbol machine "Bigfoot", having 8 non-halting instructions, must first be proven never to halt, requiring solving a Collatz-like problem.
CROSSREFS
KEYWORD
hard,more,nonn
AUTHOR
Brian Galebach, Jun 09 2025
EXTENSIONS
a(6)-a(7) from Brian Galebach, Dec 09 2025
STATUS
approved