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


Re: Reversible Cellular Automata

Postby Alan Masterman on February 25th, 2018, 8:08 am 

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

Postby hyksos on February 25th, 2018, 5:06 pm 

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


Re: Reversible Cellular Automata

Postby hyksos on February 25th, 2018, 6:02 pm 

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



Return to Mathematics

Who is online

Users browsing this forum: No registered users and 2 guests