Briefly, we have a grid of cells, and each cell in the grid has a state: It can be "alive" or "dead" (or on/off, 1/0, etc.) The state of a cell is a

**simple property**.

There are also statistical properties of a grid, such as the number of alive cells, the mean or median number of alive cells in some set of distinct arbitrarily-defined subgroups of cells (e.g. the mean or median number of alive cells in distinct squares of nine or sixteen cells, or the mean number of consecutive alive cells, etc.) We can define these sorts of statistical properties in terms of computability: A property is statistical if it can be computed for a finite grid by a polynomial of the size of the grid.

The Game of Life also specifies transformation rules: Given a grid G

_{0}of finite size, with some specific set of alive and dead cells, there is exactly one grid G

_{1}of the same size as G

_{0}that results from the transformation rules applied to grid G

_{0}. It might or might not happen to be the case that G

_{0}and G

_{0}are identical. If G

_{1}is not identical to G

_{0}, then we can apply the transformation rules to G

_{0}to determine grid G

_{2}.

If we preserve the grid size during transformations, then we know that for every grid G, there is either a final grid G

_{n}such that G

_{n}is identical to G

_{n-1}, or there is a final period of grids G

_{n,m}(with count

*m*-

*n*) such that G

_{m+1}is identical to G

_{n}. (A final grid is the same as a final period of grids of count 1). The maximum final period must be less than 2

^{s}where

*s*is the size of the grid. (It has to be strictly less because we know that some grids are part of are part of periods smaller than 2

^{s}.) It should be clear that the final period of grids is determined exclusively by the initial grid G: For every grid G, there is exactly one final period of grids G

_{y,z}. Thus the final period is

**ontologically reducible**to the initial grid. (Note that a final grid is not necessarily

*epistemically*reducible to the initial grid: There are many initial grids that produce the same final period of grids.)

However, we cannot generally compute the final period of grid G in polynomial time. For size-preserving transformation rules, we can generally compute the final period in only

*exponential*time, i.e. 2

^{c}, where

*c*is less than the grid size

*s*. We'll classify these properties as

*emergent*.

Things get even more interesting when we do not preserve grid size. Conceptually, we can compute G

_{n+1}by first adding an extra margin of dead cells around G

_{n}, applying the transformation rules, and then trim the result to the grid containing all the live cells. Alternatively, we can start with an enumeration of a finite number of alive cells, each with a position of finite size, and apply the transformation rules, which will result in another finite number of alive cells (which may be more or less than the original number) each with a position of finite size. Again, it seems clear that the result (whatever it happens to be) is strictly ontologically reducible to the initial state: one initial state will produce exactly one result.

The result can be strict periodicity such as a block or boat with count 2, or a blinker with count 2; or abstract periodicity such as a block plus a glider. But since the grid size is not constant, we are not assured even that there is always

*any*periodicity, strict or abstract. So not only can we not generally calculate the computational complexity

*at all*to determine the final period, we can't even generally tell in finite time if some finite initial state even

*has*any final period. And yet we have not at all removed the conditions of strict ontological reducibility.

The Game of Life, and the notions of simple, statistical and emergent properties is not just interesting in and of itself, it has some interesting philosophical implications for both atheism and economics.

## No comments:

## Post a Comment

Please pick a handle or moniker for your comment.It's much easier to address someone by a name or pseudonym than simply "hey you". I have the option of requiring a "hard" identity, but I don't want to turn that on... yet.With few exceptions,

I will not respond or reply to anonymous comments, and I may delete them.I keep a copy of all comments; if you want the text of your comment to repost with something vaguely resembling an identity, email me.No spam, pr0n, commercial advertising, insanity, lies, repetition or off-topic comments. Creationists, Global Warming deniers, anti-vaxers, Randians, and Libertarians are automatically presumed to be idiots; Christians and Muslims

mightget the benefit of the doubt, if I'm in a good mood.See the Debate Flowchart for some basic rules.

Sourced factual corrections are always published and acknowledged.

I will respond or not respond to comments as the mood takes me. See my latest comment policy for details. I am not a pseudonomous-American: my real name is Larry.

Comments may be moderated from time to time.

When I do moderate comments, anonymous comments are far more likely to be rejected.I've already answered some typical comments.

I have jqMath enabled for the blog. If you have a dollar sign (\$) in your comment, put a \\ in front of it: \\\$, unless you want to include a formula in your comment.