paultsui wrote:One thing I don't really get - You mentioned that to determine evolutionary behaviour, one should consider a 4x4 or 5x5 area and count the number of possible states that could be evolved. Does one need to use periodic boundary condition (i.e. torus universe) when doing the measurement? Because if one considers only a small patch of the universe, then a lot of information would lost due to the fact that quite a lot of the patterns simply move out of the 4x4 patch. Shouldn't this be a problem?
The point is not to determine a specific pattern's behavior, it is to determine how much a rule favors certain environments over others. These environments would be expected to become more numerous when a random starting state is created and let evolve (one of 50% density should contain equal proportions of all possible environments, if we treat rotations and reflections as distinct) and from this some conclusions might be drawn.
Also we would consider all possible 4×4 areas, not anything "measured" from a pattern.
For a simple example, in rules with B345678/S234567, a 2×2 area with 3 cells will always become one with 4 cells, no matter what may exist outside of this area. Leave B8 out, and only 128 of the 4096 neighborhoods will not lead to 4 cells in the center from 3 cells in the center… This may still be critical however. In B34567/S234567 it is actually easy to find patterns that fill the plane with regular mesh, ie. in which all 2×2 areas have 3 cells. (Intuitively, this seems to be because an overall high proportion of 3-cell 2×2 areas would also imply an overall high proportion of those 128 neighborhoods in which there are 5 live cells surrounding the dead cell.)
paultsui wrote:In addition, can you justify why one should use a 4x4 or 5x5 area?
Simply because a 3×3 area is not sufficient for getting information on configuration frequency, only how common birth and death would be. This requires assuming that the probability of the states of adjacent cells in another cell's neighborhood are independant (which is not the case).
That still makes for a very quick test run of this idea, tho… So let's consider a few chaotic rules:
— Seeds: 28 B2 environments. 0 survival environments.
A density ρ would approximately mean that each cell has a probability ρ of being live; hence, the probability of finding a dead cell with a B2 environment is 56ρ²(1-ρ)⁷. The density after once generation is exactly the density of the previous kind of cells. If ρ is a stable density, then ρ = 56ρ²(1-ρ)⁷, which has the roots ρ = 0, ρ ≈ 0.0207, ρ ≈ 0.345.
Running 10 random starting configurations and sampling areas of 100×100, it seems the density of random chaos in Seeds is about 0.0209. So the first nontrivial root here actually fairly well corresponds to the empirical results
I'm not sure what to make of the 2nd root, Seeds has no stable agars and the previous analysis does not apply to oscillators (they can have different densities for different phases). Although I will mention that the first oscillating agar I remembered in Seeds is the following:
Code: Select all
x = 30, y = 30, rule = B2/S
2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5b
o5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo
$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5b
o5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo$
2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo$5bo5bo5bo5bo5bo$o5bo5b
o5bo5bo$bo5bo5bo5bo5bo$2bo5bo5bo5bo5bo$3bo5bo5bo5bo5bo$4bo5bo5bo5bo5bo
$5bo5bo5bo5bo5bo$o5bo5bo5bo5bo$bo5bo5bo5bo5bo!
…which has an average density of ⅓, not far from 0.345.
— 3-4 Life: 56 B3 environments, 70 B4 enviroments. 56 S3 environments, 70 S4 environments.
Live cells in the next generation should have a density of about 70ρ⁵(1-ρ)⁴ + 126ρ⁴(1-ρ)⁵ + 56ρ³(1-ρ)⁶. For a stable density, we get the non-trivial roots ρ ≈ 0.207 and ρ ≈ 0.496 (and some roots > 1, but we don't care).
From a similar sample of 10 areas of 100×100, I get a density of about 0.427 for random chaos. Seems close (but not too close) to the 2nd root.
— DryLife: 56 B3 environments, 8 B7 environments. 56 S3 environments, 28 S2 environments.
Live cells in the next generation should have a density of about 8ρ⁷(ρ-1)² + 56ρ⁴(1-ρ)⁵ + 56ρ³(1-ρ)⁶ + 28ρ²(1-ρ)⁷. We get 2 real solutions ∈ (0,1] for a stable density: ρ ≈ 0.0448, ρ ≈ 0.404.
Sampling random chaos givs a density of about 0.086 (a very loose estimate, as DryLife becomes homogenous at only much larger scales than 100×100… individual samples ranged from 0.0425 to 0.102). I would not have expected this one to match very well tho, as chaos in DryLife is concentrated in "clouds", and various edge effects are going to be important. The density of a single "cloud" seems it might well be around 0.4, however…
— B12345678/S46: One A0 environment. 70 S4 environments, 28 S6 environments.
Life cells in the next gen should have a density of about (1-ρ)(1-(1-ρ)⁸) + 70ρ⁵(1-ρ)⁴ + 28ρ⁷(ρ-1)². This has only one non-trivial applicable root, ρ ≈ 0.644. Density of chaos in this rule turns out to be about 0.647. Rather close again.
I probably ought to test some "shrinking chaos" rules as well, but it seems that even this method can predict to some extent the density of chaos, at least in the more "white-noisey" rules.
paultsui wrote:However, can you explain in more details why focusing on a 4x4 or 5x5 area would be enough? i.e. is it true that the chaotic-ness of a 4x4 patch (more or less_ the same as the chaotic of the corresponding infinite grid?
I don't know if this is actually the case; this is simply an educated gess that's going to require investigation (but the previous tests look promising). I don't expect a rigorous general proof to exist, as growth behavior of CA patterns includes the halting problem…