Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 25, 2003
Last updated: Mar. 25, 2003

Prioritized Predicate Rules (PPRs)

I've stumbled onto a whole new way to define CA rules that opens up a huge new family of possible CAs. (This requires the use of the Celluar Automaton program "MCELL".) I call the method Prioritized Predicate Rules or PPRs, and I've written a configurable MCell DLL to support the whole family. You may download the DLL and sample rules here. You may also view the download readme file here.

The way the rules are defined is very simple, but the number of possible rules is astronomical. Plus, the rules can be applied to either the Moore neighborhood or the von Neumann neighborhood. Also this method of rule definition is very well suited to creating autocatalytic sets which makes it useful for exploring self-organizing systems.

The rule is defined as a list of predicated, or conditional transitions. Each transition consists of a set of three state numbers like this:

A(B)->C

A is the state number of the current center cell.

B is the predicate state

C is the state to transition to if and only if the neighborhood contains at least one cell in the predicate state B.

For example, the transition: "1(2)->3" means that state 1 will transition to state 3 if there is at least one cell in state 2 anywhere in its neighborhood. The number of neighbors is irrelevant, so it doesn't matter if there is one state 2 cell or if all 8 neighbors are in state 2. All that matters is that at least one of the neighbors is in the predicate state.

But what happens if there are two rules like: "1(2)->3" and "1(4)->5"? If the center cell is state 1 and has a neighbor in state 2 it wants to transition to state 3, and if it has a neighbor in state 4 it wants to transition to state 5. But what if it has both kinds of neighbors in its neighborhood? It can't make both transitions at the same time. That's where the "Prioritized" of "Prioritized Predicate Rule" come into play. The rules are listed in priority order where the last rule listed for that state has the highest priority when a conflict occurs. In other words, an earlier rule in the list will be applied only if some later rule can't override it. So with rules "1(2)->3" and "1(4)->5" mentioned above if state 1 has only neighbors in state 2 it will transition to state 3, but if it has both a neighbor in state 2 and a neighbor in state 4 the state 4 rule, being listed last, takes precendence.

States not mentioned in a transition are ignored. For the transition "4(16)->3" it doesn't matter if the the state 4 cell also has neighbors in states 7, 14, 23 and 199. The transition only cares about state 16 being present or absent somewhere in the nieghborhood.

A rule can also be written as "A(*)->B" where "*" means "any state". State A will always transition to state B unless some later rule overrides it. So in the example above the list of rules: "1(*)->9; 1(2)->3; 1(4)->5" means state 1 goes to state 9 unless any later rule overrides it. This is the default transition for the state and must always be listed before other rules for the same state. If the default transition is listed last it will override all tansitions for that state and will be the only transition that ever happens for that state.

Finally, if a state has no transitions at all the global default is for the state to remain unchanged.

Here's an example:

If a single cell of state 1 is placed in the middle of empty space all state 0 cells that touch it will turn to state 1 (0(1)->1) and state 1 will quickly flood all of space. Now place a single cell of state 2 in the middle of that flood. All state 1 cells that touch it will turn to state 2 (1(2)->2) and state 2 to will immediately vanish to state 0 (2(*)->0), so a wave of state 2's will eat all the cells in state 1 and return space to its empty state.

Now put a cell in state 1 next to a cell in state 2 and watch them battle it out for control of space. State 1 tries to flood space and state 2 tries to destroy state 1. An interesting battle.

Extended PPR Rule Definitions

The most natural extension of the above method of defining rules is to allow more than one predicate, requiring that all predicates be present. Such a rule could be written:

A(B,C)->D

where both states B and C must be present in the neighborhood of A for the transition to take place. Extending this extension even further we can imagine transitions written as A(B,C,D)->E, or A(B,C,D,E,F)->G.

In addition it would be useful to be able to state a rule in the form:

A(B,-C)->D

where "-C" indicates that state C must not be present for the transition to take place. Notice that we have taken the logical AND of all the predicates. If it is necessary that a transition of A to E takes place if the expression B AND (C OR D) is true this can be expressed as two seperate transitions:

A(B,C)->E
A(B,D)->E

If the negation of an entire expression is required, for example: NOT(  B AND ( C OR D )) we can invoke DeMorgan's theorem and rewrite the expression as ( NOT B ) OR NOT( C OR D ), and applying DeMorgan again: ( NOT B ) OR (( NOT C ) AND ( NOT D )). This is then transcribed into transitions as:

A(-B)->E
A(-C,-D)->E

Footnote on Autocatalytic Sets

A collection of interacting entities often react in certain ways only, e.g. entity A may be able to affect B but not C. D may only affect E. For a sufficiently large collection of different entities a situation may arise where a complete network of interconnections can be established - the entities become part of one coupled system. This is called an autocatalytic set, after the ability of molecules to catalyse each other's formation in the chemical equivalent of this arrangement.

--From FAQ for USENET Newsgroup comp.theory.self-org-sys

Clearly realtionships such as those mentioned in the definition above can easily be established with a CA rule consisting of a system of PPR transitions that form a directed graph of catalytic interconnections.