A384629 Instruction-Limited Busy Beaver Sequence BBi(n): Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before eventually halting.

0, 1, 3, 5, 16, 37, 123, 3932963

Offset: 0

Author

Brian Galebach, Jun 05 2025

Keywords

• hard
• more
• nonn

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 Busy Beaver step functions BB(states,symbols) into a single sequence defined only by number of allowable instructions BBi(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)=123 confirmed by Shawn Ligocki on bbchallenge discord on Jul 12 2025.

a(7)=3932963 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 3932963 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 takes around 6.889 x 10^1565 steps before halting.

Examples

			a(0)=0.  No instructions means machine instantly halts. (Philosophical question: Can something that was never moving actually "halt"?)
a(1)=1.   A0:0RB - One of two 1-instruction machines taking 1 step.
a(2)=3.   A0:0RB, B0:1LA
a(3)=5.   A0:0RB, B0:1LA, B1:1RB - One of 14 3-instruction machines taking 5 steps.
a(4)=16.  A0:1RB, B0:0RC, C0:1LC, C1:0LA
a(5)=37.  A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB - BB(2,3) minus the halt instruction for A2.
a(6)=123. A0:1RB, A1:3LA, A2:1RA, A3:0LA, B0:2LA, B3:3RA
a(7)=3932963. 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)>=6.889 x 10^1565. Must be at least the number of steps taken 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.
		

Links

• bbchalenge Wiki, Instruction-Limited Busy Beaver.
• discord, Announcement of BBi(7)..
• N. Drozd, New BBi(8) champion machine found.
• S. Ligocki, BBi(8) steps value confirmed.
• S. Ligocki, BB(3,3) is Hard (Bigfoot).
• Pascal Michel, The Busy Beaver Competitions.

Crossrefs

Cf. A060843, A384766.

Extensions

a(6) added by Brian Galebach, Jul 15 2025

a(7) added by Brian Galebach, Aug 05 2025