Sequences

This page lists sequences related to the Busy Beaver functions.

This table is incomplete, you can help by adding missing items.

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

Noncomputable Sequences

The following sequences depend on the specific behavior of programs.

Sequence Name	Description	Values	OEIS sequence
Max Shift Function S(n, m)	The maximal number of steps that an n-state 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 Turing machine can print on an initially blank tape before halting.		A028444
	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
	The number of programs with n states that halt after exactly BB(n) steps (Max Shift) for each n (including all equivalent transformations)		-
	The number of programs that maximize the number of non-zero cells at the time of halting (Max Score) for each n (including all equivalent transformations)		-
	The number of distinct final tape states of halting machines with n states		-
	The number of non-halting programs with n states which reach infinitely many tape cells		-

For more related sequences, see OEIS search: "busy beaver" and OEIS Wiki: "related to busy beaver"