BB(6, 2) > 4^4^4^4^4^7

[Shawn Ligocki]

I am excited (and nervous) to share with you all a machine which (I calculate) leaves M > 4^4^4^4^4^7 marks on the tape upon halting:

1RB 0LA  1LC 1LF  0LD 0LC  0LE 0LB  1RE 0RA  1RZ 1LD

Please let me know if anyone can confirm (or dispute) this result! Please analyze carefully, this bound was computed completely by hand after I developed the rules based on my simulator code. I have run some smaller variants through my code and feel somewhat confident in the result, but I think it's definitely possible that I made an arithmetic mistake (which might lead to, say, a different number of 4s in the tower).

I can give an even slightly tighter bound of

• 4^4^4^4^34_587 < M < 4^4^4^4^34_589 and
• 10^10^10^10^20_822  <  M  <  10^10^10^10^20_825
  

Which would put it smaller (but within "striking distance") of Wythagoras's 7x2 bound.

Here is my Analysis: Let:

• E(n, m) = 0^inf <E 0^n 100 01^m 0^inf

The rules I believe it follows are:

• Rule R0: E(3k  , m) -> E((19 4^k - 13) / 3, m+1)
• Rule R1: E(3k+1, m) -> 0^inf <Z 11 011^k 00 01^m+1 0^inf = Halt(2k + m + 3)
• Rule R2: E(3k+2, m) -> E((28 4^k - 13) / 3, m+1)

And the TM is in config E(3, 0) at step 5.

"Computing" this "Exponential type" Collatz-like function (once it gets large) is not trivial and I had to use the methodology similar to "Cloudy176" (referenced by Pascal Michel). Specifically, you need to be able to figure out what the remainder is mod 3 without actually computing the full 4^k (once it is too big to fit in memory fully). This is the part of the computation that I am the most nervous of having made an arithmetic mistake in, so I would love if anyone else to could carefully try to recreate this analysis (for this reason, I have not included the sequence of Rules used to get from E(3, 0) to Halt(...) in hopes of getting an independent verification!).

-Shawn

[Terry Ligocki]

Wow, I hope the analysis holds up! This would be an incredible result for BB(6,2). Maybe this will be worthy to stand for a week or two, 🤣...

                                Terry J.

P.S. Some how I've gone from research in this area to "color commentator"! Well, I'll be retired at the end of next week and then look out, 🤪...

--
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/CADhnJ7CxnteYkHgXx6kWQyDZnNYvUTPb%2BZGQChEx%2Bnw3Rfma7w%40mail.gmail.com.

--

---

Bitterness

Never be afraid to share your dreams with the world,
because there's nothing the world loves more
than the taste of really sweet dreams.

(Despair, Inc.)

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

this one looks like a winner :D. i would like to hear the story behind
it.

[Nicholas Drozd]

I can't confirm or deny, but here's the CFG. It's pretty simple, with three reflexive nodes. The branching nodes are B and D. B always reaches D via C or F, and D always reaches B either directly or via E and A.

[Wietze Koops]

Congratulations on this great result!  I can confirm the result. Here is my analysis.

First note the following (similar to the result in the linked proof by Cloudy176): if we know the residue class of n mod 3^{e+1} for some e, then writing n = 3k+ r with r in {0, 1, 2} we know the residue class of k mod 3^e.
Since 4^{3^e} = 2^{2*3^e} = 1 mod 3^{e+1} by the Euler-Fermat theorem this implies that we know the residue class of 4^k  mod 3^{e+1}, so we know the residue class of (19 4^k - 13)/3 and (28 4^k - 13)/3  mod 3^e.

Based on this we have the following:
E(3, 0) -> E(21, 1) -> E(103761, 2) -> E( (19 * 4^34587  - 13)/3, 3) -> E(n4, 4)
             -> E(n5, 5) -> E(n6, 6) -> Halt(2/3*(n6-1)+9).
