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.

TODO: group by position in arithmetical hierarchy

Sequence Name	Symbol	Description	Values	OEIS sequence	Position in Arithmetical Hierarchy
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	Π1
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	Π1
	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	-	Π1
		Number of n-state Turing machines which halt.		A004147	Π1
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	-	Π2
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)		-	Π1
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)		Π1
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			Π1
Size of the Runtime Spectrum		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"		Π1
	#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		-	Π1
		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"