## Reversible Cellular Automata

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

### Reversible Cellular Automata

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 :

Single Rotation as a bijective substitution of 4 bit integers.

Single Rotation
Code: Select all
`0 _  01 _  82 _  13 _  34 _  25 _  56 _  6 7 _  78 _  49 _  910_ 10 11_ 1112_ 1213_ 1314_ 1415_ 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".

hyksos
Active Member

Posts: 1563
Joined: 28 Nov 2014

### Re: Reversible Cellular Automata

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: 739
Joined: 08 Nov 2013

### Re: Reversible Cellular Automata

Hyksos has not replied in two weeks.

Hyksos has a history of posting topics which present as questions in advanced mathematics, to which the average member of this forum is unable (or unwilling) to respond. Two hypotheses present: either Hyksos' posts are gobbledegook, or they are too abstruse for the average forum member. Two possible scenarios correspond to these hypotheses: Hyksos is an average mathematician with an unusual gift for satire, or, Hyksos is really a gifted mathematician with a self-confidence problem.

So which is it, Hyksos? I'm in the happy position of not being a mathematician - I failed high school mathematics with the lowest achievable grade - I'm an outsider. So I feel no embarrassment at all in asking the question.
Alan Masterman
Member

Posts: 52
Joined: 04 Mar 2012

### Re: Reversible Cellular Automata

Hello Alan Masterman.

Alan has discovered that I have posted problems on this forum that are from recreational mathematics. He also noticed no regulars here have attempted to respond to them. A short laundry list of my threads :

(1) viewtopic.php?f=19&t=32670

(2) viewtopic.php?f=19&t=32893

(3) viewtopic.php?f=19&t=32894

(4) viewtopic.php?f=19&t=32552

I don't mind the lack of responses, as there was a bomb problem that received enormous attention. Here : viewtopic.php?f=19&t=32647

I provided two zany solutions to the bomb problem -- meaning your needle should be moving away from "average" and tiling towards "gifted".

hyksos
Active Member

Posts: 1563
Joined: 28 Nov 2014

### Re: Reversible Cellular Automata

someguy1 » February 11th, 2018, 12:36 am wrote: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.

Because of reversibility, all grid states at all times t, are unique. The entire grid , (and all its states at time t) form a group. This is true no matter how large the grid under consideration becomes.

Corollary : With enough forward time, the grid must eventually return to its original eden state.

With deep future time, the original eden state of the grid will recur at fixed period lengths. (Though a single period is astronomically long.)

hyksos
Active Member

Posts: 1563
Joined: 28 Nov 2014