where n4, n5 and n6 are given below.
the first two steps can be confirmed by direct calculation.
Then note that 103761 = 0 mod 243, so in particular 0 mod 3. So k2 = 34587 = 0 mod 81. Let n3 = (19 * 4^k2  - 13)/3.
Then n3 = (19 * 4^k2 - 13)/3 = (19 * 4^0 - 13)/3 = 2 mod 81, so in particular 2 mod 3. So k3 = (19 * 4^k2 - 19)/9 = 0 mod 27, where n3 = 3 * k3 + 2. Let n4 = (28 * 4^k3  - 13)/3.
Then n4 = (28 * 4^k3 - 13)/3 = (28 * 4^0 - 13)/3 = 5 mod 27, so in particular 2 mod 3. So k4 = (28 * 4^k3 - 19)/9 = 1 mod 9 , where n4 = 3 * k4 + 2.  Let n5 = (28 * 4^k4  - 13)/3.
Then n5 = (28 * 4^k4 - 13)/3 = (28 * 4^1 - 13)/3 = 6 mod 9, so in particular 0 mod 3. So k5 = (28 * 4^k4 - 13)/9 = 2 mod 3 , where n5 = 3 * k5.  Let n6 = (19 * 4^k5  - 13)/3.
Then n6 = (19 * 4^k5 - 13)/3 = (19 * 4^2 - 13)/3 = 1 mod 3, so the machine halts.
We have 2/3*(n6-1)+9 >  2/9 * (19 * 4^k5  - 13) > 2/9 * 18 * 4^k5 > 4^k5,
and k5 =  (28 * 4^k4 - 13)/9 > 3*4^k4 and k4 =  (28 * 4^k3 - 19)/9 > 3*4^k3 and k3 = (19 * 4^k2 - 19)/9 > 2*4^34587. So in particular M > 4^4^4^{2*4^34_587} > 4^4^4^4^{34_587.5}.
When using powers of 10 instead we have M > 4^{3*4^{3*4^{2*4^34_587}}} = 64^64^10^10^{34_587*log_{10}(4) + log10(log_{10}(16))} > 10^10^10^10^{20_823.5}.

 
To have another confirmation, here is an analysis using different configurations. Let s be an arbitrary string, and let 

• D(a, b, s)  = 0^inf <D 1^a (011)^b 00 s  

If b>=1 then D(a,b,s) reduces to D(4a+1, b-1, s).

So D(a, b, s) reduces to D(4^b*a+(4^b-1)/3, 0, s).

Also, we have

• D(3k+1,0,s) -> Halt(8k+3+#s) with #s denoting the number of marks in s. 
• D(3k+2,0,s) -> D(2, 4k+1, 01s) -> D((28 4^{4k} - 1)/3, 0, 01s)
• D(3k,0,s) -> D(6, 4k-2, 01s) -> D((19 4^{4k-2} - 1)/3, 0, 01s)
  

Then we have 

D(6, 0, 01) -> D(25941, 0, (01)^2) -> D((19 4^34586 - 1)/3, 0, (01)^3) -> D(a4, 0, (01)^4)

                   -> D(a5, 0, (01)^5) -> D(a6, 0, (01)^6) -> Halt(8/3*(a6-1)+9),

where 25941 = 183 mod 243 (so 0 mod 3), and (19 4^34586 - 1)/3 = 62 mod 81 (so 2 mod 3), and a4 = 2 mod 27 (so 2 mod 3),

and a5 = 0 mod 9 (so 0 mod 3), so a6 = 1 mod 3, and the machine halts (for these computations I used Python to do the modular exponentiations).

It can also be shown that D(x, 0, (01)^m) reduces to E(4x - 3, m) which links the two analyses, but it is nice to see the modular arithmetic work out in two different analyses.

[Terry Ligocki]

Welcome to the group Wietze! I'm sure Shawn will be happy to see the confirmation. Do you have an overall interest in the area? I hope we will hear more from you in the future...

                                Terry J. (Ligocki, tjli...@gmail.com)

--
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/d33e8c7e-7ece-4abc-86c0-a05922a0c909n%40googlegroups.com.

---

Every hour wounds, the last one kills - old saying

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

On 2022-05-27 18:13, Shawn Ligocki wrote:
> I am excited (and nervous) to share with you all a machine which (I
> calculate) leaves M > 4^4^4^4^4^7 marks on the tape upon halting:
>
>> 1RB 0LA  1LC 1LF  0LD 0LC  0LE 0LB  1RE 0RA  1RZ 1LD

i'm trying to implement a limited form of expressions in exponents &
after 2 days of hacking, it looks like it can handle your machine (but
can't produce such beautiful exponents; or there is some another problem
left)

1 H> 1 {0 1^2}^((76*(4^((112*(4^((112*(4^((76*(4^((76*(4^(6)) - 22)/9))
- 28)/9)) - 28)/9)) - 22)/9)) - 16)/9) 0^2 {0 1}^7

while we are at analyzing - can you take a look at this machine?

1RB 0LD 1RC 0RF 1LC 1LA 0LE 1RH 1LF 0RB 0RC 0RE

my simulator generates this output, but it's even harder to be sure if
it's correct than after previous round of hacking. my code badly needs a
competition break to stabilize & my brain to learn modarithmetic hackery
:).

