exactly how many diffrent rules are possible?

[iconmaster]

I would definatly like to know. Thx!

[Elithrion]

You can have a cell be born or not for each of 9 different numbers of neighbours and to survive or not for each of the 9. So, the total number of different rules is 2^18=262144. Although a lot of them are of course very similar.

[H. V. McIntosh]

You can have a cell be born or not for each of 9 different numbers of neighbours and to survive or not for each of the 9. So, the total number of different rules is 2^18=262144. Although a lot of them are of course very similar.

I wonder if that is quite right? A neighborhood contains 9 cells, each of which can be in one of two states (live or dead (or inert)); 512 different neighborhoods in all. Each one of these neighborhoods can be assigned one of those two values to describe its possible evolution, 2^512 in all; truly a huge number, but not the biggest there is.

The rules considered for Conway's Life weren't chosen quite so arbitrarily as that; only the occupancy of the neighborhood was taken into account. That is, if there were only one live cell, it could sit in any one of the nine cells making up a neighborhood, and all of them would be deemed to evolve the same way and there would be just one rule, not nine different rules. And so on. Rules constructed according to occupancy are called totalistic rules. But there is a little more variety to Life than that; the central cell is exceptional, occupancy being reckoned according to the content of the remaining cells, having noted its own value. In other words, a semitotalistic rule.

There are still plenty of those; 9 different sums (0 - 8) and thus 2^9 = 512 choices for the new cell. Coming back to the central cell, there are 2 choices and each of them can be followed by the choice of a rule for the outer neighborhood, giving 2 x 2^9 = 2^10. Which, curiously, is the number of totalistic rules. But the ways to get 0+10 and 1+9 are different than getting 10 all at once, so the two alternatives would give different kinds of evolution.

Apart from wondering whether this analysis is correct or not, the Life neighborhoods have symmetry and one might not want to consider symmetrically related rules as actually being different. Besides the eight symmetries (rotations and reflections) of the Moore neighborhood, complementation is a symmetry, whereby all 0's and 1's (or live's and dead's) are exchanged. Rather than simply dividing the supposed number of rules by 16, account has to be taken of certain rules which are actually symmetric and identical to their mirror images (or whatever). For example, for Wolfram's one dimensional cellular automata, out of a possible 256 first neighbor binary rules, only 88 are "really" different. I don't know whether anyone has actually reckoned this out for rules similar to Life, it's just a bit of group theory.

-hvm

[calcyman]

In a neighbourhood of size n, where each cell can take one of x states, the number of possible rules is:

rules = x ^ (x ^ n)

So for the Moore neighbourhood with 2 states (on which Life is defined), there are 2 ^ (2 ^ 9) = 2^512 rules.


However, cellular automata can be defined with arbitrary neighbourhoods and arbitrary numbers of states.


Golly can run CAs with up to and including 256 states, using the Moore neighbourhood, so Golly can run 256 ^ (256 ^ 9) rules.


This is a number with 11372591694895835406911 decimal digits!

[MadMan]

OK, granted that there are a jillion different rules for cellular automata based on immediate neighborhoods alone, consider the 3-4 alternate life universe. I have never found any program to run this. It is just not popular enough.

In 3-4 Life, still-lifes are rare and only the Block (I call it the Vermin) ever appeared naturally. The others are engineered. In contrast, natural oscillators are common. All too often a small pattern grows malignantly showing no cyclic behaivor or order in its endless expansion in all directions. In Conway's Life, only the Spacefiller family shows such amazing behaivor. "3-4 Life" just does not have the richness of regular Life.

00... This grows malignantly without limit and its final form -IF ANY - has never been found -in 3-4 Life.
.00.. In regular Life, this becomes 4 Blocks (or Vermin) at 70 or so. I HAVE found several long-term ancestors.
..00.

If only 6 of the neighborhood blocks are taken into consideration , one can -with difficulty & care- attempt Hexagonal life with a square graph grid.

