A Simple and Natural Uncomputable Function
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.^{[1]}
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 (nontight) 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.

Assuming the canonical TM model for these kinds of things – using a tape alphabet $\Gamma := \{0, 1\}$, where $0$ also serves as the blank symbol (i.e. the empty tape consists fully of zeros), assuming that the lowest state is the initial and acceptance is done by halting. ↩