BB(6, 2) > 10^78913

[Shawn Ligocki]

Hi all, I have exciting news. After a bunch of Beeping Busy Beaver stuff, I decided to dip my toes back into the vanilla Busy Beaver 6x2 enumeration and I believe I've found a new champion!

1RB 1RC  1LC 0RF  1RA 0LD  0LC 0LE  1LD 0RA  1RE 1RZ

which looks like it runs 9.6 x 10^78,913 steps and writes 6.0 x 10^39,456 symbols (exactly 3/2 * 2^2^17 + 1 to be precise).

I have written up an analysis and a precise value for the number of steps as well at https://www.sligocki.com/2022/05/13/bb-6-2-e78913.html .

Is anyone in a position to verify this machine using independent code?

Using our codebase, you can simulate it with:

$ Code/Quick_Sim.py Machines/6x2-e78913

• Runs for about 8min, ~5.6M simulator steps

$ Code/Quick_Sim.py --no-steps Machines/6x2-e78913

• Runs in about 1min, does not compute step count

$ Code/Quick_Sim.py --recursive Machines/6x2-e78913

• Runs for about 36s, ~5.3k simulator steps
• Using "recursive" rule proving mechanism which allows proving rules built on top of other rules. This code is a bit more experimental.

$ Code/Quick_Sim.py --recursive --no-steps Machines/6x2-e78913

• Runs in about 1s, recursive rules, does not compute step count

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

hats off to you :).
 
i can confirm the number of ones.

it looks like it should still be possible to simulate this machine with Heiner's simulator (in a few days using `mawk`, if i remember correctly). if not, i can play with my code to calculate the steps correctly.

Dátum: piatok 13. mája 2022, čas: 17:41:20 UTC+2, odosielateľ: slig...@gmail.com

[Nicholas Drozd]

Fantastic! You know, I actually took a crack at 6x2 myself over the past few weeks. Except, instead of a "40-node (500 core) compute cluster", I just used a single modest desktop. The results were ... not quite this good. I'll include what I found here just for completeness.

  * 1RB 0RC  1RC 0LC  1RD 1RA  1RE 0LF  1LD 1R_  0LA 1LF
  Steps: 2.4 x 10^1224
  Marks: 2.9 x 10^612

  * 1RB 0RC  1RC 1RB  1RD 1RA  1RE 0LF  1LD 1R_  0LA 1LF
  Steps: 1.2 x 10^1224
  Marks: 2.9 x 10^612

As with the Mother of Giants, these two differ at just one instruction. Maybe that's worth looking into further?

Now, on to the new champion. I've attached the control flow graph, which has some interesting features.

1. It is IRREFLEXIVE (no states jump to themselves). Pavel's previous champ is also irreflexive, but Pavel's champ before that is not.

2. According to the graph reduction procedure, this program is NOT SIMPLE. Out of its six nodes, there is a four-node irreducible kernel consisting of states A, C, D, and E. (Observe that any two-color halting program will always lose its halting state to reduction, which in this case is state F. State B is eliminated because it is only reached from A.)

3. Nevertheless, there is some kind of interesting pattern here. The blue arrows indicate scanning a blank and the red arrows indicate scanning a mark. Well, ignoring state B and F, the blue arrows all go clockwise and the red arrows all go counterclockwise. Pavel's previous champ has this same quality. Does this mean anything? Does it help us understand the program's structure in a meaningful way? IS IT SPAGHETTI?

Shawn, is the search still running? What kind of parameters did you use (time / steps per program, etc)? The usual way to search is: while (search && found something) { bump parameters }. Given that you found something, does that mean you'll keep going?

[Nicholas Drozd]

Perhaps my own 6x2 search strategy will be of some interest in light of this new data.

Suppose you are working with limited hardware. Exhaustive search is definitely out of the question for 6x2, even using Brady's algorithm. Is there anything that can be done about this?

My idea was to make certain predictions about what a champion program might look like, and then to restrict the search to just programs with those properties. Ideally these properties can be applied to partially constructed programs. We want to prune the tree as early as possible to avoid doing any unnecessary work. Aggressie, speculative pruning is the only way to make the task even remotely feasible.

