BB(6,2) > 1.7 x 10^646_456_993

[uni...@fu-solution.com]

please analyze this machine carefully - i still don't have enough
confidence in my new code, it was not reasonable to try to confirm it
with my old code and i'm not used to manual proving :).


1RB 1RH 0LC 0LD 1LD 1LC 1RE 1LB 1RF 1RD 0LD 0RA


following Shawn's example, i looked at an adjacent machines - these are
the productive ones:

* two complementing rules, probably infinite:

B1R H1R C0L D0L D1L B0R E1R B1L F1R D1R D0L A0R
B1R H1R C0L D0L D1L D1L E1R B1L F1R D1R D0L A0R

* hacked simulator to make a not entirely correct proof, probably
infinite:

B1R H1R C0L D0L D0R C1L E1R B1L F1R D1R D0L A0R
B1R H1R C0L D0L D1L C1L E1R B1L F0L D1R D0L A0R
B1R H1R C0L D0L D1L C1L E1R B1L F1R D1R B0R A0R
B1R H1R C0L D0L D1L C1L E1R B1L F1R D1R D1L A0R
B1R H1R C0L D0L D1L C1L E1R B1L F1R D1R D0L C0L

* don't know yet, looks infinite:

B1R H1R C0L D0L D1L C1L E1R B1L F1R D1R A0R A0R
B1R H1R C0L D0L D1L C1L E1R B1L F1R D1R D0L E0R

[Terry Ligocki]

If this is correct it’s amazing!

Sent by modern magic - TJL

> On May 22, 2022, at 6:18 AM, uni...@fu-solution.com wrote:
>
> please analyze this machine carefully - i still don't have enough confidence in my new code, it was not reasonable to try to confirm it with my old code and i'm not used to manual proving :).

> --
> 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/f995ab8182c7a8949538b7f7ce6468eb%40fu-solution.com.

[Shawn Ligocki]

Wow, that is quite a number! Very exciting! If confirmed, this is approaching the limit of what numbers can be stored directly in memory, any bigger and we'll have to use fancier math to keep track of things :)

After 10 min of simulation (in our code), I'm only up to 10^(1.3M) so this will take a while for me to confirm with software (maybe 4 days if it goes linearly ... never run simulation that long). If I get a chance I'll try analyzing by hand.

[Shawn Ligocki]

Haha, nevermind, my simulator is not linear at this scale, it's quadratic (takes 4x as long to 2x the number of digits. So my simulator is looking like it would take 7 years. I will definitely need to break out the pencil and paper!

[Shawn Ligocki]

OK, I can confirm this machine via human analysis. Congratulations Pavel!

In fact, I believe that this machine halts with exactly 2^2^31 ones on the tape (~1.7 x 10^646_456_993). At least, assuming I didn't botch my arithmetic! Here's my analysis:

Let D(a, b) ... = 0^inf <D 10^a 01^b ...

• Rule 2:  D(a, b+2) -> D(4a+6, b)
• Rule 2x: D(a, 2k+r) -> D( (a+2) 4^k - 2, r)

• Rule 3:  D(a+1, 0)    0^inf  ->  D(6, a)    0^inf
• Rule 4:  D(a+1, 1)    0^inf  ->  D(6, a) 11 0^inf
• Rule 5:  D(a,   1) 11 0^inf  ->  0^inf 1^2a+2 01 Z> 1 0^inf  =  Halt(2a+4)

Then:

• @11:     D(3, 0)
• Rule 3:  D(6, 2)
• Rule 2:  D(30, 0)
• Rule 3:  D(6, 29)
• Rule 2x: D(8 4^14 - 2, 1)  =  D(2^31 - 2, 1)
• Rule 4:  D(6, 2^31 - 3) 11
• Rule 2x: D(8 4^(2^30 - 2) - 2, 1) 11  =  D(2^(2^31 - 1) - 2, 1) 11
• Rule 5:  Halt(2 [2^(2^31 - 1) - 2] + 4) = Halt(2^2^31)

I have not calculated the steps, but it shouldn't be too hard to extend this analysis to include step counts.

-Shawn

[Terry Ligocki]

Wow, again! Congratulations Pavel and nice analysis Shawn (I haven't checked it but you're pretty skilled and reliable with these things - said the proud father, 😜)!

The fact that Pavel's new code can compute this (with a few caveats remaining) and it can be analyzed points to all of us making improvements in our codes and adding new, more efficient methods and implementations in addition to continuing to find new analysis tools (which may also become computational methods in the future).

So very exciting...

                                Terry J.

P.S. Also, since the (2,n) TMs seem to exceed the (n,2) TMs (for reasons mentioned in these discussions), what is waiting in the (2,6) TMs? Or even the (2,5) TMs?

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7CSuoJJ3UcCrMt9c6Ha8a_v_Ae10UDm0CGrtrJJwU-FnA%40mail.gmail.com.

--

---

Mistakes

It could be that the purpose of my life
is only to serve as a warning to others.

(Despair, Inc.)

[uni...@fu-solution.com]

On 2022-05-23 05:39, Shawn Ligocki wrote:
> In fact, I believe that this machine halts with exactly 2^2^31 ones on

> the tape.

true

[uni...@fu-solution.com]

On 2022-05-23 05:39, Shawn Ligocki wrote:

> OK, I can confirm this machine via human analysis.

thank you for your analysis :)

