I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51.
I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60.
Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?
I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51.
I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60.
Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?
Like you can mirror the tape. You can relabel states B and C. And you can relabel symbols 1, 2, 3. Though the analysis is complicated a little bit by the fact that some (combinations) of those operations may yield the exact same machine.
If you mean multiple halting states, then that is possible, and it can be used as a model of computation for, e.g., computable functions returning a single bit as output. But you still don't gain any additional running time before the machine halts.
As for no halting transitions, the problem is choosing what point to measure the tape at. One thing you can do is to put a mark on one of the transitions, then see whether the machine only runs that transition a finite number of times, or if it keeps running it forever. This yields the "Beeping Busy Beaver" numbers [0], which are uncomputable even if you have an oracle for the halting problem.
[0] https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
Perhaps this is semantic games, but I'm trying to get at the idea that while there may be 60 bits of information in the BB(3,4) program, there are fewer in the BBWOHT(3,4) program, because we can prima facie exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BBWOHT(n,k), in the same way that we can exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BB(n,k) programs that aren't symmetries of other BB(n,k) programs.
> 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.
Looking at the state transitions:
12 * log2(3+1) is 24 bits
log2(12) + 11 * log2(3) is only 21.02 bits
And since the specific output symbol and movement direction of the halting state don't matter, that's another few bits you can throw away.
So that gets you down to 54.02 bits before you even consider factoring out symmetries.