Here are the predictions I made.

Prediction: There shouldn't be too many right-shifts. Specifically, no more than seven of the twelve shifts should be to the right.
Outcome: Correct. The new champ has seven right-shifts.

Prediction: At least two of the left-shifts should occur on zero instructions.
Outcome: Correct. The new champ has three zero-left instructions.

Prediction: There should be at least three erase instructions (instructions that print a blank over a mark).
Outcome: Correct. The new champ has four erase instructions.

Prediction: Upon scanning a blank, a mark will always be printed.
Outcome: WRONG. The new champ has D0 -> 0LC. This is different from all champs in lower classes as well as Pavel's previous champ.

Prediction: The program should be simple according to the graph reduction procedure.
Outcome: WRONG. But perhaps there is a way to extend the procedure to include this case (see previous message).

Prediction: The program should be irreflexive.
Outcome: Correct.

So I would never have found Shawn's new champ. This does not necessarily mean that the predictions are wrong with respect to the "true" champion. And of course, there is no particular reason to believe that this is the true champion. "We looked and couldn't find anything better, so we believe this is the real value." How many of us here have said that? How often did it turn out to be false?

As for me, the weather is starting to get warm where I am, and it's just too hot in my apartment to keep searching :)

[Terry Ligocki]

Congratulations!

Sent by modern magic - TJL

On May 13, 2022, at 8:41 AM, Shawn Ligocki <slig...@gmail.com> wrote:



--
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/CADhnJ7ASpYyhuC2ebtgm1UWCdQkgjNJgwAU6_6tk9t8U0_Gq_g%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

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

this one should show up in your logs ;) > 10^98641

`1RB 1RH  1RC 1RA  1RD 0RB  1LE 0RC  0LF 0LD  0LB 1LA`

Dátum: nedeľa 15. mája 2022, čas: 3:22:27 UTC+2, odosielateľ: tjli...@gmail.com

[Nicholas Drozd]

Wow! Confirmed:

Steps: 5.4 x 10^197,282 (5428...4808)
Marks: 2.0 x 10^98,641  (2017...1356)

Could you tell us how you found that one?

[Shawn Ligocki]

Quick analysis note on Pavel's machine (1RB 1RH  1RC 1RA  1RD 0RB  1LE 0RC  0LF 0LD  0LB 1LA):

• 01^2k+1 D>  ->  01^(20 2^k - 8) D>
• 01^2k D>  ->  Halt(10 2^(5 2^k - 4) - 5)

@step 9 it's in config 01^3 D>

• -> 01^(20 2^1 - 8) D> = 01^32 D>
• -> Halt(10 2^(5 2^16 - 4) - 5)

which is the same number of symbols I get through simulation (>10^98,641)

--

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/CABAiW0qitb_HicTDLvfsF7GQ7JC3hLjdHQkY9JT%2BNnX3Zz4tCA%40mail.gmail.com.

[Terry Ligocki]

Pavel - I must say that you are a wonderfully concise person! I do wonder if you have a list many (6,2) results and simply disclose them as needed, :-), or if each time this problem heats up a bit you do a bit more investigation with the improved hardware of the time and maybe improved code.

In any case, I find the group of people investigating this periodically invigorating, fun, and full of surprises!

                                Terry J.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/fe6ff31f-590b-43cd-b85e-8f0e3d22bf61n%40googlegroups.com.

--

---

Champagne, cocaine, gasoline
And most things in between...

       - Don't Threaten Me With A Good Time (Panic! At The Disco)

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

On 2022-05-15 18:13, Nicholas Drozd wrote:
> Could you tell us how you found that one?

a year and a half ago i spent some time rewriting and slightly improving
my old code in rust. i didn't get too far, the code is in a really raw
dev state & probably often incorrect - i wouldn't bother running it in
search mode yet if i didn't see how well it handles Shawn's machine
(4.5ms without computing steps & printing).

