Sequences

This page lists sequences related to the Busy Beaver functions.

These tables are incomplete, you can help by adding missing items. If you add a value, please add a reference to a paper or code with which it was computed/proved if possible.

If the "canonical" values of a sequence are maintained on another Wiki page, please link to that, instead of replicating them here.

Computable Sequences

Sequence Name	Description	Values	OEIS sequence
2-symbol TM count	Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.		A052200
Number of n-state 2-symbol halt-free TMs	A Turing machine is halt-free if none of its instructions lead to the halt state.		A337025
Lazy Beaver	The smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape.	LB(1)=2, LB(2)=7, LB(3)=22, LB(4)=72, LB(5)=427	A337805

Noncomputable Sequences

The following sequences depend on the specific behavior of programs and are grouped by their position in the arithmetical hierarchy.

Note that when the bbchallenge community refers to BB(n, m), we mean the Max Shift function S(n, m) defined below (if m is omitted, it is set to 2 by default). Some literature may refer to the Max Score function Σ(n, m) by BB(n, m) instead.

Π1

Sequence Name	Symbol	Description	Values	OEIS sequence
Max Shift Function	S(n, m)	The maximal number of steps that an n-state, m-symbol Turing machine can make on an initially blank tape before eventually halting.	see the Main Page	A060843
Max Score Function	Σ(n, m)	Maximal number of 1's that an n-state, m-symbol Turing machine can print on an initially blank tape before halting.		A028444
	BB_SPACE(n,m)	Maximum number of memory cells visited by a halting Turing machine with n states and m symbols starting from all-0 memory tape	BB_SPACE(1,2)=2, BB_SPACE(2,2)=4, BB_SPACE(3,2)=7, BB_SPACE(4,2)=16	-
		Number of n-state Turing machines which halt.		A004147
Blanking Beavers		The maximum number of steps that an n-state m-symbol Turing machine can make on an initially blank tape until it is blank again (halting or not)		-
BB_clean		The maximum number of steps that an n-state 2-symbol Turing machine can make on an initially blank tape until it halts on a blank tape	(see comments #75 and #77 here)
BB_ones		The maximum number of 1's that an n-state 2-symbol Turing machine can make in a row, before halting on a 0 next to it
Size of the Runtime Spectrum	$R(n)$	The number of distinct runtimes for a machine with a given number of symbols, for increasing number of states	see "The Spectrum of Runtimes" in "The Busy Beaver Frontier"
		The number of non-halting programs with n states which reach infinitely many tape cells
Instruction-Limited Busy Beaver	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.		A384629
Instruction-Limited Symbol Busy Beaver	Σi(n)	Maximum number of non-blank symbols that an n-instruction Turing machine (allowing any number of states and symbols) can leave on an initially blank tape before eventually halting.		A384766

Π2

Sequence Name	Symbol	Description	Values	OEIS sequence
Beeping Busy Beaver	BBB(n)	The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times	see Beeping Busy Beaver#Results
Beeping Booping busy beaver	BBBB(n)		BBBB(1) = 1

Yet ungrouped

Sequence Name	Symbol	Description	Values	OEIS sequence
	#S(n, m)	The number of programs that halt after exactly S(n,m) steps (Max Shift) for each n of a given m (including all equivalent transformations)	#S(1,2)=32, #S(2,2)=40, #S(3,2)=16	-
	#Σ(n, m)	The number of programs that halt with Σ(n, m) 1's on the tape (Max Score) for each n of a given m (including all equivalent transformations)	#Σ(1,2)=16, #Σ(2,2)=4, #Σ(3,2)=40	-
Maximum space	#BB_SPACE(n,m)	The number of programs that visited the most number of tape cells for a given (n,m) (including all equivalent transformations)	#BB_SPACE(1,2)=32, #BB_SPACE(2,2)=24, #BB_SPACE(3,2)=48	-
		The average number of states that are reached infinitely many times, among all non-halting turing machines with n states		-

More possibilities

• The number of distinct final tape states of halting machines with n states and m symbols, for some definition of "distinct"
• Any of the above for machines with more than one tape, or tapes with more dimensions (2d grid, 3d, n-d...)
• Machines with a finite tape, or a circular one of a certain length

Further information

For more information on sequences, see the OEIS Wiki: Busy Beaver Numbers, OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"