4 ms·
> 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
by tromp 2y ago
> 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.
[1] https://oeis.org/A333479 https://oeis.org/A333479
[2] https://oeis.org/A361211 https://oeis.org/A361211
[3] https://arxiv.org/pdf/1703.05170 https://arxiv.org/pdf/1703.05170
- passion__desire 2y agoIsn'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.
- Sniffnoy 2y agoThe 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.
- anandijain 2y agoA 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. I found this https://oeis.org/A141475 https://oeis.org/A141475, but it gives 27 trillion for 5.
- tromp 2y agoWhile 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. [1] https://oeis.org/A052200 https://oeis.org/A052200