1 H> 0
1^((81*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^(1)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 19)/8)) - 13)/2)

[Shawn Ligocki]

This is all very exciting and I hope to respond to all of you with more thoroughly as soon as I get a chance. For now, I am very busy with a recent move and guest visiting. But it is nice to meet you, Wietze. Great to hear your confirmation of my analysis and your new analysis (which I haven't had a chance to dig into yet). Pavel, I have an exciting story to tell about how I found this machine! (But it will have to wait a bit).

Pavel, I have done a preliminary analysis of your new machine and I got the bound M > 3^3^3^3^3^3^3^3^3^3^3^3^22_144 > 3^3^3^3^3^3^3^3^3^3^3^3^3^3^2  (That is a tower of 12 3s with 22_144 on top or a tower of 14 3s with 2 on top). I think this is one 3 less than in your tower, so I'm guessing that one of us has made an error in evaluating the number of times that the rules are applied before the TM halts. FWIW, here are my rules and sequence:

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

•   @45: C(5, 1)
•   R1:  C(35, 1)
•   R3:  C(88_574, 1)
•   R2:  C((3^22_146 - 11) / 2, 1)   # ...1110111011100000000011111111
•   R3:  C(> 4 3^3^22_144)           #   ...11010011110001101110000010
•   R2:  C(> 4 3^3^3^22_144)         #     ...011111101000110010111111
•   R3:  C(> 4 3^3^3^3^22_144)       #       ...0011101101101010100010
•   R2:  C(> 4 3^3^3^3^3^22_144)     #         ...01110111010110001111
•   R2:  C(> 4 3^3^3^3^3^3^22_144)   #           ...111111001110111010
•   R2:  C(> 4 3^^7^22_144)          #             ...1110111001011011
•   R3:  C(> 4 3^^8^22_144)          #               ...01011101110001
•   R1:  C(> 4 3^^9^22_144)          #                 ...110111010111
•   R3:  C(> 4 3^^10^22_144)         #                   ...0101100110
•   R2:  C(> 4 3^^11^22_144)         #                     ...01011000
•   R0:  Halt(> 4 3^^12^22_144 > 4 3^^14^2)

But I am also pretty tired after a long day so could have made a mistake here ...

Either way, it looks like you've once again taken the lead in this 6x2 BB race. Nice work! I predicted I might get at least a week before you updated your code. But as before, you are extra fast :) Well played!

-Shawn

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

[Shawn Ligocki]

Oops, forgot to mention:

• C(n, m) = 0^inf 1 0^n 11 0^3m+2 C> 0^inf
  

[Nicholas Drozd]

CFG for the new one attached. Nodes C and D can be eliminated, but nothing else. That leaves a 4-node kernel consisting of A, B, E, and F. So we can say that from a control flow standpoint, this program is fairly complex, but not maximally so.

[Pascal Michel]

Just a note about notations for big numbers.

Citing "The book of numbers", by Conway and Guy (1996), p.60, the arrow notation, defined by Knuth in 1976, is such that

 m^n is  m x m x ...x m,

 m^^n is m^m^ ...^m,

 m^^^n is m^^m^^ ... ^^m,

and so on, with n copies of m in each case, and the expression being evaluated from the right.

So writing  3^^12^22144,  to denote 3^ ... ^3^22144 with 12 copies of 3, is misleading.
It is not  3^^(12^22144), which is 3^3^ ...^3, with 12^22144 copies of 3.

it is not  (3^^12)^22144, which is (3^ ...^3)^22144 (12 copies of 3) = 3^(22144 x (3^ ... ^3))

How to denote this number? I don't know.

In my web pages, I evade the problem by writing that the new machine has s(M) > 10^^13.

[Pascal Michel]

About the last (6,2)-Pavel Kropitz machine.

There is a problem with the number of ones left on the tape

Everyone agrees that it is a tower o powers of 3, ending with something like 22144.

But

 - Pavel found 13 3s in the tower,

 - Shawn found 12 3s in the tower,

 - I find 14 3s in the tower.

The list of applications of rules during the computation that I find is not the same as Shawn's.

My list: R1 R3 R2 R3 R1 R3 R2 R3 R1 R3 R1 R3 R2 R3 R1 R0 Halting

I hope someone will resume the study and find which is the right result.

Pascal

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

On 2022-06-03 09:26, Pascal Michel wrote:
> Everyone agrees that it is a tower o powers of 3, ending with
> something like 22144.
> But
> - Pavel found 13 3s in the tower,
> - Shawn found 12 3s in the tower,
> - I find 14 3s in the tower.

my raw output is

1 H> 0
1^((81*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^((27*(3^(1)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 1)/8)) - 17)/8)) - 3)/8)) - 17)/8)) - 1)/8)) - 19)/8)) - 13)/2)

