> There are many variants of the original busy beaver problem, and some Busy Beaver Challenge contributors plan to keep working on these.
One such variant is a functional busy beaver defined in terms of the lambda calculus [1]. Since it measures program size in bits rather than states, it allows many more values to be determined (37 so far versus only 6 for TMs), and the gap between the largest known value and values beyond Graham's Number is a mere 13 program bits. A closely related variant [2] can be directly expressed in terms of Kolmogorov complexity, which Mikhail Andreev argues [3] is crucial for applications in Information Theory.
A bit unrelated but you posted oeis so hoping you know.
In the article they mention there are 17 trillion possible 5-2 turing machines. I tried finding the sequence for this but couldn't.
While the official formula [1] is (4(n+1))^(2n)
, if one ignores the symbol written and head movement for transitions to halt, then this becomes (4n+1)^(2n), which is ~ 17 trillion for n=5.
Isn't there another formulation of BB where we count shifts (from left to right, and from right to left) a TM makes instead of strings of contiguous 1s. I remember seeing a video about this definition.
The variant of BB discussed in the article is counting steps, not 1s. (I guess "shifts" is equivalent to steps, although that seems like a more roundabout way of specifying it.) Also, I don't think anyone counts strings of contiguous 1s, although of course one could define such a thing.
One such variant is a functional busy beaver defined in terms of the lambda calculus [1]. Since it measures program size in bits rather than states, it allows many more values to be determined (37 so far versus only 6 for TMs), and the gap between the largest known value and values beyond Graham's Number is a mere 13 program bits. A closely related variant [2] can be directly expressed in terms of Kolmogorov complexity, which Mikhail Andreev argues [3] is crucial for applications in Information Theory.
[1] https://oeis.org/A333479
[2] https://oeis.org/A361211
[3] https://arxiv.org/pdf/1703.05170