.. x I know even less about Hexagonal Life than I do 3-4 Life. (My sourses are from the 80's. I am prepared to stand corrected)
.0.
x.. (x are neighborhood units NOT to be considered.).


And no consensus on 3-D Life seems to have been adopted.

[calcyman]

MadMan:

In Conway's Life, only the Spacefiller family shows such amazing behaviour.

The explosions in Type-III cellular automata (e.g. 3-4 Life) are irregular and uncontrollable. Conversely, the spacefillers in Life are completely regular, and a single block in the vicinity of the spacefiller will quickly ground it to a halt, whereas the irregular explosions engulf surrounding debris whilst themselves remaining completely unperturbed. As yet, no patterns in B3/S23 (Conway's game of Life) have exhibited Type-III-style growth. (Yes, I've just discovered that the IceNine agar was purely speculative.)


You seem to have altered the question to "exactly how many interesting rules are possible?" That question is far more difficult to answer, and the definition is very fuzzy. Do you consider the infinity of engineered rules (e.g. John von Neumann's 29-state rule) to be interesting? Some people adopt the approach of "Yes, but the rule is hardly natural, is it?"; others state "Wow! I can build tiny universal constructors in this rule."

Life is especially interesting since it is a very basic rule, exhibits type-IV behaviour and allows universal computer-constructors to be built.

[Elithrion]

In a neighbourhood of size n, where each cell can take one of x states, the number of possible rules is:

rules = x ^ (x ^ n)

So for the Moore neighbourhood with 2 states (on which Life is defined), there are 2 ^ (2 ^ 9) = 2^512 rules.

What? How do you figure? Consider our usual notation for rules: B123456789/S123456789. It is clear that for each number we must either choose to list it or not in each of B and S. I.e. two options for each number, 18 numbers in total. So that the total number of choices we have is 2^(2*9). To generalise, the correct number of rules of this sort would be x^(x*n).

[calcyman]

What? How do you figure? Consider our usual notation for rules: B123456789/S123456789.

You're already imposing a restriction on it: this assumes that all of the surrounding cells are summed. Consider the ShipLife variant, which behaves exactly like Life except for the neighbourhoods:

Code: Select all

**. .**
*.* *.*
.** **.

where the central cell becomes live next generation. You can't express, or any asymmetric rules, that in the B/S form.

To generalise, the correct number of rules of this sort would be x^(x*n).

That only works for outer-totalistic rules; the definition of a cellular automaton does not require this.

[Elithrion]

Ah, my apologies, I had for some reason (again >.>) assumed that restriction.

[H. V. McIntosh]

.... MadMan:You seem to have altered the question to "exactly how many interesting rules are possible?" That question is far more difficult to answer, and the definition is very fuzzy. ....

Conway himself seems to have offered an opinion, wishing for a rule in which an initial population neither died out completely nor increased without limit. As I recall, in the original Scientific American exposition the evolution was rather delicately balanced, and a prize was offered for a configuration which would actually grow indefinitely, albeit non-explosively. This requirement was rather similar to that embodied in Wolfram's Class IV which came along somewhat later. And which turned out to be somewhat nebulously defined; even undefinable.

Statistical evidence can be gathered for Conway's criterion, thanks to the ideas of Seiden and Schulmann or Dresden and Wong. Similarly to defining a rule by occupancy, or density, of live cells in a neighborhood (the totalistic rules), think of the probability that a cell is live. In other words the fraction of live cells taken over a large expanse rather than just a neighborhood. Take p as the probability of a cell being live, with q = (1 - p) as the probability that it is not. According to the specifications of the rule in question, the probability of a cell being live in the next generation, being p in the present generation, is a polynomial in terms p^i q^(n-i) with i running from 0 to n. This is a Bernstein polynomial; graphing it as a function of p gives the return map, an indication of how evolution affects the density of live cells.

Fixed points and their stability are the significant features of return maps. The density at an unstable point is avoided during the evolution, the more so the larger the multiplier. Conversely stable densities persist, even though the precise location of the live cells can be quite variable. In other words, fixed density does not imply still life, although that is included. Dividing the two extremes are the neutral fixed points, with unchanging density. Even though probabilities are real, positive, and confined to the interval (0, 1), complex fixed points of the Bernstein polynomials have a significant influence on their behavior on the real line.

Superstable and superneutral are also significant conditions wherein the adjectives are exaggerated by the behavior of derivatives at those fixed points. So in the end, a possible definition of an "interesting" rule might be that its return map have a superstable fixed point and another superneutral point. The latter implies not just a constant density, but a modest range of nearly constant densities.

Conway's Life seems to fulfill this description; superstable fixed point at zero density (vacuum) and somewhat superneutral at around 0.37. Many of Wolfram's Class IV can also be mentioned, but unfortunately the notorious Rule 110 has an ether rather than a vacuum and I have not been able to decide on a suitable rationale for it. But otherwise, the criterion seems to be workable; moreover the graph is easily constructible.

A final precaution --- the construction of the return map depends on the usual probabilistic assumptions of independence and exhaustivity. These hold for a single generation, but thereafter composition rather than iteration must be used, since reusing the same cell in different contexts infringes on independence. On the other hand, general observations such as maximum or minimum densities, and the dispersion induced by unstable fixed points, seem to carry over usably.