Ciro Santilli @cirosantilli 34

The last value we will likely every know for the busy beaver function! BB(6) is likely completely out of reach forever.

By 2023, it had basically been decided by the The Busy Beaver Challenge as mentioned at: discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141, pending only further verification. It is going to be one of those highly computational proofs that will be needed to be formally verified for people to finally settle.

As that project beautifully puts it, as of 2023 prior to full resolution, this can be considered the:on the Busy beaver scale.

The busy beaver game consists in finding, for a given $n$, the turing machine with $n$ states that writes the largest possible number of 1's on a tape initially filled with 0's. In other words, computing the busy beaver function for a given $n$.

There are only finitely many Turing machines with $n$ states, so we are certain that there exists such a maxium. Computing the Busy beaver function for a given $n$ then comes down to solving the halting problem for every single machine with $n$ states.

Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.

The Busy Beaver problem is cool because it puts the halting problem in a more precise numerical light, e.g.:

Bibliography:

In intuitive terms it consists of all integer functions, possibly with multiple input arguments, that can be written only with a sequence of:and such that n does not change inside the loop body, i.e. no while loops with arbitrary conditions.

n does not have to be a constant, it may come from previous calculations. But it must not change inside the loop body.

Primitive recursive functions basically include every integer function that comes up in practice. Primitive recursive functions can have huge complexity, and it strictly contains EXPTIME. As such, they mostly only come up in foundation of mathematics contexts.

The cool thing about primitive recursive functions is that the number of iterations is always bound, so we are certain that they terminate and are therefore computable.

This also means that there are necessarily functions which are not primitive recursive, as we know that there must exist uncomputable functions, e.g. the busy beaver function.

Adding unbounded while loops of course enables us to simulate arbitrary Turing machines, and therefore increases the complexity class.

More finely, there are non-primitive total recursive functions, e.g. most famously the Ackermann function.

The prototypical example is the Busy beaver function, which is the easiest example to reach from the halting problem.