i intended to continue when a new threadripper comes out (+winter to use
the burnt electricity for good secondary use), but Shawn wrote it
correctly - to win with that machine after 12 years of progress would be
too cheap :).

i have logs from my first attack, so i cheated and haven't run a full
search yet - just looked for an easy win there - however, i didn't
expect to find something so quickly. probably more to come.

[Terry Ligocki]

Thanks for the update. It sounds like you have a very efficient code! Happy hunting...

                                Terry J.

---

When you sleep, where do your fingers go?

       - When You Sleep (Cake)

[Nicholas Drozd]

Pavel, is there any chance you could put your code online? I google-translated your old thesis, but that only got me so far :)

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

On 2022-05-16 19:30, Nicholas Drozd wrote:
> Pavel, is there any chance you could put your code online? I
> google-translated your old thesis, but that only got me so far :)

it should be possible to download my old code somewhere along the
thesis, but as you experienced with the text - even for me it was easier
to invent it from scratch than to understand myself from a decade ago -
it's really horrible experimental c++. and it's overly complicated and
ineffecient compared to what it can handle in the end => so i started
new version in rust :).

i can opensource my new code, but:

* it will not help you right now - 2 most important parts - computing
nested minima & divisibility conditions are not yet right. i
simplified/optimized that part compared to old code, but it's tricky to
get it right - that was the place i left that code 1.5y ago - i needed
gui to debug it and gui is one of the last things that doesn't have a
success story in rust yet. but I finally hacked one :)

* rado's `busy beaver competition` would lost its `competition` part.
any idea how to frame collaborative effort afterwards?

however, science is about making progress, not winning, and my code is a
good starting point from where to hunt interesting machines - for
example doomsday variation of those machines Shawn is searching for - a
machine that halts, but it's not possible to compute the number. (the
new code has been shaped to make it easier to implement the 'rozbor
pripadov' section from my thesis to make it possible). plus there are
more things i would like to see implemented, but it would probably
exceed my time budget for this "round" - happy to share the load.

and the final quest - it's time to finalize BB(5) and get close to BB(6)
- but there are real monsters that would need yet another proof/tape
representation.

[Shawn Ligocki]

I can confirm this machine runs for 5.4 * 10^197,282 steps and leaves 2.0 * 10^98,641 symbols.

Nice find, Congratulations Pavel! You couldn't let me hold the record for 3 days could you :P

This machine takes 9s to simulate without computing steps (with our code), but 30min with computing steps (so it timed out in my search). It appears to spend almost 100% of its time applying a rule over and over again.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/fe6ff31f-590b-43cd-b85e-8f0e3d22bf61n%40googlegroups.com.

[Terry Ligocki]

Wow, congratulations - things are heating up in BB-land!

Sent by modern magic - TJL

On May 15, 2022, at 4:59 AM, uni...@fu-solution.com wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/fe6ff31f-590b-43cd-b85e-8f0e3d22bf61n%40googlegroups.com.

[Shawn Ligocki]

For context: I originally sent this message 2 days ago (but it looks like it got stuck in the moderation queue).

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

On 2022-05-15 18:05, Shawn Ligocki wrote:
> You couldn't let me hold the record for 3 days could you :P

:D sorry, i really contemplated for like 12 hours if this is the time to
give up control... then i started hacking.

i expected you will beat me and managed to not work on it preemptively,
but that number was unsatisfactory for proper win ;).

[Shawn Ligocki]

Pavel, for what it's worth, my dad and I made our code public several years ago and I have been very happy with the result, which has mostly been that now Nick runs it in various ways I had not expected and we motivate each other to think of new ideas. Of course, maybe this is easier for me to say when I have access to a 40-node cluster :) I'm not sure how I would feel if someone used my code to find a new champion, maybe both jealous and proud? Perhaps we should give credit to the code author as well as the person who found a machine in some way? In general, I am very excited about growing and nurturing the Busy Beaver community by providing tools that make it easier for new folks to get involved. But, of course, I also want to win :)

