ConwayLife.com

I conjecture the following: In no non-isotropic cellular automaton is there a circularly expanding pattern—a pattern such that there exists a natural number n and a constant k such that the number of generations it takes for a cell (x,y) to first become alive differs from (x^2+y^2)^(1/2)/k by at most n.

I should clarify what I mean by "non-isotropic cellular automaton". I am only including cellular automata that can be notated using the method described in the "Range-1 Moore neighbourhood" section of this page: https://conwaylife.com/w/index.php?titl ... did=116684.

The discussion in "Smallest slowest spaceship?" thread seems relevant:

ynotds wrote: ↑

April 9th, 2011, 10:47 pm

...
This shows B3/S345 run to 30,000 iterations from a small asymmetric seed:

Code: Select all

x = 4, y = 3, rule = B3/S345
2o$2o$b3o!

with a circle superimposed, the circle generated by a simple enough Golly script:

Code: Select all

script

calcyman wrote: ↑

April 10th, 2011, 5:45 am

This shows B3/S345 run to 30,000 iterations from a small asymmetric seed:

I seem to recall that this doesn't actually asymptotically approximate a perfect circle, although it is indeed possible to engineer cellular automata which do. For example, the FHP lattice gas automaton has macroscopically circular waves.

ynotds wrote: ↑

April 11th, 2011, 2:26 am

I seem to recall that this doesn't actually asymptotically approximate a perfect circle

In the very long term you must get c/2 common spaceship collisions in the diagonal corners seeding new small circles so the total pattern will eventually diverge from circular. As the circle radius grows at just under c/4, potentially colliding spaceships can only ever form within not much more than 15° of the diagonals with consequent new centres correspondingly close to the growing circle. More dramatically, it is also relatively easy to engineer patterns ("engines") at the growing edge which move at c/2 and thus appear to drag out a triangle bounded by two tangents to the circle. Aside from those kinds or localised irregularities, I don't see any reason to assume divergence from at worst a near regular n-gon with very high n. Having seen a lot of similar near circular growth phases in other rules, I have formed an impression that their circularity is like that of the cauliflower, a statistical averaging of bumps.

I think that my criterion is actually a bit more strict than asymptotically approaching a circle. It's closer to this:
.
If we take the red region to be the set of cells that have been alive at some point, then the boundary of red region has to stay in between 2 circles whose radii are increasing at the same rate. The distance between the circles does not increase in proportion to their size, so if you were zooming out with 1 of the circles, the 2 circles would appear to get closer and closer together, and furthermore, they would do so at a rate completely determined by n and k. If the red region only had to asymptotically approach a circle, then it could take its sweet time doing so. But the way I've defined it, it has to reach a certain level of circle-ness within some amount of time specified by n and k. The following diagram explains why I don't think that's possible.

Essentially, I think a constructor at the point shown will eventually have to know the angle theta that it's supposed to be propagating in arbitrarily precisely for the pattern to be circularly expanding as I have defined it. But it must keep expanding at a rate of k, so it must move a distance of at least 1 cell in 1/k generations. For the sake of argument, let's say the arc shown is the arc it has to get to within 1/k generations. This means that all of the information on theta will have to get to the constructor within 1/k generations, which means it must all be within a 2c/k-by-2c/k square centered on the constructor. As this space is not infinite, and the necessary precision of theta becomes arbitrarily large, there will eventually not be enough room in the square to hold the information.

Talking about FHP specifically, I think the person was talking about waves in a medium that already has a certain density of living cells, so my conjecture doesn't really apply anyway.

I found this interesting article, but I don't know if it actually applies to this problem or not: https://core.ac.uk/download/pdf/82429819.pdf.

PraseodymiumSpike wrote: ↑

February 11th, 2023, 12:39 am

I found this interesting article, but I don't know if it actually applies to this problem or not: https://core.ac.uk/download/pdf/82429819.pdf.

Yes -- the "in real time" constraint is exactly what we need here.