Number of Halting TMs

The Number of Halting TMs for a given domain ($N_e(n,m)$) is an uncomputable Busy Beaver Function first defined by Tibor Radó in his 1962 paper. It counts the number of n-state, m-symbol Turing machines which eventually halt. It is bounded above by the total number of n-state, m-symbol Turing machines $N(n,m)=(2(n+1)m{)}^{nm}$. Note that this definition allows 2m different halting transitions: 0RZ, 0LZ, 1RZ, 1LZ, etc.

This function is uncomputable: Knowing the exact value for a domain would allow you to solve the halting problem for that domain (by running all TMs in parallel until $N_e(n,m)$ of them have halted). However, unlike the Max step S(n, m) or Max Score Σ(n, m) functions, $N_e(n,m)$ is bounded by a computable function (namely N(n, m) as described above).

Exact Values

$N_e(n,m)$

	2-state	3-state	4-state	5-state
2-symbol	9,784	7,571,840	11,140,566,368	26,751,695,615,616
3-symbol	20,453,040
4-symbol	116,636,824,512

Methodology

These values were computed using the commands Count.py --rado --halt BB${DOMAIN}_verified_enumeration_augmented.csv from the official CoqBB5 augmented verified enumeration files. The TMs in this file are all in Tree Normal Form and thus each represent many fully specified TMs. This script counts the number of fully-specified TMs represented by each halting TNF TM. To compute this we:

1. Start by computing the number of permutations of non-start states and non-blank symbols and directions. For a TM which specifies all states and symbols this is $2(n-1)!(m-1)!$. It is smaller if the TM does not specify all states or symbols.
2. For every undefined transition, multiply by $2(n+1)m$ (all possible transitions, including halting ones) that could be used here.
3. For every explicit halting transition (all halting TNF TMs will have exactly one of these), multiply by 2m (all legal fully-specified halting transitions).

The results above are the sums of each of these values across all halting TMs in each domain.

See Also

• https://oeis.org/A004147: $N_e(n,2)$