User:Tropylium/Pattern

From LifeWiki
Jump to navigation Jump to search

A pattern is any configuration of cells on the plane.

Physical limitations preclude the simulation of patterns of infinite complexity. Patterns of finite complexity can be generated in many ways, but the most commonly explored class of patterns involve a static, periodic background (the medium), and a finite number of perturbations from this. This number may be, in fact, zero, in which case the pattern will be known as an agar.

Most other patterns operate using the vacuum as the medium. In this paradigm, the symmetry between different cell types is broken. The cell type that makes up the vacuum are normally called dead, while all other cell types are called live; any pattern of this sort is, then, characterized by the presence of an infinite number of dead cells, vs. a finite number of live cells. The foregoing discussion will be limited to patterns of this kind.

(nb: infinite wicks fit poorly into this scheme)

Area

An area is a subset of a pattern that is surrounded by at least two disjoint perimeters of dead cells. For rules using the Moore neighborhood, the perimeters will need to be rookwise connected; for rules using the von Neumann neighborhood, a kingwise connected perimeter will suffice. The evolution of any area to the next generation will be independent of any other areas, regardless of the exact transition rule.

Equivalently, given a subset of a pattern, the subset neighborhood can be defined as:

  1. All live cells in the subset.
  2. All dead cells that are neighbors to live cells in the subset.

Two subsets of a pattern then belong in different areas, if their subset neighborhoods are disjoint.

An example of a pattern that forms a single area:

........
.O.O....
....OO..
.....O..
..OOO...
......O.
........
.O..O...
...O....
........

If a rule is however fixed, it will be possible to however establish finer criteria for dividing a pattern in parts.

Cluster

A cluster is the rule-specific analogue of an area: a subset of cells delineated by less stringent criteria, that regardless has the property that its evolution can be predicted without reference to the other clusters present in the pattern.

In Conway's Game of Life, the following criteria are relevant for determining cluster status:

  • The existence of a rookwise connected perimeter of dead cells, where every cell only has one parent within the perimeter

The same does not hold in all Life-like cellular automata; e.g. in the rule Seeds, where two live cells is a sufficient criterion for the birth of a new cell, two Life clusters that occur within the same area can end up interacting.

The above single-area example pattern is in Life composed of four clusters, marked in the first figure with the letters A, B, C, D; and in the second figure separated by perimeters marked by asterisks:

........   *******.
.A.B....   *O*O..**
....BB..   ***.OO.*
.....B..   .*...O.*
..BBB...   .*OOO..*
......B.   .*....O*
........   ********
.C..D...   *O*.O*..
...D....   ***O.*..
........   ..****..

A cluster is, however, only determined in the context of the pattern in general. A subset may be a separate cluster in one pattern, but not in another. As an extreme example, consider e.g. clusters A and C above: these comprise only a single live cell, yet in by far most cases determining the evolution of a particular live cell requires reference to other cells.

Object

An object, loosely defined, is a part of a minimal partition of a pattern into non-interacting components.

In the context of general CA, the notion of an object is dependent on the definition of a medium. While the backdrop of cellular automata is a connected space (in the graph-theoretic sense), and no part of a pattern can be truly independent of its surroundings, it is desirable to abstract away from the predictable evolution of empty medium. The evolution of a pattern, then, can be decomposed into the evolution of its medium (infinite but easily predictable) and the evolution of its objects (finite, non-trivial to predict). The following discussion will presume vacuum medium.

a set of cells in a pattern, finite at least in one dimension, such that no reference to other cells in the pattern is necessary to predict its live cells' immediate development; and that the pattern cannot be divided in a set of smaller objects. An object, therefore, consist of a boundary of dead cells, of one neighborhood thickness (at least some of whose evolution necessarily depends on the cells beyond the boundary), containing one or more live cells.

Notes:

  • A pattern subset that does not necessarily fulfill the last criterion could be called an "objectoid". Another possibility is "pre-object", but this may be likely to be confused with a predecessor of an object.
  • Infinite but periodic wicks should probably be treated as objects; most agars should probably not, given that they will occupy the entire plane. This leaves "agars with holes" and "agar half-planes" (quarter-planes, etc.) as edge cases.

Objects can be further divided in strict objects and pseudo-objects. In a strict object, no reference to the live cells outside the object is necessary to identify cells that remain live, die, or are born. However, cells that remain dead may still be simultaneously within the neighborhood of more than one strict object. An object that can be divided in more than one strict object, then, is a pseudo-object.

The best-studied pseudo-objects are the pseudo still lifes, but also pseudo-oscillators, pseudo-spaceships, etc. are known (indeed, it is often trivial to extend a strict object into a pseudo-object).

Equivalently, strict objects are the parts of a partition of pattern into minimal sets of live cells such that any change of the live cells to dead within one partition will not affect any of the other partitions.

At least within Conway's Game of Life, it is not sufficient to define a strict object merely as a minimal set of live cells such that any change to other live cells will leave the evolution of the pattern unaffected. Consider a 5×5 square of live cells: the removal of any one of the 9 central cells will not affect the evolution of the pattern, as all cells within the central 5×5 square will be dead in the next generation regardless. However, it would seem strange to analyze the "removable" central cells as isolated dot sparks, since their isolatedness status is not independent. For example, the removal of all nine of them will produce a clearly different object; the 5×5 unfilled square is a large spark instead of a honey farm predecessor. Therefore, while the dynamics of a 5×5 block can be analyzed on a sub-object level, it cannot be consistently partitioned into smaller objects.

  • This issue is perhaps resolvable by adding an intermediate concept. Any one subtraction is an analysis into a dot spark (clearly an object by itself) plus a residual possibly-object; however, different possibly-object analyses will terminate in different minimal possibly-objects. Then, an object is a possibly-object that does not have a unique analysis as minimal possibly-objects (although it may have two or more such minimal analyses).

All polyplets (including polyominoes) are objects, though not necessarily elementary objects (a polyplet can still constitute a tie).

It would seem to be desirable to further define a term for a cell subset formed by an object with its boundary removed. It is this level of analysis that is often applied to conventional terms such as beehive. A honeycomb, for example, does not contain a beehive-as-an-object or a tub-as-an-object, but it does contain sets of cells that consitute a beehive/tub-as-an-object-sans-boundary. Mere shape is not meaningful, though: also identical evolution should be required.