[nichol...@gmail.com]

The control flow graph is attached. This graph is also simple -- observe that state F will always reach state D, passing through A and possibly C along the way. The C node is reflexive.

Pavel, are you searching for these just by mark count? Have you found any that run longer but with fewer marks? In the past the longest-running machines have also had the most marks, so there hasn't been a need to distinguish.

On the BBB side things are quite a bit different, as the longest-running quasihalting machines tend to leave no marks at all! Why that should be the case is still unclear.

[Terry Ligocki]

My guess is the BBBs are hiding by covering up all their tracks but by doing so they aren't hiding very well, 🥴.  Seriously, that's an interesting observation!  And it, again, raises the question: Is this real in some sense, an artifact of what we can characterize in our searches, or an artifact of the relatively small TMs we can handle...

                                Terry J.

--
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/cc22f3c0-5638-4a06-a3dc-40e801345619n%40googlegroups.com.

--

---

There's always a reason
Behind the reason
When you look for a reason

       - The Reason (Carly Simon)

[uni...@fu-solution.com]

On 2022-05-23 13:38, nichol...@gmail.com wrote:
> Pavel, are you searching for these just by mark count? Have you found
> any that run longer but with fewer marks?
> In the past the longest-running machines have also had the most marks,
> so there hasn't been a need to distinguish.

just marks. computing steps usually requires "math" one level up from
what you use in accelerating rules / nonhalt proofs => most of the time
it lags behind in my simulator.

but to be precise, to this day i have tested uncategorized machines with
1 undefined transition from my old logs, as it was the most promising
place to look & i didn't have to spend time implementing search
infrastructure. => as soon as i debugged my implenentation, there were
only a few new numbers to see.

but it was good stress testing - this code should definitely handle a
full tm6 scan from single modern machine in reasonable time (when
complete)

// in some places, including here, i see BB function used as the max
number of steps, but it's defined as the max number of ones. i was not
aware of this schism until Shawn announced his record. when did this
started?

[nichol...@gmail.com]

I think the change in focus from marks to steps is due to Scott Aaronson. See https://www.scottaaronson.com/writings/bignumbers.html. His interest was in defining big numbers, and counting steps leads to bigger numbers than counting marks. Rado originally defined the Busy Beaver game in terms of counting marks, but he doesn't say why. It's just stipulated.

There are a variety of Busy Beaver-like questions that can be asked, all of the same form: for a program of length n, what's the greatest number of ___ that can be attained before halting? Define the following functions by filling in the blank:

  - S: steps (aka "shift")
  - C: traversed cells
  - M: marked cells (aka "sigma")

For any n, we have S(n) >= C(n) >= M(n), because a cell has to be traversed to be marked and a step has to be taken to traverse a cell. And so for any n, the values of C(n) and M(n) can be calculated given S(n). There is a straightforward decision procedure: just run all the machines for S(n) steps and count the marks for anything that halts within that time and take the max.

To me, the simplicity of this decision procedure means the step function is logically central.

It is true that S(n) can be given an upper bound in terms of M (or C), but the method for doing so is more convoluted. There's no way to calculate S(n) given M(n); the value of M for some k > n is required. All of these BB-like functions are co-computable in this sense.

It would be very interesting to know if there is some class for which the markingest machine is not the longest-running. Currently all the available evidence points to the mark champion also being the step champion, but there is no proof of that.

[Shawn Ligocki]

Yeah, I generally agree with Nick.

My interpretation is that BB() has always been a somewhat ambiguous notation. Before Scott Aaronson's 2020 paper, I think the standard was to use Sigma() for the marks function and S() for the shift/steps function (which come from Rado and Lin's first two papers). Pascal Michel uses this notation on his website. In the entire 17+ years I've been doing Busy Beaver stuff, I have felt that folks seemed "more interested" in the steps function. For example, proving things about it is easier, because (unlike the marks function) it monotonically increases the longer you run a machine, so you can make definitive statements like S(2, 4) = 3,932,964 or S(2, 4) > 10,000,000 (because you've simulated all machines for 10M steps and this was the one that halted latest). You can't really make any statements like this for the Sigma() function.

Then, in 2020, Scott Aaronson published a Busy Beaver review article. This introduced a bunch of new variants (like Beeping Busy Beaver and Lazy Beaver) which got a lot of discussion for a while. This is how Nick got into Busy Beaver (IIUC) and when my interest was rekindled as well. In this paper, Scott uses the notation BB() to refer to the shift/step function. Since this fit into my general preference as well, I've adopted that shorthand notation.

Nick, FWIW, the 3x2 case does have different marks and steps champions. But my guess is that for large examples, the "machinery" required to produce a Sigma() champion will make it a S() champion as well.

--

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/c6fa65a7-70ae-43f1-b1c8-8cde3ec59214n%40googlegroups.com.

[uni...@fu-solution.com]

interesting, thank you both. i will try to pay more attention to steps
then. for me it was an annoying second-class citizen, that is harder to
count and not worth devoting time to.

[Nicholas Drozd]

Thanks for the correction, Shawn!

Even if we say that the steps function is more important or whatever, counting marks still seems to be a pretty good strategy for searching. After all, the mark count provides a perfectly good lower bound for the step count, but as Pavel says it's much easier to calculate. So from a practical standpoint the mark function remains important.

This doesn't seem like something that Rado could have foreseen, but who knows?