Thoughts on the new champion

[nichol...@gmail.com]

Here are some general thoughts I had after reading Shawn's post.

1. Pavel's new champion has superseded the previous 7-state record held by Wythagoras. That program, as I understand it, was constructed by adding an extra state at the beginning and then dropping into a permuted version of Pavel's old champion program. Such a hand-modified program clearly has no chance of being the true champion, or even close to it. Anything a human would think to write out will inevitably have a computable quality to it, some kind of modular layout, and this simply cannot keep up with uncomputability. That said, if anyone wants to grab some glory, there is probably a way to add a new state to this new champion and obtain and new 7-state champ.

2. It's been a good season for Pavels: another Pavel recently came up with a tetrationally long running Game of Life program. See https://cp4space.hatsya.com/2022/06/23/tetrational-machines/. "Long-running" in the Game of Life setting apparently means running until "self-destruction", or until there are no more live cells. This seems somewhat more related to the Blanking Beaver problem (BLB). BLB is believed (at least by me) to be faster-growing than BB. Can we get some good lower bounds on BLB(6)?

3. There is also the Beeping Busy Beaver problem BBB. Back when the old champ reigned, I thought maybe it could be shown that BBB(5) > BB(6), at least as far as known lower bounds go. And pending verification that a certain Collatz-like function actually terminates, that would have worked. I think it might still be the case, but it will be harder to show now. BB(5) is not even 1.5 times greater than BBB(4), and there is a K such that BBB(K) > BB(K + 1). It is entirely possible that K = 5.

4. According to Shawn, we have 10 ↑↑ 15 < Marks(t15) < Shift(t15) < 10 ↑↑ 16. To return to our previous discussion of the relationship between marks and steps and the "true" Busy Beaver function, apparently it doesn't matter which one we pick -- we can hardly distinguish them anyway!

5. It's funny that the bounds are 10 ↑↑ 15 and 10 ↑↑ 16. They look like they should be pretty close, since 15 and 16 are pretty close, but in fact that upper bound is quite a big greater than the lower bound.

6. There is not any reason to believe that this is the true champion. I mean, not that I can do any better, but still! It certainly proves that 6-state machines can do some wild stuff, and with that in mind it would be imprudent to assume the wildness ends here.

7. If I understand the halting configuration properly, all but one of the marks are in a single contiguous block. If you change the halt instruction from 1RZ to 0RZ, then all the marks are together, with the machine head scanning the first blank next to the block. That is perfect standard configuration! This machine is very well-behaved. Does that mean anything? Should that be taken as evidence that it is or is not the true champion?

[Shawn Ligocki]

On Sat, Jun 25, 2022 at 11:05 AM nichol...@gmail.com <nichol...@gmail.com> wrote:

4. According to Shawn, we have 10 ↑↑ 15 < Marks(t15) < Shift(t15) < 10 ↑↑ 16. To return to our previous discussion of the relationship between marks and steps and the "true" Busy Beaver function, apparently it doesn't matter which one we pick -- we can hardly distinguish them anyway!

Yes, it's convenient that we don't need to argue over naming any more :) Once you get a machine in the tetration level, squaring has basically no effect.

5. It's funny that the bounds are 10 ↑↑ 15 and 10 ↑↑ 16. They look like they should be pretty close, since 15 and 16 are pretty close, but in fact that upper bound is quite a big greater than the lower bound.

Yes, proving these bounds was a little too easy since they are actually sooo far apart! I just posted a new article discussing potential notations with higher precision. In those notations, I prove that this machine runs in:

• 10↑↑15[↑4.0238] < s(t15) < 10↑↑15[↑4.0240]
• 10↑↑15.60463 < s(t15) < 10↑↑15.60466
  

Which (at least feels) precise.

6. There is not any reason to believe that this is the true champion. I mean, not that I can do any better, but still! It certainly proves that 6-state machines can do some wild stuff, and with that in mind it would be imprudent to assume the wildness ends here.

I agree, I think we're only started on this new journey!

7. If I understand the halting configuration properly, all but one of the marks are in a single contiguous block. If you change the halt instruction from 1RZ to 0RZ, then all the marks are together, with the machine head scanning the first blank next to the block. That is perfect standard configuration! This machine is very well-behaved. Does that mean anything? Should that be taken as evidence that it is or is not the true champion?

That's super interesting. This looks reminiscent of what Milton Green called a "Class G" machine (in his 1964 paper). Green builds off of this class of machines to manually construct a sequence of machines which demonstrate a sort of Ackermann function lower bound for BB(n). There are some caveats which make this machine (perhaps) not apply in to Class G:

