1534 views

Skip to first unread message

May 27, 2022, 12:14:01 PMMay 27

to Busy Beaver Discuss

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

May 27, 2022, 2:43:27 PMMay 27

to busy-beav...@googlegroups.com, Shawn 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, 🤪...

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.)

because there's nothing the world loves more

than the taste of really sweet dreams.

(Despair, Inc.)

May 27, 2022, 3:26:59 PMMay 27

to busy-beav...@googlegroups.com

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

it.

it.

May 27, 2022, 4:08:18 PMMay 27

to Busy Beaver Discuss

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.

May 30, 2022, 9:46:24 AMMay 30

to Busy Beaver Discuss

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

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.

May 30, 2022, 3:22:40 PMMay 30

to busy-beav...@googlegroups.com, Wietze Koops

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)

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.

May 30, 2022, 4:08:49 PMMay 30

to busy-beav...@googlegroups.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 &
> 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

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)

May 31, 2022, 1:23:38 AMMay 31

to Busy Beaver Discuss

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:

- Rule R0: C(4k , 1) -> Halt((3^k+3 - 11) / 2)
- Rule R1: C(4k+1, 1) -> C((3^k+3 - 11) / 2, 1)
- Rule R2: C(4k+2, 1) -> C((3^k+3 - 11) / 2, 1)
- 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.

May 31, 2022, 1:40:51 AMMay 31

to Busy Beaver Discuss

Oops, forgot to mention:

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

May 31, 2022, 10:36:07 AMMay 31

to Busy Beaver Discuss

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.

Jun 2, 2022, 3:31:56 AMJun 2

to Busy Beaver Discuss

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^ ...^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.

Jun 3, 2022, 3:26:52 AMJun 3

to Busy Beaver Discuss

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

Jun 3, 2022, 7:24:22 AMJun 3

to busy-beav...@googlegroups.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
> 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.

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)

Jun 5, 2022, 2:52:06 AMJun 5

to Busy Beaver Discuss

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.

Jun 7, 2022, 3:38:44 AMJun 7

to Busy Beaver Discuss

(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.

Jun 7, 2022, 11:40:23 AMJun 7

to Busy Beaver Discuss

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?

Jun 9, 2022, 3:57:53 AMJun 9

to Busy Beaver Discuss

(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.

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.

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

Jun 9, 2022, 1:30:49 PMJun 9

to Busy Beaver Discuss

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?

Jun 10, 2022, 3:33:47 AMJun 10

to Busy Beaver Discuss

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

Jun 10, 2022, 11:21:05 AMJun 10

to Busy Beaver Discuss

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.

Jun 13, 2022, 11:23:02 PMJun 13

to Busy Beaver Discuss

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):

- 1RB 1RZ 0LC 0LD 1LD 1LC 1RE 1LB 1RF 1RD 0LD 0RA
- 0LC 0LD 1RA 1RZ 1LD 1LC 1RE 1LA 1RF 1RD 0LD 0RB
- 1LD 1LA 0LA 0LD 1RB 1RZ 1RE 1LB 1RF 1RD 0LD 0RC
- 1RE 1LB 0LC 0LA 1LA 1LC 1RB 1RZ 1RF 1RA 0LA 0RD
- 1RF 1RD 0LC 0LD 1LD 1LC 1RA 1LB 1RB 1RZ 0LD 0RE
- 0LD 0RF 0LC 0LD 1LD 1LC 1RE 1LB 1RA 1RD 1RB 1RZ

Or (converted into TNF):

- 1RB 1RZ 0LC 0LD 1LD 1LC 1RE 1LB 1RF 1RD 0LD 0RA
- 0RB 0RC 1RC 1RB 1LD 1RA 1LE 1LC 0RC 0LF 1LA 1RZ
- 1RB 1RA 1LC 1RE 1LD 1LB 0RB 0LF 0RA 0RB 1LE 1RZ
- 1RB 1LD 1RC 1RA 0LA 0RE 0LF 0LA 1RD 1RZ 1LA 1LF
- 1RB 1RC 0LC 0RF 1RA 1LD 0LE 0LC 1LC 1LE 1RD 1RZ
- 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:

- 1RC 0RB 1RA 1RF 1LD 0RA 0LE 0LC 0LB 1LE 1RB 1RZ
- 1RF 1RZ 1RC 0RF 1LD 0RB 0LE 0LC 0LF 1LE 1RB 1RA
- 1LE 1RZ 1LC 1RE 1LD 1LB 0RB 0LA 0RF 0RB 1RB 1RF
- 1LE 0RA 0RC 0RB 0RD 0RE 1LD 0LA 1RB 1RF 1RZ 1RC
- 1LE 0LD 0RC 0RE 0RD 1RC 1LA 1LF 1RB 0LA 1LD 1RZ
- 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

Jun 16, 2022, 3:34:09 AMJun 16

to Busy Beaver Discuss

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

PascalJun 22, 2022, 12:37:38 AMJun 22

to Busy Beaver Discuss

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!):

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

Jun 22, 2022, 9:41:21 AMJun 22

to Busy Beaver Discuss

Very nice post, thank you!

Jun 22, 2022, 7:13:29 PMJun 22

to Busy Beaver Discuss

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

Reply all

Reply to author

Forward

0 new messages