The Busy Beaver numbers are an undecidable set; if they were decidable, we could figure out BB(n) for each n, enabling us to decide the halting problem. They are also not recursively enumerable, but for a trickier reason. Recursive enumerability would not allow you to figure out BB(n) (as it just gives us the ability to list out the BB numbers in some order, not necessarily in increasing order). But since the sequence is strictly increasing, recursive enumerability would enable us to put an upper bound on BB(n), which is just as good for the purposes of solving the halting problem. Simply enumerate the BB numbers in whatever order your algorithm allows, and once you’ve listed n of them, you know that the largest of those n is at least as big as the BB(n) (after all, it’s a BB number that’s larger than n-1 other BB numbers).

So the Busy Beaver numbers are also not recursively enumerable. But curiously, they’re Turing equivalent to the halting problem, and the halting problem is recursively enumerable. So what gives?

The answer is that the Busy Beaver numbers are co-recursively enumerable. This means that there is an algorithm that takes in a number N and returns False if N is not a Busy Beaver number, and runs forever otherwise. Here’s how that algorithm works:

First, we use the fact that BB(N) is always greater than N. This allows us to say that if N is a Busy Beaver number, then it’s the running time of a Turing machine with at most N states. There are finitely many such Turing machines, so we just run them all in parallel. We wait for N steps, and then see if any machines halt at N steps.

If no machines halt at N steps, then we return False. If some set of machines {M₁, M₂, …, M_k} halt at N steps, then we continue waiting. If N is not a Busy Beaver number, then for each of these machines, there must be another machine of the same size that halts later. So if N is not a Busy Beaver number, then for each M_i there will be a machine M_i‘ such that M_i‘ has the same number of states as M_i and that halts after some number of steps N_i‘ > N. Once this happens, we rule out M_i as a candidate for the Busy Beaver champion. Eventually, every single candidate machine is ruled out, and we can return False.

On the other hand, if N is a Busy Beaver number, then there will be some candidate machine M such that no matter how long we wait, we never find another machine with the same number of states that halts after it. In this case, we’ll keep waiting forever and never get to return True.

It’s pretty cool to think that for any number that isn’t a Busy Beaver number, we can in principle eventually rule it out. If a civilization ran this algorithm to find the first N busy beaver numbers, they would over time rule out more and more candidates, and after a finite amount of time, they would have the complete list of the first N numbers. Of course, the nature of co-recursive enumerability is that they would never know for sure if they had reached that point; they would forever be waiting to see if one of the numbers on their list would be invalidated and replaced by a much larger number. But in the limit of infinite time, this process converges perfectly to truth.

✯✯✯

Define H to be the set of numbers that encode Turing machines that halt on the empty input, and B to be the set of Busy Beaver numbers. H and B are Turing equivalent. The proof of this is two-part:

1. H is decidable with an oracle for B

We are given as input a Turing machine M (encoded as some natural number) and asked whether it will halt. We use our oracle for B to find the value of BB(n), where n is the number of states that M has, and run M for BB(n) steps. If M doesn’t halt at this point, then we know that it will never halt and we return False. And if it has already halted, we return True.

2. B is decidable with an oracle for H

We are given as input a number N and asked whether it’s a Busy Beaver number. We collect all Turing machines with at most N states, and apply H to determine which of these halt. We throw out all the non-halting Turing machines and run all the rest. We then run all the remaining Turing machines until each one has halted, noting the number of steps that each runs for and how many states it had. At the end we check if N was the running time of any of the Turing machines, and if so, if there are any other Turing machines with the same number of states that halted later. If so, then we return False, and otherwise we return True.

So H and B have the same Turing degree. And yet B is co-recursively enumerable and H is recursively enumerable (given a Turing machine M, just run it and return True if it ever halts). This is actually not so strange; the difference between recursive enumerability and co-recursive enumerability is not a difference in “difficulty to decide”, it’s just a difference between whether what’s decided is the True instances or the False instances.

As a very simple example of the same phenomenon, consider the set of all halting Turing machines H and the set of all non-halting Turing machines H^c. H is recursively enumerable and H^c is co-recursively enumerable. And obviously given an oracle for either one can also decide the other. More generally, for any set X, consider X^c = {n : n ∉ X}. X and X^c are Turing equivalent, and if X is recursively enumerable then X^c is co-recursively enumerable. What’s more, if X is Σ_n then X^c is Π_n.