News for hackers. Stuff that matters.
Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @03:20PM (#40458813)
There are many inefficiencies in Turing Machines which you could try to work around with increasingly complicated encodings. But that will never yield a provably optimal machine encoding such as you can obtain with BBλ2 [1].

[1] https://oeis.org/A361211

Re:BB(3, 4) > Ack(14) by sligocki on Thursday May 23, 2024 @09:13PM (#40461863)
Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) < BB(n + c) and vice-versa. I am not sure what the exact equation will be off-hand, maybe in this case we will need to replace BB() with a version based on binary encoding of TMs.
Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @09:53PM (#40462118)
As the OEIS entry says:

> for any other busy beaver BB based on self-delimiting programs, there is a constant c such that a(c+n) >= BB(n)

This requires an information theoretic measure of program size, such as bits or bytes, whereas the TM-based BB measures in states. I don't believe there are additively tight bounds on how many states are needed to encode an arbitrary string of n bits.