Mother of Giants

Unsolved problem:

Does the Mother of Giants quasihalt? If so, how many steps does it take to quasihalt?

This article is a stub. You can help the BusyBeaverWiki by expanding it.

The Mother of Giants is a collection of adjacent Turing machines, some of which are Cryptids in the 5-state Beeping Busy Beaver problem that probviously quasihalt. They must all be proven to halt or not if we want to solve BBB(5).

The TMs are all the "children" of 1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA where children means all the TMs created by filling in the undefined E0 transition.

Overview of the children

An overview of the 8 most interesting children.


Machine	Status
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_1RC0LA` (bbch) and `1RB1LE_0LC0LB_0LD1LC_1RD1RA_1LC0LA` (bbch)	Probviously quasihalting Cryptids
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_1LA0LA` (bbch)	Probviously quasihalting Cryptid
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_0LC0LA` (bbch)	Probviously quasihalting Cryptid
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA` (bbch) (current champion) and `1RB1LE_0LC0LB_0LD1LC_1RD1RA_0LD0LA` (bbch)	Quasihalt after $>10^{14\,006}$ steps.^[1]
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_1RD0LA` (bbch)	Quasihalts after about $10^{12\,978}$ steps.^[2]
`1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RD0LA` (bbch)	Quasihalts after about $10^{4\,079}$ steps.^[1]

1RB1LE_0LC0LB_0LD1LC_1RD1RA_1RC0LA

Probviously quasihalting Cryptid with collatz-like behaviour. Analysis by Shawn Ligocki:


Let: F(a, b, c) = 0^∞ <D 0^a 10^b 1^c 0^∞

The Mother of Giants (and all of her children) satisfies the following rules:

F(a, b + 2, c) → F(a + 7, b, c)
F(a, 1, c + 1) → F(a + 6, 0, c)

F(2k + 1, 0, c + 2) → F(1, k + 2, c + 1)

F(a, 0, 1) → F(1, 0, a + 3)
F(a, 0, 0) → Spin Out / Quasihalt

Blank tape → F(1, 0, 1) (at step 4)
(I leave proof of these rules as an exercise for the reader. They follow a similar style to those proofs in previous Collatz analysis posts.)

There’s one rule missing from this list. What happens after config F(2k, 0, c + 2)? This is the one part of the analysis where each child brings their own unique twist!
For E0 → 1RC:
F(2k, 0, c + 2) → F(1, k + 3, c + 1)

Collatz Behavior of 1RC
Let G(n, m) = F(n, 0, m) = 0^∞ <D 0^n 1^m 0^∞

First, we can combine the first two rules in order to eliminate b immediately:

F(a, 2k, c) → F(7k+a, 0, c) = G(7k+a, c)
F(a, 2k+1, c+1) → F(7k+a, 1, c+1) → F(7k+a+6, 0, c) = G(7k+a+6,c)
Going further, it helps to have a specific machine in mind: let’s explore the E0→1RC machine.

Let G(n, m) = F(n, 0, m) = 0^∞ <D 0^n 1^m 0^∞
then:

G(4k, m+2) → F(1, 2k+3, m+1) → G(7k+14, m)
G(4k+1, m+2) → F(1, 2k+2, m+1) → G(7k+8, m+1)
G(4k+2, m+2) → F(1, 2k+4, m+1) → G(7k+15, m+1)
G(4k+3, m+2) → F(1, 2k+3, m+1) → G(7k+14, m)

G(n, 1) → G(1, n + 3)
G(n, 0) → Spin Out / Quasihalt

The current maximum known reset config for this TM is $G(1,>3\times 10^{286\,575})$ .

1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA and 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0LD0LA

Both quasihalt after $>10^{14\,006}$ steps, with 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch) taking more steps to quasihalt. Analysis by Shawn Ligocki:

let
  G(n, m) = 0^inf <D 0^n 1^m 0^inf
then:
  G(4k  , m+2) -> G(7k+ 7, m)
  G(4k+1, m+2) -> G(7k+ 8, m+1)
  G(4k+2, m+2) -> G(7k+ 8, m+1)
  G(4k+3, m+2) -> G(7k+14, m)
  G(n, 1) -> G(1, n+3)
  G(n, 0) -> Spin Out
If you compare this to my Collatz-like analysis of the 10^4079 machine (emailed on Mar 16), you'll see that it is extremely similar! The only difference is two of the constants on the right have changed. And likewise the 10^325 machine also had a similar Collatz-like analysis. So it appears that the 5x2 TM space has been able to simulate many parameterizations of these 2-stage style Collatz-like functions and we are noticing the especially "lucky" ones which run for quite a long time before quasihalting (but not toooo "lucky" or else my simulator will not run long enough to catch them).

The orbit for this TM starting on a blank tape is:

  0 : G(1, 1)
  1 : G(1, 4)
    2 : G(8, 3)
    3: G(21, 1)
  4 : G(1, 24)
    5 : G(8, 23)
    6 : G(21, 21)
    7 : G(43, 20)
    8 : G(84, 18)
    9 : G(154, 16)
    10 : G(274, 15)
    11 : G(484, 14)
    12 : G(854, 12)
    13 : G(1499, 11)
    14 : G(2632, 9)
    15 : G(4613, 7)
    16 : G(8079, 6)
    17 : G(14147, 4)
    18 : G(24766, 2)
    19 : G(43345, 1)
  20 : G(1, 43348)
    21 : G(8, 43347)
    22 : G(21, 43345)
    ...

    28_832 : G(2533...2210, 0)

    Spin out

So, it grew m up to >43k before spinning out (vs. 12k in the 10^4079 case).

1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RD0LA

Quasihalts after about $10^{4\,079}$ steps. Analysis by Shawn Ligocki:

let
  G(n, m) = 0^inf <E 0^n 1^m 0^inf
then
  G(4k+1, m+2) -> G(7k+ 8, m+1)
  G(4k+2, m+2) -> G(7k+ 6, m+1)
  G(4k+3, m+2) -> G(7k+14, m)
  G(4k+4, m+2) -> G(7k+12, m)
  G(n, 1) -> G(1, n+3)
  G(n, 0) -> Spin Out
and for completeness (although we can never reach G(0, m) by applying these rules):
  G(0, m+2) -> G(7, m)
and finally, at step 4 we are in G(1, 1).

As before, iterating these relations leads to a sort of "2-stage" Collatz-like behavior:
  G(1, 1)
  G(1, 4)
    G(8, 3)
    G(19, 1)
  G(1, 22)
    G(8, 21)
    G(19, 19)
    G(42, 17)
    G(76, 16)
    G(138, 14)
    G(244, 13)
    G(432, 11)
    G(761, 9)
    G(1338, 8)
    G(2344, 7)
    G(4107, 5)
    G(7196, 3)
    G(12598, 1)
  G(1, 12601)
    G(8, 12600)
    G(19, 12598)
    ...
G(1876213840710521598391379605525487806521622108810778432527722867392307436766159159315654305525834552560172561652032118063458627370309987185176524224005388698700446967268349729419384342385261686600728253800107702390205303703109911013679543376784994065131479319486732208008605302317371513424001996538578227420511014587912085639154043098929108973505716971259211164084851171147584492195641828442403195419357046301200977722765015982127629619366127227507539382553155352425623517192820793588314301840633848042122283284527197514334793445174332133304252240350530614310123013246222482691057522680607329801073658994807307108563977792602674937915145127717601763644562450026084468482011253492787037376937107425102889344711991496275353115166560777221320784075353693443765935139868061950972649919070516499077698769361018135243624369764825602272332642411663431603264357025025605181511270774475664657506683051463739351416893336641567178700404415824985611548629898352736718482963400988142981278524634899806152389037871669098549259903261356156435822856442997107359268004720245053216395652317114834047445010107196444627059271727548915696497640596592913994488623239627564677236759609661035594688933526335837056500047460869283130575904150442715133699885285716657627307991036082003072952095275483832305837708309180971389464320818551264951669392266140549796563778468321806984538951296296552524443477377012382914243026356951988052699080778947387243967930857325467739175240274180541636551276654811833607927610176824006302410755537315645723335878886137585589884378754363497710819886157044977428594424751379562193743624891055837449756993817095474523342307530343858042369299814007843193782820421402610428397007107529266963233646286254595510683332294534735691214261351756352969840115522216379692717569241523917906031879093475856928361266209321993314289669996574460021380115709710519270157850694498748462253621222466800698577194648206832226152375452456786050873778773714111576650409478390819793529657854689649591879416169292957147115001498762307255727596635383777744252057, 0)
  Spin Out

References

[:0-1] 1.0 ^1.1 https://www.sligocki.com/2022/04/03/mother-of-giants.html

[2] ttps://groups.google.com/g/busy-beaver-discuss/c/zUiw3G7hR8E

[1]

[2]