# Analysis of the 1RC-child of the Mother of Giants

84 views

### Pascal Michel

Apr 11, 2022, 3:49:27 AM4/11/22
to Busy Beaver Discuss
(1) In a mail on April 4, 2022, Shawn Ligocki gave the following Turing machine m:
1RB 1LE 0LC 0LB 0LD 1LC 1RD 1RA 1RC 0LA
He gave an analysis of this machine on his web page
using configurations G(n,m) = ...0(D0)0^n1^m0...
We have, for n, k, m >=0
(a) ...0(A0)0... --(4)--> G(1,1)
(b) G(n,1) --(2n + 8)--> G(1,n + 3)
(c) G(4k,m + 2) --(7k^2 + 40k + 56)--> G(7k + 14,m)
(d) G(4k + 1,m + 2) --(7k^2 + 26k + 22)--> G(7k + 8,m + 1)
(e) G(4k + 2,m +2 ) --(7k^2 + 40k + 60)--> G(7k + 15,m +1 )
(f) G(4k + 3,m + 2) --(7k^2 + 40k + 51)--> G(7k + 14,m)
(g) G(n,0) = ...0(D0)... quasi halts

(2) It is easy to prove that, if G(x,m) --(t)--> G(y,m') is a transition (c), (d), (e) or (f), then
y/x > 7/4 and t > (y^2)/7.

(3) If G(1,a) yields G(b,c) with c = 0 or 1, in p transitions of configurations G(n,m) with decreasing m, then p > a/2.
By (2), we have b > (7/4)^p, and the last transition takes a time t > (b^2)/7.
So we have t > ((7/4)^a)/7.

(4) Shawn Ligocki wrote that machine M reaches a configuration G(1,a) with a > 3 x 10^286575.
So the total time T = BBB(M) from the blank tape to quasihalting for machine M is
T > t > ((7/4)^(3 x 10^286575))/7 > 10^(10^286574).
Note that this lower bound for machine M is not proven to be optimal, because we do not know the fate of configuration G(1,a).

(5) Since BBB(M) > 10^(10^286574) we have BBB(5,2) > 10^(10^286574)

Pascal

### Shawn Ligocki

Apr 11, 2022, 9:49:15 AM4/11/22
to Pascal Michel, Busy Beaver Discuss
Thanks Pascal for the detailed analysis and lower bound for quasihalting! I have one question about step (4): Can we prove that this machine is guaranteed to eventually quasihalt? I feel that it "probviously" does (using the terminology of Conway) because the idea that it could reach m=1 every time for eternity seems far-fetched, but I feel at a loss to give any hard justification for this hunch. What do you think?

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

### Nicholas Drozd

Apr 11, 2022, 12:06:53 PM4/11/22
to Shawn Ligocki, Pascal Michel, Busy Beaver Discuss
Let me see if I have this right. The claim is that the machine in question implements the following iterated Collatz-like function:

G(n, 0) = 0
G(n, 1) = G(1, n + 3)

G(4k + 0, m) = G(7k + 14, m - 2)
G(4k + 1, m) = G(7k +  8, m - 1)
G(4k + 2, m) = G(7k + 15, m - 1)
G(4k + 2, m) = G(7k + 14, m - 2)

Starting from the blank tape executes the function call G(1, 1).

Assuming that is the case, the next step is to calculate how many machine steps it takes to run this all the way through. This will take a very very long time, so long that it's possible we can't actually witness a simulator running it to the end. And therefore we can only estimate the number of steps required.

As far as proving that it does stop (that is, that m eventually reached 0), it's easy to implement G in Python. It terminates after 29,941 iterations. So if the TM really does implement G, then I think we can safely say that it will eventually terminate.

### Shawn Ligocki

Apr 11, 2022, 12:31:53 PM4/11/22
to Nicholas Drozd, Pascal Michel, Busy Beaver Discuss
On Mon, Apr 11, 2022 at 12:06 PM Nicholas Drozd <nichol...@gmail.com> wrote:
Let me see if I have this right. The claim is that the machine in question implements the following iterated Collatz-like function:

G(n, 0) = 0
G(n, 1) = G(1, n + 3)

G(4k + 0, m) = G(7k + 14, m - 2)
G(4k + 1, m) = G(7k +  8, m - 1)
G(4k + 2, m) = G(7k + 15, m - 1)
G(4k + 2, m) = G(7k + 14, m - 2)
Typo: This should be 4k+3, m (and in all these cases we should only apply these if m >= 2 (perhaps implied by the order you listed these :) ) Given those two caveats, I agree with this function.

Starting from the blank tape executes the function call G(1, 1).

Assuming that is the case, the next step is to calculate how many machine steps it takes to run this all the way through. This will take a very very long time, so long that it's possible we can't actually witness a simulator running it to the end. And therefore we can only estimate the number of steps required.

As far as proving that it does stop (that is, that m eventually reached 0), it's easy to implement G in Python. It terminates after 29,941 iterations. So if the TM really does implement G, then I think we can safely say that it will eventually terminate.
Nick, can you check your program? I wrote the same program and I see G iterating millions of iterations with no stop in sight. Specifically, here is it's evaluation at several iteration counts:
• 0 : G(1, 1)
• 1 : G(1, 4)
• 4 : G(1, 31)
• 26 : G(1, 1_768_519)
•   ...  100_000 : G(10^24_298.6, 1_618_623)   [4s]
•   ...  200_000 : G(10^48_602.4, 1_468_482)   [17s]
•   ...  300_000 : G(10^72_906.2, 1_318_604)   [42s]
•   ...  400_000 : G(10^97_210.0, 1_168_543)   [78s]
•   ...  500_000 : G(10^121_513.8, 1_018_777)   [125s]
•   ...  600_000 : G(10^145_817.7, 868_766)   [180s]
•   ...  700_000 : G(10^170_121.5, 718_734)   [259s]
•   ...  800_000 : G(10^194_425.3, 568_688)   [335s]
•   ...  900_000 : G(10^218_729.1, 418_898)   [417s]
•   ...  1_000_000 : G(10^243_032.9, 268_857)   [508s]
•   ...  1_100_000 : G(10^267_336.7, 119_123)   [615s]
• 1_179_161 : G(1, 10^286_575.6)
At this point (as Pascal has noted) we are guaranteed that it will run for at least 10^286_575 more iterations because each iteration can reduce m by at most 2.

If we could find when iteration of G eventually terminates, then we would have proven when the TM itself quasihalts since the TM simulates this G.

### Shawn Ligocki

Apr 11, 2022, 1:01:32 PM4/11/22
to Nicholas Drozd, Pascal Michel, Busy Beaver Discuss
As a quick sanity check, I ran our standard TM simulator (no Collatz function baked in) and it agrees that the TM reaches G(1, 1_768_519):

\$ Code/Quick_Sim.py Machines/beep/5x2-Giants -vbn2 | egrep "00\^inf (<D 01\^1|<C) 11\^\d+( 10\^1)? 00\^inf"

5  00^inf <C 11^2 00^inf (4, 13)

57  00^inf <C 11^15 10^1 00^inf (30, 263)

649  00^inf <D 01^1 11^884259 00^inf (2, 663445078995)

Read the bottom line as: At step 663_445_078_995 (simulator step 649) the TM is in configuration 00^inf <D 01^1 11^884_259 00^inf = 0^inf 0 1^1_768_519 0^inf = G(1, 1_768_519).

### Nicholas Drozd

Apr 11, 2022, 2:54:21 PM4/11/22
to Shawn Ligocki, Pascal Michel, Busy Beaver Discuss
Right on both counts, Shawn. Typo in the definition and wrong number in my Python. With that number corrected, I get the same reset counts as you.

So yes, we will need some kind of proof that this terminates!

### Pascal Michel

Apr 13, 2022, 2:37:25 AM4/13/22
to Busy Beaver Discuss
(1) I see no way to know the result of 10^286575.6 transitions, that is iterations of a Collatz-like function.
And I see no way to prove that the machine eventually quasihalts.

(2) Shawn, you wrote "10^286575.6". Do you know some digits after the 6?
This could lead to improve the lower bound BBB(M) > 10^(10^286574).

### Shawn Ligocki

Apr 13, 2022, 9:20:41 PM4/13/22
to Pascal Michel, Busy Beaver Discuss
Yes, Pascal, I can share the exact number ... but it is quite large, so I've attached a file with it. I'll say that it starts and ends with:

371803237711966978001607279479823194967...410220642038156074733

which I'm guessing is enough to refine these bounds.
--
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.
collatz_1RC.txt

### Pascal Michel

Apr 15, 2022, 3:12:25 AM4/15/22
to Busy Beaver Discuss
Thank you.
The digits you have given don't allow to improve the lower bound.

### Pascal Michel

May 3, 2022, 3:33:04 AM5/3/22
to Busy Beaver Discuss
I give here more analysis about the 1RC-child of the Mother of Giants.

Consider a sequence of transitions from G(n,a) to G(b,c), with  c = 0 or 1, via configurations G(q,m) with decreasing m.
It is easy to prove that the values of m in this sequence depend only of n modulo 4^(a -1).
When n takes values from 0 to 4^(a - 1) - 1,the number of numbers m that occurs in the sequences G(q,m) varies as follows.

If P(m) is the proportion of sequences in which m occurs, then we have
P(a) = 1 (a occurs in all sequences),
P(a - 1) = 1/2 (a - 1 occurs in half of the sequences),
P(m) = (P(m + 1) + P(m + 2))/2 if 0 < m < a - 1,
P(0) = P(2)/2 = 1 - P(1).

It is easy to prove that the solution to these conditions is
P(m) = (2/3) + ((-1)^(a - m)/(3x2^(a - m))) if m > 0,
P(0) = (1/3) + ((-1)^a/(3x2^(a - 1))).
In particular, P(1) = (2/3) + ((-1)^(a - 1)/(3x2^(a - 1))).

it is easy to verify these values for small values of a.

Note that, when a is a big number, we get that
P(1) is approximately 2/3, and
P(0) is approximately 1/3.