==

14 3s
&
((27*(3^((27*(3^(1)) - 17)/8)) - 3)/8) == 22143 (+ some small value
propagated from coefficients)

[Shawn Ligocki]

Aha, I had made an arithmetic mistake in my analysis (turns out 3^3 = 27 (not 9), sigh). After fixing this mistake, I get the same sequence of rules as Pascal: 1, 3, 2, 3, 1, 3, 2, 3, 1, 3, 1, 3, 2, 3, 1, 0. And AFAICT, Pavel's expression also encodes within it the same sequence.

Here is a more detailed output from my program. The numbers are: iteration #, n % 4, trailing bits of n, trailing bits converted to base 10

0 1 00000000000000000000000000000101 5

1 3 000000000000000000000000100011 35

2 2 0000000000010101100111111110 88574

3 3 10111011100000000011111111 49152255

4 1 111011010101001010000101 15553157

5 3 0110000011100001100011 1587299

6 2 00110110001111011110 222174

7 3 111010100010101111 239791

8 1 0110011011111101 26365

9 3 11000101111111 12671

10 1 001111000101 965

11 3 0010000011 131

12 2 11001110 206

13 3 000111 7

14 1 1001 9

15 0 00 0

16

So we start with C(5, 1) with 32 bits of precision. Each time we iterate we lose two bits of precision. The first 3 are all exact (5, 35, 88574) and match the numbers I listed above. Then we get to the situation where we are throwing away leading bits. So:

• At iteration 3:  we have (27 * 3^((88_574-2)/4) - 11) / 2  ≡  49_152_255 (mod 2^26)  =  4 * 12_288_063 + 3
• At iteration 4:  we have (27 * 3^12_288_063 + 1) / 2  ≡  15_553_157 (mod 2^24)  =  4 * 3_888_289 + 1
• ...
• At iteration 13: (27 * 3^((206 - 2)/4) - 11) / 2   ≡  7 (mod 2^6)  =  4 * 1 + 3
• At iteration 14: (27 * 3^1 + 1) / 2 = 41  ≡  9 (mod 2^4 = 32)  =  4 * 2 + 1
• At iteration 15: (27 * 3^2 - 11) / 2 = 116   ≡  0 (mod 2^2 = 4)  =  4 * 0 + 0
• At iteration 16: Halt!

So I agree with Pascal that the lower bound is a tower of 14 3s topped by something about 22_144. So, I think we are all in agreement on this machine now :)

I agree that my 3^^14^22_144 notation was sloppy in the way you explained Pascal :) I do think it would be useful to have a short notation for this sort of thing maybe you could write something like 3^^14(^22_144) or 3^^14(...^22_144) or something similar? Please share your ideas everyone on what notation would be unambiguous and useful. Of course, in many cases, this level of detail is not necessary and something like 10^^15 should suffice. But if we find two with the same 10^^k notation, we'll need some ways to delineate them!

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

[Pascal Michel]

(1) i confirm that the final configuration 

  1 H>0 1^((81* ... - 13)/2)

of the (6,2) - machine M with s(M) > 10^^15, given by Pavel in his mail on May 30, 2022, is correct.

In this configuration:

 - the terms -1 corresponds to rules R1,

 - the terms -3 corresponds to rules R2,

 - the terms - 17 corresponds to rules R3.

(2) Despite the big numbers involved in the computation, it is easy to prove the lower bound on sigma (M).

It is sufficent to apply the rules R1, R2, ..., first modulo 2^17.

