Thread for CA-related fast-growing functions

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
Post Reply
User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Thread for CA-related fast-growing functions

Post by Moosey » April 2nd, 2021, 10:33 am

To start off, from the discord, by myself: let g(n) for natural n be the supremum of the population of all evolutions of a single state-1 cell throughout all range-1 moore CA with n+2 states with population that is bounded beneath a finite number. (i.e. basically the range 1 moore CA equivalent of the busy beaver function)

g(0) is at least 33 (by this rule https://catagolue.hatsya.com/census/b1e ... eknqy5ej6e):

Code: Select all

x = 1, y = 1, rule = B1e2-an3ejkry4cjrw5ceny6c7c/S2ik3-aejr4eknqy5ej6e
o!
EDIT: 40

Code: Select all

x = 1, y = 1, rule = B1e2-an3ejkry4ejrw5ceny6c7c8/S2ik3-aejr4ceknqy5ej6e
o!
EDIT: 65

Code: Select all

x = 1, y = 1, rule = B1e2-an3ejkry4ejrw5ceny6c7c8/S2ik3-aejr4ceknqty5ej6e7e
o!
But is likely larger thanks to MAP rules-- can anyone try to construct a map rule giving a better lower bound? (ideally >100)

g(1) is at least 811941681; the rule in question is one where:
a single state-1 cell causes b1e of state-2 cells and becomes a state-2 cell itself, and state 2 follows this rule.

Challenge: construct a stronger lower bound on g(1).

g(2) is something that I'm not going to even pretend to approach-- if you want I welcome you to try to construct a rule which provides a lower bound
not active here but active on discord

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Thread for CA-related fast-growing functions

Post by toroidalet » April 2nd, 2021, 4:44 pm

G(0)≥3,156:

Code: Select all

x = 1, y = 1, rule = B1e2i3k4acjw5ny7e8/S12-e3jkry4artwz5ry6c
o!
A larger one could be constructed by focusing on denser rules.

This anisotropic 3-state rule goes up to 2^(7 million or so):

Code: Select all

@RULE 1C3SShip (incomplete)
@TABLE
n_states:3
neighborhood:Moore
symmetries:none
#delay
0,0,0,0,0,2,1,2,0,2
2,0,0,0,0,0,1,0,0,1
1,0,0,0,0,0,1,0,0,0
2,0,0,0,0,0,2,0,0,1
1,0,0,0,0,0,2,0,0,0
#leftward expansion
0,0,0,1,0,0,0,0,0,2
0,0,0,0,0,1,2,0,0,2
0,0,0,2,1,2,0,0,0,1
2,0,0,0,2,1,2,0,0,0
2,1,0,1,2,0,0,0,0,1
1,0,0,0,1,1,0,0,0,0
1,1,0,1,2,0,0,0,0,2
0,0,1,1,0,0,0,0,0,2
0,0,0,1,1,0,0,0,0,1
2,1,0,2,0,0,0,0,0,1
2,0,0,0,0,1,2,0,0,0
1,1,0,2,0,0,0,0,0,2
1,0,0,0,2,1,0,0,0,0
#downward expansion
0,1,0,0,0,0,0,0,0,2
0,0,0,0,0,0,2,1,0,2
0,2,0,0,0,0,0,2,1,1
2,0,0,0,0,0,2,1,2,0
2,1,2,1,0,0,0,0,2,1
2,0,0,0,0,1,2,1,0,0
1,0,0,0,0,0,0,1,1,0
2,1,0,1,0,0,0,0,1,1
1,1,0,1,0,0,0,0,2,2
0,1,1,0,0,0,0,0,0,2
0,1,0,0,0,0,0,0,1,1
2,2,0,1,0,0,0,0,0,1
1,2,0,1,0,0,0,0,0,2
1,0,0,0,0,0,0,1,2,0
0,0,0,0,0,2,1,0,0,2
2,0,0,0,0,2,1,0,0,0
#downward stop
0,1,0,0,0,0,2,1,0,1
1,0,0,0,0,0,2,1,0,2
2,0,0,0,0,0,2,1,0,0
0,2,0,0,0,1,1,2,2,2
2,1,0,2,0,2,0,0,1,1
2,0,0,0,0,0,2,2,1,0
0,2,0,0,0,1,2,2,2,2
2,0,0,0,0,1,1,2,1,0
2,1,0,2,1,1,0,0,0,1
1,2,2,1,0,0,0,0,0,2
1,2,0,0,0,0,0,1,2,2
2,1,0,2,1,2,0,0,0,1
2,0,0,0,0,1,2,2,1,0
1,2,0,0,0,0,0,2,2,0
2,2,1,1,0,0,0,0,0,0
1,1,0,0,0,0,0,2,2,0
0,0,0,2,2,1,2,1,1,1
1,0,0,0,2,1,2,1,1,2
2,1,2,1,0,0,0,0,0,0
1,2,0,2,0,0,0,2,1,0
0,0,0,0,0,2,1,1,0,2
1,1,0,2,1,2,0,0,1,0
2,0,0,0,2,1,2,1,1,0
2,0,1,0,0,0,0,1,2,0
#downward counting
0,1,0,0,0,0,1,1,0,2
1,1,1,0,0,2,2,0,0,2
1,1,0,0,0,0,2,1,1,0
0,0,2,0,0,0,1,2,2,1
0,0,0,0,0,1,1,1,1,1
0,0,2,0,0,0,2,1,1,1
0,2,0,0,0,1,2,2,1,1
0,0,2,0,0,0,2,2,2,1
1,1,0,1,0,1,0,0,1,2
1,1,0,0,0,0,2,2,2,0
1,1,0,0,0,0,1,2,2,0
1,0,0,0,0,0,2,2,1,0
1,0,0,0,0,0,1,2,1,0
1,1,0,0,0,0,1,1,1,0
0,0,2,0,0,0,1,1,1,1
0,0,0,0,0,0,2,0,2,1
1,0,0,0,0,2,0,0,1,0
2,0,0,0,0,0,1,1,0,0
1,1,2,0,0,1,0,0,1,2
0,2,0,0,0,0,1,2,1,2
2,0,0,0,0,0,1,2,1,0
2,1,0,2,0,1,0,0,2,1
1,2,2,0,0,1,0,0,0,2
1,1,2,0,0,2,0,0,1,2
0,2,0,0,0,0,2,2,1,2
0,2,0,0,0,0,1,2,2,2
2,1,0,2,0,1,0,0,0,1
1,2,2,0,0,2,0,0,0,2
0,2,0,0,0,0,2,2,2,2
2,1,0,2,0,2,0,0,0,1
0,2,0,0,0,0,0,2,2,2
2,0,0,0,0,0,0,1,1,0
2,0,1,2,0,0,0,0,0,0
2,1,0,0,0,0,0,2,0,1
2,1,1,1,0,0,0,0,2,0
1,1,0,0,0,0,0,2,1,0
1,0,0,0,0,0,0,2,0,2
0,0,2,0,0,0,1,1,2,1
#upward signal
0,0,1,1,2,2,0,0,0,2
0,0,1,1,1,2,0,0,0,2
0,0,2,1,1,2,0,0,0,2
0,0,2,2,1,2,0,0,0,2
0,0,2,2,2,2,0,0,0,2
0,0,2,1,2,2,0,0,0,2
0,0,1,2,1,2,0,0,0,2
0,0,1,2,2,2,0,0,0,2
2,0,1,1,1,0,0,0,0,0
2,0,1,1,2,0,0,0,0,0
2,0,1,2,1,0,0,0,0,0
2,0,1,2,2,0,0,0,0,0
2,0,2,1,1,0,0,0,0,0
2,2,2,1,2,0,0,0,0,0
2,0,2,2,1,0,0,0,0,0
2,0,2,2,2,0,0,0,0,0
2,1,0,0,0,1,0,2,0,1
2,2,0,0,0,1,0,2,0,1
0,1,1,2,1,2,0,0,2,1
0,1,1,1,2,2,0,0,1,1
1,1,1,2,2,0,0,0,2,2
0,2,1,2,0,0,0,0,1,2
2,1,0,2,0,2,2,0,1,1
2,1,0,2,0,1,0,2,0,1
2,1,1,0,1,1,0,1,1,1
1,1,2,0,0,2,0,1,1,2
1,1,0,0,0,2,0,1,1,2
1,0,1,2,1,0,1,0,0,2
2,2,2,0,0,1,0,0,2,1
1,0,0,1,2,1,0,1,0,2
2,0,0,1,1,2,0,1,0,1
1,1,1,2,2,0,0,0,1,2
2,1,0,0,0,2,0,1,1,1
2,2,1,1,2,0,0,0,1,0
1,0,0,2,2,0,0,1,0,2
1,0,0,2,2,0,0,2,0,2
2,0,0,1,0,2,0,1,0,1
#leftward stop
0,0,0,0,0,2,2,0,0,2
2,0,0,0,0,2,2,0,0,0
0,0,0,0,0,0,2,2,0,2
0,0,0,2,2,2,2,0,0,2
2,0,0,0,2,2,2,0,0,0
2,2,0,2,0,0,0,2,0,1
2,0,0,0,1,2,2,0,0,0
2,2,0,1,0,0,0,2,0,1
0,0,0,2,2,2,1,1,0,2
0,0,0,2,2,2,2,1,0,2
1,0,0,2,2,1,0,0,0,2
2,0,0,0,1,2,1,1,0,0
2,2,0,1,0,0,0,1,1,1
1,0,0,2,1,2,0,0,0,0
2,0,2,0,1,1,2,1,0,1
1,0,1,0,1,1,2,0,0,0
2,1,1,0,0,0,0,0,2,0
1,0,0,1,1,2,0,0,0,0
1,0,0,0,1,1,1,0,0,0
2,0,0,1,2,0,0,1,1,1
2,0,0,2,0,2,0,1,1,1
0,0,0,0,1,1,2,1,0,1
1,0,0,1,1,2,0,0,0,0
1,0,0,0,1,1,2,0,0,0
2,0,1,1,0,0,0,0,0,1
2,2,1,0,0,0,0,0,1,0
2,0,0,1,0,2,0,1,1,1
#leftward counting
0,2,1,2,0,0,0,0,2,2
2,2,1,0,0,0,0,0,2,0
0,2,2,2,0,0,0,0,1,2
0,2,2,2,0,0,0,0,2,2
2,0,0,1,0,2,0,2,0,1
2,1,1,2,2,0,0,0,2,0
2,1,1,0,0,0,0,0,1,0
0,2,2,2,0,0,0,0,0,2
2,0,0,2,2,0,0,0,0,0
2,0,1,0,0,0,0,0,0,0
1,0,0,1,0,0,2,0,0,2
#ending
2,2,0,2,0,0,0,0,0,0
2,0,0,0,2,0,0,0,0,0
2,0,0,0,0,0,0,0,0,1
#diagonal mode
#2,0,0,0,2,0,0,0,0,0
#2,0,1,0,0,0,0,0,2,0
#0,0,0,1,0,2,0,2,0,1
#extra length
2,0,2,1,2,0,0,1,1,1
2,1,0,0,1,1,0,0,1,1
2,0,0,0,0,0,1,1,2,0
1,1,0,0,0,0,0,0,0,0
2,0,1,0,2,0,0,0,0,0
0,1,0,0,0,2,0,2,0,1
#back up
0,2,1,1,0,0,0,0,0,2
2,1,1,0,1,1,0,2,1,1
0,2,1,1,1,0,0,0,2,2
2,2,1,2,2,0,0,0,0,0
2,1,1,1,1,2,0,2,2,0
2,0,1,1,1,2,0,2,0,0
#TODO: convert binary counter push into binary counter pull
#TODO: collapse back into a single cell
ORDINAL ALERT/EDIT (ORDINAL EDIT?): I realized that g(n) is actually a w_2^CK function because the pattern doesn't have to stabilize: it could go on infinitely and never repeat but still have a finite population.

Explicit proof: given a statement {for all x there exists y such that z} make a [register machine/waterfall model/Collatz function/tag system storing the tape as a binary integer in sliding-block memory/register machine that simulates the next step of a Turing machine by simulating itself emulating f(input)/whatever as long as the system is universal and it can be simulated with a bounded population] that does the following:

Code: Select all

For the first (value of) x, look for a y such that z, then increase the population and move on to the next x, and so on
On the other hand, {there exists n such that for all generations g, the population is less than n} is a Sigma^1_1 statement describing a pattern's population being bounded.
Any sufficiently advanced software is indistinguishable from malice.

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Thread for CA-related fast-growing functions

Post by toroidalet » April 6th, 2021, 6:47 pm

Double post so as to prevent w edits on the last one: A potential w_3^CK-function is "the largest population reached infinitely many times (starting from 1 cell in any n state rule)", but I don't think it works. The value for each rule is in sigma_0^2 (there exists p such that for all q≥p, there exists n such that population q is reached less than n times), but in order for it to be higher than g(n) it has to go arbitrarily high infinitely many times, but the maximum population jump is from p to 9p, so the infinite pigeonhole principle prevents this.
Can it be fixed somehow? Perhaps "the largest population reached infinitely many times such that p+1 is also reached (in?)finitely many times" would work, there's probably a less contrived version.
Does anyone have any ideas about reaching w_4^CK in such a manner?



In the realm of fast growing functions that are not ridiculously contrived and fast growing, some other contest entries include longest-lasting diehards and largest anti-diehard produced from a single cell (I'm not sure if these are worth doing since it's a lot harder to make diehards and anti-diehards appear).
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Thread for CA-related fast-growing functions

Post by Moosey » April 7th, 2021, 11:53 am

toroidalet wrote:
April 2nd, 2021, 4:44 pm
ORDINAL ALERT/EDIT (ORDINAL EDIT?): I realized that g(n) is actually a w_2^CK function because the pattern doesn't have to stabilize: it could go on infinitely and never repeat but still have a finite population.

Explicit proof: given a statement {for all x there exists y such that z} make a [register machine/waterfall model/Collatz function/tag system storing the tape as a binary integer in sliding-block memory/register machine that simulates the next step of a Turing machine by simulating itself emulating f(input)/whatever as long as the system is universal and it can be simulated with a bounded population] that does the following:

Code: Select all

For the first (value of) x, look for a y such that z, then increase the population and move on to the next x, and so on
On the other hand, {there exists n such that for all generations g, the population is less than n} is a Sigma^1_1 statement describing a pattern's population being bounded.
Hm, this is clever and makes sense
in that case, g(n) is actually on the level of an oracle busy beaver I think? Nice that it's stronger than BB though; pretty interesting that it just happens to place at w2ck naturally-- usually such ordinals seem to be a result of contrived functions (like the ones you mentioned in the most recent post).

Regardless, that implies that g(n) eventually dominates not only all computable functions (which is hilariously trivial), but also quite a few uncomputables (for instance, there must be an n such that g(n) > BB(n)-- more or less the definition of uncomputables and also it's probably every number; also, because googology can be mind-bending this also includes hopelessly weak changes that initially seem like a massive boost; function iteration is the first thing that comes to mind. Time to find a lower bound on the number for something like m such that for all n > m, g(n) > BB^n(n))
not active here but active on discord

User avatar
toroidalet
Posts: 1514
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Thread for CA-related fast-growing functions

Post by toroidalet » April 10th, 2021, 3:15 pm

Moosey wrote:
April 7th, 2021, 11:53 am
in that case, g(n) is actually on the level of an oracle busy beaver I think? Nice that it's stronger than BB though; pretty interesting that it just happens to place at w2ck naturally-- usually such ordinals seem to be a result of contrived functions (like the ones you mentioned in the most recent post).
The basic idea is that since we set no time limit on the pattern's evolution (in particular, "largest population of a stabilizing single cell in any n-state rule" is w_1^CK), it could serially simulate arbitrarily many Turing machines, and we would need a halting oracle to see if it ends up simulating finitely or infinitely many of them. Also, note that a Turing-complete model can asymptotically simulate an oracle Turing machine by running it, guessing "no" every time it "asks" the oracle, then checking in parallel to see if it eventually ends up turning up a "yes" answer, then backtracking to that consultation and running it with a "yes" answer. It will end up simulating arbitrarily many steps of the oracle machine, but there is no way to see which times the fake oracle gave the wrong answer without proving otherwise. (more intuitively, while checking that it passed any one population would be RE, we have to check infinitely many such populations to show that it wasn't growing infinitely behind our backs)

Also, it is possible to show g(n)≥f(BB(n)) directly as follows: make a machine that simulates all n-state Turing machines at once, then calculates f(number of 1's written) every time one halts, storing the largest value. By applying this construction recursively, one can get any ordinal which is a recursive function of w_1^CK (this is equivalent to any ordinal less than w_2^CK by definition). To make it easier to simulate, one could substitute "all n-state Turing machines" with "a universal one running on all strings of a certain length".



To pivot this topic away from fast-growing functions in general and towards CA-related fast-growing functions, how many states do you think it would take to explicitly show busy-beaver/post-busy-beaver growth in g(n)? On one hand, it would probably only take 4-6 to construct universal-computer-type patterns, but on the other, the programs described in this post are hideously complicated.
Which of the following designs seems the most plausible for doing so (in order of machine simplicity, which is inversely proportional to program simplicity)?
[*]Waterfall model
[*]Register machine
[*]Prime number multiplier

The "prime number multiplier" utilizes the differences of spaceship speeds to multiply the distance a sliding block is at. One design would send out a faster and slower ship, and when the faster ship hit the block, it would turn into a different ship (either one slower than the other, or a ship heading back) and create a new block where they collide next. I am not sure if the "round down when dividing" method is Turing-complete, but "if the ships are out of phase (the distance is not divisible) then send a signal back indicating so" is transparently equivalent to a register machine.
It should also be possible to simulate a cyclic tag system which stores the string as a binary integer in sliding-block memory and has a separate register with 2^(n=length of string-1). Every cycle it would divide the string number by 2 and if the remainder is 1, add 2^n*(string to append in binary) then double or halve the other register as necessary.
Any sufficiently advanced software is indistinguishable from malice.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Thread for CA-related fast-growing functions

Post by Moosey » May 8th, 2021, 9:42 pm

bump
g(n) can be proven to be a strictly increasing function, that is, n>m implies that g(n)>g(m) (for natural n,m)

proof:
the best rule for g(n) can be modified to yield a better rule with a strictly greater final population by making it so that the new state is birthed by all other nonzero states when no other states would be born in the relevant position and other states do not care whether any cell is the new state or state zero. If the new state is never born, it implies that all patterns expand indefinitely in the original (and new) rule, and therefore that the original could not have been the best rule for g(n) because it does not qualify for g(n).
not active here but active on discord

User avatar
bibunsekibun
Posts: 345
Joined: April 17th, 2021, 7:58 pm
Location: Japan

Re: Thread for CA-related fast-growing functions

Post by bibunsekibun » May 8th, 2021, 10:27 pm

Square Function:SqC(n)
Make a huge square from a pattern where MCPS is n.
Output the number of cells in the final result.
Rule is OT or INT only.
Square must be a still life.
SqC(1)=1

Code: Select all

x = 1, y = 1, rule = B/S0
o!
SqC(2)=4

Code: Select all

x = 2, y = 2, rule = B2e/S013
o$bo!
SqC(3)≧3359631054192951769

Code: Select all

x = 3, y = 1, rule = B2-a3ajq4-nqz5-k6-n78/S02-ik3aj4akqwyz5-cjry678
obo!
sorry I can only speak Japanese, English is made by machine translation
I'm a fan of methuselahs

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Thread for CA-related fast-growing functions

Post by Moosey » May 9th, 2021, 3:01 pm

bibunsekibun wrote:
May 8th, 2021, 10:27 pm
Square Function:SqC(n)
Make a huge square from a pattern where MCPS is n.
Output the number of cells in the final result.
Rule is OT or INT only.
Square must be a still life.
Since you stipulate this has to stabilize, it should be of strength w1ck in the fgh. (Unless somehow none of the relevant rules are turing complete, a situation I highly doubt)

Unrelated: can anyone think of a function relevant to this thread which is computable?
not active here but active on discord

Post Reply