Circularly Expanding Pattern Conjecture
-
- Posts: 11
- Joined: February 8th, 2023, 2:44 am
Circularly Expanding Pattern Conjecture
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.
-
- Posts: 11
- Joined: February 8th, 2023, 2:44 am
Re: Circularly Expanding Pattern Conjecture
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.
- confocaloid
- Posts: 3029
- Joined: February 8th, 2022, 3:15 pm
Re: Circularly Expanding Pattern Conjecture
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:with a circle superimposed, the circle generated by a simple enough Golly script:Code: Select all
x = 4, y = 3, rule = B3/S345 2o$2o$b3o!
Code: Select all
script
calcyman wrote: ↑April 10th, 2011, 5:45 amI 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.This shows B3/S345 run to 30,000 iterations from a small asymmetric seed:
ynotds wrote: ↑April 11th, 2011, 2:26 amIn 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 seem to recall that this doesn't actually asymptotically approximate a perfect circle
127:1 B3/S234c User:Confocal/R (isotropic CA, incomplete)
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
-
- Posts: 11
- Joined: February 8th, 2023, 2:44 am
Re: Circularly Expanding Pattern Conjecture
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.
.
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.
-
- Posts: 11
- Joined: February 8th, 2023, 2:44 am
Re: Circularly Expanding Pattern Conjecture
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.
-
- Posts: 11
- Joined: February 8th, 2023, 2:44 am
Re: Circularly Expanding Pattern Conjecture
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.
Re: Circularly Expanding Pattern Conjecture
Yes -- the "in real time" constraint is exactly what we need here.PraseodymiumSpike wrote: ↑February 11th, 2023, 12:39 amI 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.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?