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, m-symbol Turing machine halts in exactly a(n) steps on an initially blank tape.	see Lazy Beaver#Computed Values	A337805 (for m=2)
Configs A(a, b) reached in Antihydra			A386792 (for a), A385902 (for b)

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
Maximum Space Function	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	see Maximum Space Function#Champions	-
		Number of n-state Turing machines which halt.		A004147
Blanking Busy Beaver	BLB(n,m)	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)	see Blanking Busy Beaver Function#Champions	-
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.	see Instruction-Limited Busy Beaver#Champions	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.	see Instruction-Limited Busy Beaver#Champions	A384766
Instruction-Limited Greedy Busy Beaver	gBBi(n)	Maximum number of steps that an n-instruction Turing machine can take from a blank tape before halting, where the Turing machines first n-1 instructions are a machine which runs for gBBi(n-1) steps.	see Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants
Instruction-Limited Blanking Busy Beaver	BLBi(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 blanking the tape again.	see Instruction-Limited Busy Beaver#Instruction-Limited Busy Beaver Variants
Busy Beaver for lambda calculus	BBλ(n)	Maximum beta normal form size of any closed lambda term of size n.	see Busy Beaver for lambda calculus#Champions	A333479

Π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
Busy Beaver for lambda calculus with a BBλ oracle	BBλ1	Maximum beta/oracle normal form size of any 1-closed lambda term of size n.	see Busy Beaver for lambda calculus#Oracle Busy Beaver	A385712

Π3

Sequence Name	Symbol	Description	Values	OEIS sequence
Beeping Booping busy beaver	BBBB(n)		see Beeping Busy Beaver#Beeping Booping Busy Beavers

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
• Any of the above functions bounded by the number of instructions rather than states and symbols.

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"