Reversible Cellular Automata

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

Reversible Cellular Automata

Postby hyksos on February 10th, 2018, 1:04 am 

Reversible Cellular Automata

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 :

singlerotrule.png


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".
User avatar
hyksos
Active Member
 
Posts: 1094
Joined: 28 Nov 2014


Re: Reversible Cellular Automata

Postby someguy1 on February 10th, 2018, 4:36 pm 

Since reversible transformations give rise to groups, is this essentially group theory in disguise? The "single rotation rule" seems to be identical to the rotations of a square, which form a subgroup of the 4! = 24 element group of order 4 of the group of all possible permutations of a set of four elements.
someguy1
Member
 
Posts: 616
Joined: 08 Nov 2013



Return to Mathematics

Who is online

Users browsing this forum: No registered users and 5 guests