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
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 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
Beeping Busy Beaver	BBB(n)	The latest possible step that any 2-symbol TM with n states exits a chosen state finitely many times	BBB(1)=1, BBB(2)=6	-
	#BB(n)	The number of programs with n states that halt after exactly BB(n) steps (Max Shift) for each n (including all equivalent transformations)	#BB(1)=32, #BB(2)=40, #BB(3)=16	-
		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		-
		The average number of states that are reached infinitely many times, among all non-halting turing machines with n states

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