1. Class G machines are not allowed to move past the position they halt on. This machine does.
2. Class G machines must halt at a specific position relative to their start location. I haven't checked this one, but I doubt it does.
3. Class G machines must compute some (well-define) function G(n) when starting (in this position) on n. But all we know about t15 is that it computes G(0) > 10↑↑15. We'd have to investigate what it did on different inputs to know if it would allow the kind of extension that Green used.

That said, it does look ripe for a code golfer to use as a basis to improve some bounds :)

[nichol...@gmail.com]

I think I can answer my own question here and establish an extremely modest lower bound for BLB(6).

Pavel's machine ends in this configuration: 1 Z> 0 1^N, where N is some huge number. Modify the D1 instruction so that D1 -> 1RE (instead of D1 -> 1RZ). Then it reaches the configuration: 1 E> 0 1^N. E0 -> 1LF, so we get F> 1^(2 + N).

Then we get F1 -> 0RE, E1 -> 0RB, and B1 -> 0RF. These three instructions work together to keep erasing and moving right, and this causes the whole block of marks to get erased. So BLB(6) > Steps(t15) + Marks(t15).

I'm not sure what state the machine is in after the last mark is erased. The most "well-behaved" outcome would be for it to end in state F. F0 -> 0RC, and then C0 -> 1LC, at which point it would spin out, nice and clean. If it ends in either E or B, something else happens that is less elegant.

[Shawn Ligocki]

A_16 = (3^M - 11) / 2 (for large M), so 3^M = 3 (mod 6) and thus A_16 = 2 (mod 3). Your variation (2+N = A_16 +1), so it does indeed have an exact multiple of 3 1s and so will end in F0 -> 0RC & C0 -> 1LC and spin out. Good guess :)

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/8d0b5c67-2f2a-465e-93fb-96ade1ffdbecn%40googlegroups.com.

[Shawn Ligocki]

Another BBB variation of Paval's machine: Modify D1 -> 1RG and add G0 -> 1LC.

Now:

• C(4k) ->
• 1 G> 0 1^N
• 1 <C 1^N+1
• <A 1^N+2
• 1 B> 1^N+2
• 1 0^N+2 B>    (because N+2 % 3 = 0 as mentioned in the previous email)
• ...
• 1 0^N+1 11 0^5 C> = C(N+1)

Where N+1 = (3^{k+3} - 11) / 2

So, now we have the following rules:

• Rule R0: C(4k  ) -> C((3^k+3 - 11) / 2)
• Rule R1: C(4k+1) -> C((3^k+3 - 11) / 2)
• Rule R2: C(4k+2) -> C((3^k+3 - 11) / 2)
• Rule R3: C(4k+3) -> C((3^k+3 +  1) / 2)

Obviously they will never halt, but the question is, will we apply Rule R0 infinitely many times? If not, then this is a BBB(7, 2) competitor (with beeping state G, since state G is only reached via Rule R0).

Of course, my guess here is that R0 should be hit infinitely often ... but to prove this requires proving a "Collatz-like" statement ...

[Pascal Michel]

I give here more analysis about the machine M that Shawn ligocki found on May 27, 2022, with sigma(M) > 4^4^4^4^4^7.

(1) I  use Shown's configurations E(n,m) = ...0 (E0) 0^n 100 (01)^m 0...

For all k >= 0,

(a) ...0(A0)0;;; --( 5 )--> E(3,0)

(b) E(3k,m) --( t_0(k) )--> E((19*4^k - 13)/3, m + 1)

  with t_0(k) = (1444*16^k + 665*4^k - 1515k - 759)/135

(c) E(3k + 1,m) --( 6k + 10 )--> ...0 1 (H1) 0 (110)^k 0 (01)^(m + 1) 0...

(d) E'3k + 2) --( t_2(k) )--> E((28*4^k - 13)/3,m + 1)

  with t_2(k) = (3136*16^k + 980*4^k - 1515k - 1011)/135

(2) With the notations of Wietze Koops (email on May 30, 2022), we have

 sigma(M) = 2 k6 + 9, with k6 = (19*4^k5 - 16)/9.

The leading term in the time of the computation s(M) is 1444*16^k5/135 in t_0(k5),

so s(M) is approximately  (3/5) sigma(M)^2.

(3) We have sigma(M) > 4^4^4^4^34587.539 > 10^10^10^10^20823.523.

Pascal