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

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.