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

Noncomputable Sequences

The following sequences depend on the specific behavior of programs.

TODO: group by position in arithmetical hierarchy

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
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.		A337805
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	-
Blanking Beavers		The maximum number of steps that an n-state m-color Turing machine can make on an initially blank tape until it is blank again		-
	#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	-
	#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 number of non-halting programs with n states which reach infinitely many tape cells		-
		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"

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"