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

[Pascal Michel]

(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

https://www.sligocki.com/2022/04/03/mother-of-giants.html

using configurations G(n,m) = ...0(D0)0^n1^m0...

I give here more details about this machine.

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]

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.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CAC8KPfFpA9y-iw0f%2BaDpp-_brnmbubmc_eEmmhKVJrtvTgdo1A%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Nicholas Drozd]

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]

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]

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]

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]

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

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/f1e54e36-5dbd-482d-a477-b9acc81913e5n%40googlegroups.com.

[Pascal Michel]

Thank you.

The digits you have given don't allow to improve the lower bound.

[Pascal Michel]

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.

[Shawn Ligocki]

Thanks for this additional analysis, Pascal! It's great to get these sort of rigorous bounds to go along with the "probvious" intuition!

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/6c5f5e1a-ccfd-415a-8394-e5ba7f99d435n%40googlegroups.com.