Motivated by an interesting survey paper, I have pondered a little bit on Busy Beavers. While I don’t have anything to share on that front, I noticed that there is another related interesting function – the function $H(n): \mathbb{N} \to \mathbb{N}$ that gives the number of TMs with n states that halt on an empty input tape.¹

Clearly this function is uncomputable – if it were computable, we could solve the halting problem for some $n$-state TM $\mathcal{M}$ by running an interlaced stepwise simulation of all $n$-state TMs and waiting until $H(n)$ of them halt. As by definition of $H$, this will happen after an unknown but finite amount of time, eventually we can abort the simulation and check whether $\mathcal{M}$ has halted.

Because the number of distinct TMs with $n$ states is bounded by an exponential function, it means that $H(n)$ is, too – it simply defines the cardinality of the subset of TMs that do halt. It is also easy to see that $H(n)$ grows strictly monotonically.

While $H(n)$ does not allow us to describe the limits of growth of computable functions like the Busy Beaver function $BB(n)$ does, it is just as easy and natural to define, and they have a simple relationship: $H(n)$ can be computed by running all TMs with $n$ states for $BB(n)$ steps and checking how many have halted, and $BB(n)$ can be computed by running all TMs with $n$ states until $H(n)$ of them have halted, the time it took the last one to halt being the desired value for $BB(n)$. So the information provided by both functions is interchangeable for all “practical” purposes.

One thing makes the $BB(n)$ function look a bit more useful – having an upper bound for $BB(n)$ already helps for deciding other problems, while a (non-tight) upper bound for $H(n)$ does not appear to be of any help – if we overestimate the number of TMs that halt and do not know $BB(n)$, we will have to wait forever in our decision procedure trying to make use of that upper bound, because no additional machines will ever halt.

It feels like $H(n)$ fits somewhere between the Busy Beaver function and the Chaitin constant. The Chaitin constant can be used in similar ways to $H(n)$, but encodes all the information in a single real value, whereas $H(n)$ stays in the realm of discrete integers. I guess it is easy to express the Chaitin constant as a weighted measure based on the ratios of $H(n)/NumTM(n)$, where $NumTM(n)$ is the total number of TMs with $n$ states.

I wonder if there has been some research into $H(n)$, but maybe studying it directly does not have any advantages over studying the Chaitin constant(s) and Busy Beavers. Still, I thought this is an interesting curiosity and was a bit surprised I have not found it mentioned anywhere.

And if someone would ask me for an example of an uncomputable monotonic function with a simple and natural definition and elementary growth, I might point them to this one.