Reversible CAs have a funny property. You can draw a starting eden state into the grid, and then run the simulation millions of cycles into the future. You can then stop the sim, reverse time , and run backwards in time. After millions of cycles, your original eden state is completely restored. You can 'draw' an eden state on a grid as a smiley face smoking a joint. Perform the process above, and the smiley face will be reformed exactly, even if it looked like random noise on the outbound states.

Try it here : https://dmishin.github.io/js-revca/index.html

Interesting enough in its own right.

Now let's consider the theoretical properties of reversible CA. A 2x2 block is called a Margoulis Neighborhood. During odd sim cycles, the neighborhood is shifted down and rightwards by 1 cell location. Then switched back again on even cycles. Encode the rule table such that Margoulises are stretched thin and encode a binary integer of 4 bits. You can then write out the transition rule as a so-called bijective substitution.

The single rotation rule in diagramatic form :

Single Rotation as a bijective substitution of 4 bit integers.

Single Rotation

- Code: Select all
`0 _ 0`

1 _ 8

2 _ 1

3 _ 3

4 _ 2

5 _ 5

6 _ 6

7 _ 7

8 _ 4

9 _ 9

10_ 10

11_ 11

12_ 12

13_ 13

14_ 14

15_ 15

Another way of stating the "single rotation" Rule, is to represent the number as bits. If the integer contains 1 and only 1 bit, rotate the bits clockwise one location. (or "shift right" for you programmers).

If there is no confusion about the position of the substitution, we can write the above substitution as a comma-separated string.

- Code: Select all
`0,8,1,3,2,5,6,7,4,9,10,11,12,13,14,15`

This is exactly how rules are defined in the applet linked above.

If the number of bits contained in an original number matches the number of bits in its substituted counterpart, then the rule is said to have the property of "Constant Population" . Necessarily, throughout the entire life of the simulation, a "Constant Population" rule will have a fixed number of yellow cells.

If the empty (zero) integer maps to an empty (zero) , the rule has the property called "stable vacuum".