Friday, January 14, 2011

Simple, statistical and emergent properties

Consider John Conway's Game of Life. This game is important because it gives us a conceptual handle on simple, statistical and emergent properties.

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 G0 of finite size, with some specific set of alive and dead cells, there is exactly one grid G1 of the same size as G0 that results from the transformation rules applied to grid G0. It might or might not happen to be the case that G0 and G0 are identical. If G1 is not identical to G0, then we can apply the transformation rules to G0 to determine grid G2.

If we preserve the grid size during transformations, then we know that for every grid G, there is either a final grid Gn such that Gn is identical to Gn-1, or there is a final period of grids Gn,m (with count m - n) such that Gm+1 is identical to Gn. (A final grid is the same as a final period of grids of count 1). The maximum final period must be less than 2s 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 2s.) 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 Gy,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. 2c, 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 Gn+1 by first adding an extra margin of dead cells around Gn, 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 might get 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.