CA Explorations - PPR Readme file

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

PPR.ZIP Readme file

Prioritized Predicate Rules (PPRs) for MCell --------------------------------------------

By Gary J. Shannon

Mar. 30, 2003

Installation ------------

Contents of the download zip file:

1. This readme 2. shannon.dll 3. AcidBath.mcl 4. AcidBath.ppr 5. Flood Gate.mcp 6. FloodGate.mcl 7. FloodGate.ppr

Place these files in the following locations: (You will need to create the directory "ppr" in "UserDLLs" directory.

shannon.dll -> C:\Program Files\MCell\UserDLLs\shannon.dll

AcidBath.mcl & FloodGate.mcl -> where you keep your mcl files

AcidBath.ppr -> C:\Program Files\MCell\UserDLLs\ppr\AcidBath.ppr

FloodGate.ppr -> C:\Program Files\MCell\UserDLLs\ppr\FloodGate.ppr

Flood Gate.mcp -> C:\Program Files\MCell\System\Flood Gate.mcp

Eplanation of files -------------------

shannon.dll

This configurable DLL implements the entire family of Prioritized Predicate Rules (PPRs).

AcidBath.mcl

A sample mcl using the AcidBath.ppr rule

AcidBath.ppr

The actual rule for AcidBath.mcl. An astronomical number of different PPR rules are possible. Each rule, since it can potentially be much larger than the 256 bytes allowed inside MCell for rule tables, is saved to a .ppr file. These rule files can be created within the DLL or can be created or edited using a text editor as described below.

Flood Gate.mcp

A palette that works well with the AcidBath.ppr rule.

FloodGate.mcl and FloodGate.ppr

A pattern and ppr rule that implements the fundamental logic gates for digital logic. The mcl files shows some example oscilators, diodes, AND and OR gates, invertors, memory latches and so on.

How PPR rules work ------------------

A PPR or Prioritized Predicate Rule is, as its name suggests, a list of predicate (conditional) transitions in priority order. The rules are written in the form:

A(B)->C

Which means: "A transitions to C IF AND ONLY IF there is at least one state B cell in its neighborhood."

In addition, a rule may have more than one predicate. For example:

A(B,C)->Q

Which means: "A transitions to Q IF AND ONLY IF it has one or more state B AND one or more state C in its neighborhood. The number of predicates is limited by the size of the neighborhood. The von Neumann neighborhood has 4 neighbors and so a maximum of 4 predicates can be used:

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

The Moore neighborhood has 8 neighbors and transitions may include up to 8 predicates, although an 8-predicate transitions has very little likelyhood of ever being satisfied since every single one of the states mentioned must be present for the transition to take place.

Transitions may mention their own state as a target or predicate. In this case, the cell itself does NOT count, so the transition A(A)->B will only happen if state A has another neighbor besides itself also in state A.

Unconditional transitions will occur regardless of neighborhood.

A(*)->B

Means: "A ALWAYS transitions to B no matter what the neighborhood."

Predicates may be negated in which case the transition only takes place if the named state does NOT occur anywhere in the neighborhood.

A(B,-C)->Z

Means: "A will transition to Z IF AND ONLY IF B is present in the neighborhood AND C is NOT present in the neighborhood."

It may happen that a particular state has more than one transition assigned to it. For example, the AcidBath.ppr rule included in the zip file looks like this:

State 0 = grey wall (using Flood Gate Palette) State 1 = open pathways State 2 = red molecule State 3 = blue molecule State 4 = reb/blue catalyst (purple)

Transitions:

1(2)->2 2(3)->3 3(*)->1 2(4)->3 0(2,3)->1 2(3,1)->0 3(2,1)->0 3(-2)->3

Notice that there are three transitions for state 2.

2(3)->3 2(4)->3 2(3,1)->0

What happens of all three of those conditions are satisfied? That's where the "Prioritized" in "Prioritized Predicate Rules" comes into play. Only the last transition who's condition is satisfied will be applied. In other words, a later transition who's condition is satisfied will always override an earlier transition. (Internally, the transitions are examined from the bottom of the list upward until the first one is found that is satisfied.)

If no transition is satisfied then the global default is for the state to remain unchanged. That defualt can be overridden by a default transition like "3(*)->1" in the AcidBath rule. It is important that the default transition be placed early in the list before any other transitions for that state so it does not always override the other transitions for that state.

An Explanation of the AcidBath rule -----------------------------------

The grey impenetrable wall of the containment vessel is made of state 0.

State 1 (white) is the open space inside the container.

State 2 (red) will propagate through all of the space available to it, but when it hits the walls of the containment it can spread no further. I.e., any empty space cell (state 1) will become state 2 if it has any state 2 nieghbor: "1(2)->2".

State 3 (blue) is a very short-lived state. The rule "3(*)->1" insures that it will turn back into empty space immediately. However, state 3 is able to consume state 2 and remain alive by transforming state 2 to itself: "2(3)->3". Thus state 3 will consume state 2 whenever possible. If State 3 is not busy consuming state 2 it just waits for a state 2 to come along with 3(-2)->3. For some reason without this transition the behavior looks the same but some of the more interesting features such as tunnel diggers never appear. Who knows why.

Since state 3 is so short lived there must be a way to create a fresh supply of state 3. State 4 is a catalyst for the creation of state 3. The transition "2(4)->3" creates more state 2 whenever the catalyst is touched by state 2, which won't take long because state 2 likes to flood all available space.

Now comes the interesting part. Neither state 2 nor state 3 is able to breach the containment vessel, but together they form a reactive molecule that actually erodes away a bit of state 0 wall: "0(2,3)->1". I.e., when a wall cell is touched by both state 2 and state 3 it turns to empty space. However, the two reacting chemicals sacrifice themselves in the process, turning themselves into wall material: "2(3,1)->0" and "3(2,1)->0". In other words, the same proximity that caused the wall the crumble causes the acid to be neutralized.

To begin with when the two-state acid molecule attacks the smooth side walls they can destroy at most two wall cells. When they are neutralized they then become two new wall cells and there is conservation of wall mass. However, as the etching proceeds ragged edges begin to form where a single molecule of acid can destroy 3 or 4 wall cells before being neutralized. Bit by bit the wall is eaten away.

Then, around generation 9500, a new kind of larger and more reactive molecule emerges that has a unique shape that allows it to eat through wall material very quickly. It tunnels its way into the wall leaving a clean trail of red (state 2) and no chucks of wall debris.

Several other styles of tunneling molecules, including one that tunnels very slowly, but very steadily, begin to form around generation 12,000 and beyond, and eventually the whole containment vessel is eaten.

For more information on PPR rules visit my website at www.geocities.com/fiziwig/caintro.html

Editing ppr files -----------------

ppr files can be edited by clicking on "configure DLL" in the rules setup dialog in MCell, or they can be edited or created in a text editor. The format of a ppr file is:

Line 1: 'M' or 'V' for Moore or vonNeumann neighborhood, followed by the number of states. For example:

M,4

The remaining lines are the transitions stored without the "->" used above. For example the complete ppr file for the AcidBath rule is:

M,5 1(2)2 2(3)3 3(*)1 2(4)3 0(2,3)1 2(3,1)0 3(2,1)0 3(-2)3

A rule can be attached to an MCell configuration by clicking on "Configure DLL" in the rule setup dialog, loading the desired rule and clicking "Done". Then click "Apply" in the MCell rule setup dialog. This rule will now be saved with the MCell file and will be automatically loaded back in when that MCell file is reloaded at a later date.

Debugging note:

If you discover that your newly edited rule doesn't work properly, one thing to check is the number of states you specified. Make sure you haven't created transitions for sttes higher than the number of states minus one. If you have, reload the rule into the rule editor and correct the number of states entry.