The order of 3 modulo 2^n is 2^(n - 2) if n > 2, so, at each application of a rule, the modulus is divided by 2, until we get a number divisible by 4 and apply rule R0.

[Shawn Ligocki]

On Tue, Jun 7, 2022 at 3:38 AM Pascal Michel <pascalm...@gmail.com> wrote:

(2) Despite the big numbers involved in the computation, it is easy to prove the lower bound on sigma (M).

It is sufficent to apply the rules R1, R2, ..., first modulo 2^17.

The order of 3 modulo 2^n is 2^(n - 2) if n > 2, so, at each application of a rule, the modulus is divided by 2, until we get a number divisible by 4 and apply rule R0.

Nice work Pascal. Could you explain this part in a little more detail. I'm afraid I don't understand it. Are you saying that this is the way to prove the specific orbit that this TM follows from a blank tape eventually halts (in my analysis, I required taking the first number [5] modulo 2^32). Or are you making a broader statement on how any orbit can be computed quickly or that the Collatz problem is provable for this set of rules?

[Pascal Michel]

 (1) What I said is specific to the present case.

The first time I studied the computation of Pavel's machine on a blank tape using Shawn's rules R0, ..., R3, I did like Shawn, with a high modulus 2^n and a division by 4 at each stage.

But it is possible to do better:  beginning with 2^15 and making a division by 2 at each stage.

The best way to show it is to show the beginning of the computation.

Let us start with A_0 = 88574 = (4*22143) + 2 = 4 k_0 + r_0.

By rule R2, we get 

 A_1 = ((3^22146) - 11)/2 = 4 k_1 + r_1

We have   3^22146 = 521 (mod 2^15)

so   A_1 = ((3^22146) - 11)/2 = 255 (mod 2^14)  (14 = 15 - 1, because of division by 2 in A_1)

so   4 k_1 + r_1 = 255 (mod 2^14),

so  r_1 = 3  and  k_1 = (255 - 3)/4 = 63 (mod 2^12) (12 =14 - 2, because division by 4 in k_1).

By rule R3, we get

  A_2 = ((3^(k_1 + 3)) +1)/2

k_1 is known modulo 2^12, and the order of 3 modulo 2^n is 2^(n - 2) if n > 2, so 3^(k_1 + 3) is known modulo 2^14 (I guess this is the point where I differ from Shawn)

so  3^(k_1 + 3) = 3^66 = 9481 (mod 2^14)

so  A_2 = (9481 + 1)/2 = 4741 (mod 2^13)

We see that, at each stage, the modulus is divided by 2, not by 4.

Finally, we get

  A_12 = (3^(k_11 + 3) + 1)/2 = 1 (mod 2^3)

  A_12 = 4 k_12 + r_12 with  k_12 = 0 (mod 2^1),

By rule R1,

  A_13 = (3^(k_12 + 3) - 11)/2 = 0 (mod 2^2)
so A_13 is divisible by 4 and we apply rule R0.

(2) We have k_(i + 1) > 3^(k_i) and sigma(M) > 3^(k_13), so sigma(M) > 3^ ...^3^(k_1), with 13 3s in the tower..

We have k_1 = (3^22146 - 17)/8, and it is easy to prove that k_1 > 3^22144,

so sigma(M) > 3^ ... ^3^22144, with 14 3s in the tower.

Pascal

[Shawn Ligocki]

On Thu, Jun 9, 2022 at 3:57 AM Pascal Michel <pascalm...@gmail.com> wrote:

 k_1 is known modulo 2^12, and the order of 3 modulo 2^n is 2^(n - 2) if n > 2, so 3^(k_1 + 3) is known modulo 2^14 (I guess this is the point where I differ from Shawn)

Agreed, this is where we differ. I went through the math more carefully this time, but I still don't see how you ended up with knowing "3^(k_1 + 3) modulo 2^14". Let me explain my reasoning and maybe you can show me where I can improve :)

Based upon Euler's Theorem we know that 3^phi(2^n) = 1 (mod 2^n) and by Euler's totient product formula we know that phi(2^n) = 2^(n-1) * (2 - 1) = 2^(n-1). So 3^(2^(n-1)) = 1 (mod 2^n) for any n.