It's very exciting to hear about your process. Before your confirmation email, I was not sure if you were still doing Busy Beaver things (or if your email was still working), but now I find out that you were following along on my journey and even anticipated that I might get a 6x2 record, very sneaky! I get a sense that after a decade of quiet, the competition might become heated again :)

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

[Nicholas Drozd]

It's often said that as the number of states increases, the number of TMs grows astronomically. That's a great metaphor for what we're doing. If TMs are celestial objects, then the simulator is the telescope. You point the telescope somewhere and you look and see what's there. If you don't see anything, it could be because there is nothing there; or there could be something there, but the telescope isn't powerful enough to see it. And there's the question: where exactly should you look? Everywhere, if you can afford it, and only in some carefully selected places otherwise.

Around January I realized that my own "telescope" wasn't going to cut it, so I switched to using the Ligockis'. That certainly improved my search results! I also continued to improve my own program generation infrastructure, and that helped too.

Just as we might say "A found a new star using a telescope developed by B", it would also be reasonable to say "A found a new TM using a simulator developed by B". For a few weeks (days?) I held the BBB(5) record, and that's how I would have described it. Not that it matters, because Shawn ended up finding a better one anyway!

"Fortunately" there is no money involved, so I think the issue of credit can be handled fairly and cordially. And I would also say (and perhaps others will agree) that any new progress is exciting to see and ultimately benefits everyone, if for no other reason than that it shows that progress is still possible. Just look at the events of the past few days!

[Pascal Michel]

What is the number of 1s left on the tape by the Pavel Kropitz's machine with s(M) > 5.4 x 10^197282 when it halts?

For Nicholas Drozd, in his mail on May 15, 2022, it is

 2017...1356, an even number.

For Shawn Ligocki, in his mail on May 16, 2022, it is

 10 x 2^(5 x (2^16) - 4) - 5, an odd number.

Which one is right?

The right number is 2017...1356 = 10 x 2^(5 x (2^16) - 4) - 4 (see a forthcomming analysis).

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

On 2022-05-23 09:29, Pascal Michel wrote:
> Which one is right?
> The right number is 2017...1356 = 10 x 2^(5 x (2^16) - 4) - 4 (see a
> forthcomming analysis).

true, 201-98636-356

[Shawn Ligocki]

Yes, I was off by one in my email!

--

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/4caea63d-9adb-426d-b2b4-30814b1c6e06n%40googlegroups.com.

[Terry Ligocki]

Now I might have to disown Shawn, 🤣.  Just kidding, still proud - Terry J.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7CfBpZrUYjtso7VmWS-TN_4Cpir6y44_P2yxkoD2%2BQ-Kg%40mail.gmail.com.

---

Idiocy

Never underestimate the power of stupid people in large groups.

(Despair, Inc.)

[Pascal Michel]

I give here more analysis on Pavel's machine M

1RB 1RH 1RC 1RA 1RD 0RB 1LE 0RC 0LF 0LD 0LB 1LA

with s(M) > 5.4 x 10^197282 and sigma(M) > 2.0 x 10^98641,

using Shawn's configurations C(n) = ...0(01)^n (D0)0...

We have

 ...0(A0)0... --(9)--> C(3)

 C(2k) --( t(2k) )--> ...011(H1) (01)^(10*2^(5*(2^k) - 4) - 7)0...

 C(2k + 1) --( t(2k + 1) )--> C(20*(2^k) - 8),

with

 t(2k) = 400*(4^(5*(2^k) - 4) - 1)/3 + 400*(4^k - 1)/3 - 240*2^(5*(2^k) - 4) - 50*(2^k) + 42*k + 374

 t(2k + 1) = 1600*(4^k - 1)/3 - 600*(2^k) + 42*k + 751

So

 ...0(A0)0...

 --(9)--> C(3)

 --(1193)--> C(32)

--( t(32) )--> ...011(H1) (01)^-(10*(2^327676) - 7)0...

We have

 s(M) = 400*(4^327676 - 1)/3 - 240*(2^327676) + 572,659,031,448

 sigma(M) = 10*(2^327676) - 4