Cellular Automata rules lexicon

Go back to MCell Home

Family: Margolus

Type: 2D, binary, in Margolus neighborhood

"Margolus neighborhood" CA family uses the simplest partitioning scheme where the lattice is divided in isolated blocks of size 2x2. Each block moves down and to the right with the next generation, and then moves back:

cycle 1 cycle 2

cycle 3

Margolus neighborhood rules define transitions applied to cells found in 2x2 blocks. This simple partitioning scheme turned out to be very useful for modeling physical systems. Another important property of Margolus neighborhood is that it allows for a very easy creation of reversible rules.

Margolus CA notation

The notation of Margolus automata has the "Mx,Dn1;n2;n3;..;n16" form, where:
Mx - subtype specification. Currently only one subtype is supported - "MS" (Simple, 1bit). Note that more complex Margolus rules can be specified even now using User DLLs.
D - specifies transitions of all possible neighborhood configurations. There exist 16 different 1-bit Margolus neighborhood configurations, numbered from 0 to 15:

0:, 1:, 2:, 3:, 4:, 5:, 6:, 7:, 8:, 9:, 10:, 11:, 12:, 13:, 14:, 15:

The "D" keyword accepts 16 values, separated with semicolons, that describe into which neighborhood (ngh) the given neighborhood should be changed.

Example:
Billiard Ball Machine is defined as follows: MS,D0;8;4;3;2;5;9;7;1;6;10;11;12;13;14;15
ngh 0 remains unchanged,
ngh 1 turns to 8 - the ball travels diagonally,
ngh 2 turns to 4,
ngh 3 remains unchanged,
ngh 4 turns to 2,
...
ngh 15 remains unchanged.

MCell built-in Margolus neighborhood rules

Name Rule Description
BBM MS,D0;8;4;3;2;5;9;7; 1;6;10;11;12;13;14;15 Famous Billiard Ball Machine - from Cellular Automata Machines.
A rule by Edward Fredkin.
BounceGas MS,D0;8;4;3;2;5;9;14; 1;6;10;13;12;11;7;15 A uniform "gas".
A rule by Tim Tyler.
BounceGasII MS,D0;8;4;12;2;10;9; 7;1;6;5;11;3;13;14;15 Another uniform "gas".
A rule by Tim Tyler.
Critters MS,D15;14;13;3;11;5; 6;1;7;9;10;2;12;4;8;0 This rule supports "gliders" - as described in Cellular Automata Machines.
A rule by Margolus/Toffoli.
HPP_Gas MS,D0;8;4;12;2;10;9; 14;1;6;5;13;3;11;7;15 HPP (Hardy/Pazzis/Pomeau) lattice gas - as described in Cellular Automata Machines.
A rule by Hardy, Pazzis, and Pomeau.
Rotations MS,D0;2;8;12;1;10;9; 11;4;6;5;14;3;7;13;15 Limited diffusion.
A rule by Tim Tyler.
RotationsII MS,D0;2;8;12;1;10;9; 13;4;6;5;7;3;14;11;15 Limited diffusion.
A rule by Tim Tyler.
RotationsIII MS,D0;4;1;10;8;3;9;11; 2;6;12;14;5;7;13;15 Slow, random-looking diffusion.
A rule by Tim Tyler.
RotationsIV MS,D0;4;1;12;8;10;6;14; 2;9;5;13;3;11;7;15 Slow, random-looking diffusion.
A rule by Tim Tyler.
Sand MS,D0;4;8;12;4;12;12;13; 8;12;12;14;12;13;14;15 Sand simulation.
To get most of the rule use the "Diversities/Stream injection" to produce a steady stream of new cells.
A rule by Mirek Wojtowicz.
StringThing MS,D0;1;2;12;4;10;9;7;8; 6;5;11;3;13;14;15 String shaped patterns.
A rule by Tim Tyler.
StringThingII MS,D0;1;2;12;4;10;6;7;8; 9;5;11;3;13;14;15 More string shaped patterns.
A rule by Tim Tyler.
SwapOnDiag MS,D0;8;4;12;2;10;6;14; 1;9;5;13;3;11;7;15 A gas with no particle interactions - as described in Cellular Automata Machines.
A rule by Margolus/Toffoli.
Tron MS,D15;1;2;3;4;5;6;7;8; 9;10;11;12;13;14;0 A "trip-a-tron" - from the pages of Cellular Automata Machines.
A rule by Margolus/Toffoli.

 


Webmaster: Mirek Wójtowicz
envelope info@mirekw.com,
envelope mirwoj@life.pl
globe http://www.mirekw.com


MCell mirrors:
globe USA  http://psoup.math.wisc.edu/mcell/
globe Europe  http://www.mirwoj.opus.chelm.pl

Last update: 15 Sep 2001