As you mentioned above, k_1 = 63 (mod 2^12). In other words: k_1 = 63 + m 2^12. Therefore, 3^(k_1 + 3) = 3^(66 + m 2^12) = (3^66) * (3^(2^12))^m = 3^66 * 1^m (mod 2^13) = 3^66 (mod 2^13) [Because 3^2^12 = 1 (mod 2^13)].

So I am only getting 13 bits guaranteed known for 3^(k_1 + 3). How'd you get that extra bit?

[Pascal Michel]

Euler theorem says that  a^(phi(b)) = 1 (mod b), but that means that phi(b) is a multiple of the order of a modulo b. The order can be smaller than phi(b).

This is the case here: The order of 3 modulo 2^n is 2^(n - 2), smaller than phi(2^n) = 2^(n - 1);

In fact, we have  3^(2^(n - 3)) = 2^(n - 1) + 1 (mod 2^n) if n > 3 (the case n = 3 must be treated independently) and 3^(2^(n - 2)) = 1 (mod 2^n), so the order of 3 modulo 2^n is smaller than phi(2^n) = 2^(n - 1).

Pascal

[Shawn Ligocki]

Aha, today I learned about the Carmichael function and specifically that λ(2^n) = 1/2 φ(2^n) = 2^(n-2) for (n >= 3)! Thanks for the explanation, Pascal!

This sort of analysis is definitely going to be tricky to automate into software simulations, so we have entered an exciting time for BB searching :)

--

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/60b0e35c-7fc0-4cb0-98b9-2ff39e2eeb1en%40googlegroups.com.

[Shawn Ligocki]

On Fri, May 27, 2022 at 3:26 PM <uni...@fu-solution.com> wrote:

this one looks like a winner :D. i would like to hear the story behind
it.

OK, it is time to tell the story of how I found this original 4^4^4^4^4^7 machine:

It all started, Pavel, when you announced your 10^646M machine. I have been experimenting with looking at adjacent machines and recently I started thinking about a different (simpler) type of adjacency: just permuting the start state. This change has the advantage that it will always produce a new machine which follows the same rules as the original machine (as long as its initialization get's into one of the rule configurations). I call these "permutations" of the original TM.

So I looked at all the permutations of Pavel's 10^646M machine (the first line is Pavel's machine, the rest are the results of swapping state A <-> each other state):

1. 1RB 1RZ  0LC 0LD  1LD 1LC  1RE 1LB  1RF 1RD  0LD 0RA
2. 0LC 0LD  1RA 1RZ  1LD 1LC  1RE 1LA  1RF 1RD  0LD 0RB
3. 1LD 1LA  0LA 0LD  1RB 1RZ  1RE 1LB  1RF 1RD  0LD 0RC
4. 1RE 1LB  0LC 0LA  1LA 1LC  1RB 1RZ  1RF 1RA  0LA 0RD
5. 1RF 1RD  0LC 0LD  1LD 1LC  1RA 1LB  1RB 1RZ  0LD 0RE
6. 0LD 0RF  0LC 0LD  1LD 1LC  1RE 1LB  1RA 1RD  1RB 1RZ

Or (converted into TNF):

1. 1RB 1RZ  0LC 0LD  1LD 1LC  1RE 1LB  1RF 1RD  0LD 0RA
2. 0RB 0RC  1RC 1RB  1LD 1RA  1LE 1LC  0RC 0LF  1LA 1RZ
3. 1RB 1RA  1LC 1RE  1LD 1LB  0RB 0LF  0RA 0RB  1LE 1RZ
4. 1RB 1LD  1RC 1RA  0LA 0RE  0LF 0LA  1RD 1RZ  1LA 1LF
5. 1RB 1RC  0LC 0RF  1RA 1LD  0LE 0LC  1LC 1LE  1RD 1RZ
6. 0RB 0LE  1LC 1RD  1LA 1LB  0RF 0RB  1LD 1RZ  1RB 1RF

and I discovered that #3 was in my list of top halting TMs (#249 on my list, running for 10^76.5 steps). So I was kicking myself, I could have found this machine if only I'd looked at the permutations of my top halting machines!

Thus I was on a mission, I started experimenting with looking at all the permutations of my top halting machines. First I looked at the top 100 ... no luck, then the top 1000 (found Pavel's machine, but that's it) ... finally I looked at all the permutations of the top 10k machines ... this took a little while and left me with way too many machines to analyze by hand.

So, I added some logging to my code to record which machines I was able to prove a recursive rule (but not prove halting/infiniteness), this left only 6 machines:

