How many busy beavers with the same number of states

Question

Can the number of busy beavers with n states be computed, or would it be necessary to analyze all the machines to count them ?

Answer 1

(A busy beaver is a two-symbol Turing machine that halts when started on a blank tape, and does so in a maximal number of steps among all machines with the same number of states that halt on the blank tape).

It would be extraordinarily surprising if the number of busy beavers of a given size was computable.

Remember that there must be machines where it is independent of the axioms (choose any recursive set of axioms that don't prove arithmetic falsehoods) whether the machine is a busy beaver or not. Given that, it would be very strange if the axioms nevertheless determined how many of them there are -- and unless they do so, we can at least never prove that any given algorithm counts them correctly.

Since we're getting into foundational issues here, the question is not really a yes/no one. There are at least four imaginable resolutions:

1. Yes, this function is computable, and here is a concrete algorithm that we can prove (from some reasonable axiomatic basis) computes it.

2. The function is computable, and here is a non-constructive proof that there must be a machine that computes it. We can't ever know which machine that is, though.

3. It is independent of (insert your favorite axiom system here) whether the function is computable or not.

4. The function is provably not computable.

Of these (1) and (2) would surprise me, (1) moreso than (2). However, (3) and (4) both sound plausible -- intuitively my money would be on (3), though.