1. 1RC 0RB  1RA 1RF  1LD 0RA  0LE 0LC  0LB 1LE  1RB 1RZ
2. 1RF 1RZ  1RC 0RF  1LD 0RB  0LE 0LC  0LF 1LE  1RB 1RA
3. 1LE 1RZ  1LC 1RE  1LD 1LB  0RB 0LA  0RF 0RB  1RB 1RF
4. 1LE 0RA  0RC 0RB  0RD 0RE  1LD 0LA  1RB 1RF  1RZ 1RC
5. 1LE 0LD  0RC 0RE  0RD 1RC  1LA 1LF  1RB 0LA  1LD 1RZ
6. 1LD 1RZ  0RC 0RF  0RD 1RC  1LE 1LA  1LF 0LD  1RB 0LE

#1 & #2 are permutations of each other and can be proven to never halt. #5 & #6 are also permutations of each other that can also be proven to never halt. #3 is Pavel's machine. And #4 ... was my 4^4^4^4^4^7 (short lived!) champion!

I learned the basic rules and behavior from my software, but had to prove the results of repeated application by hand.

... And then 3 days later, Pavel had rewritten his code to automatically simulate these sorts of machines and beaten me again :P

Previously I had tried to look at all 6x2 TMs for which I was able to prove a recursive rule (but not prove halting/infiniteness), but there were >10k such machines and every single one I analyzed by hand (10-20) all had infinite behavior that was just slightly too complicated for my software to notice. So finding some way to reduce this list down to a handful was necessary for manual analysis to have any success. Permutations of previous best results was that heuristic. I think the value of starting from machines which halt is that you know that they follow rules which do (sometimes) halt unlike the vast majority of the >10k machines which have rules, but no way to actually halt from those rules.

So, always look at the permutations of your winning machines! Who knows, you might find an even bigger winner!

-Shawn

PS: Which TM was this 4^4^4^4^4^7 TM a permutation of? the #1065-th best halting TM in my list which runs for 10^14.3 steps before halting:

• 1RB 1RF  0RC 0RB  0RD 0RA  1LD 0LE  1LA 0RE  1RZ 1RC

[Pascal Michel]

i give here more analysis about the machine M that Pavel Kropitz found on May 30,2022, with sigma(M) > 10^^15.

(1) I use Shawn's configurations C(n,m) = ...01 0^n 11 0^(3m + 2) (C0) 0...

For all k >= 0,

(a) ...0(A0)0... --(45)--> C(5,1)

(b) C(4k,1) --( (3*9^(k + 3) - 80*3^(k + 3) + 712k + 261)/32 )--> 1(H0)1^(n - 1), with n = (3^(k + 3) - 11)/2

(c) C(4k + 1,1) --( (3*9^(k + 3) - 64*3^(k + 3) + 712k +981)/32 ) --> C( (3^(k + 3) - 11)/2,1)

(d) C(4k + 2,1) --( (3*9^(k + 3) - 64*3^(k + 3) + 712k + 1045)/32 )--> C( (3^(k + 3) - 11)/2,1)

(e) C(4k + 3,1) --( (3*9^(k + 3) - 64*3^(k + 3)+712k + 1749)/32 )--> C( (3^(k + 3) + 1)/2,1)

(2) If the final configuration is ...01(H0)1^(n - 1) 0..., with n = (3^(k + 3) -11)/2, then the leading term of the time in the last transition is 3*9^(k + 3)/32, so

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

(3) We have sigma(M) > 3^ ...^3^22144.1 (with 14 3s) > 10^ ...^10^10565 (with 14 10s) > 10^^15

Pascal

[Shawn Ligocki]

I have written up a blog post walking through the steps of how to evaluate the Collatz-like rules for Pavel's champion 10↑↑15 machine (which I am naming "t15" for "tower 15"). It is especially aimed at anyone who is wondering how it is we have been able to simulate these latest two machines but has not been able to interpret my, Pascal's and Pavel's cryptic emails. Please let me know if any of you have any questions about it (or notice any mistakes!):

https://www.sligocki.com/2022/06/21/bb-6-2-t15.html

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/6ec0d8d6-4ada-407d-ae73-b4ededb63f31n%40googlegroups.com.

[Tristan Stérin]

Very nice post, thank you!

[Sophie]

The web page seems to crash when I use the Opera browser.