Reversible Cellular Automata

[christopherx]

Hey guys. I know this isn't strictly a Java question but this is one of the largest Comp Sci communities im aware of, and you guys tend to have good answers. I'm looking for a set of cellular automata rules that are the mathematical opposites. Essentially, if I took a grid of boolean values, and put it through one iteration of rule "F", Rule "G" would return the grid back to it's original value. I know they exist, or at least I've read that they exist. I'm just stuck on what rules compliment each other. Any help is greatly appreciated!!

[JosAH]

Hey guys. I know this isn't strictly a Java question but this is one of the largest Comp Sci communities im aware of, and you guys tend to have good answers. I'm looking for a set of cellular automata rules that are the mathematical opposites. Essentially, if I took a grid of boolean values, and put it through one iteration of rule "F", Rule "G" would return the grid back to it's original value. I know they exist, or at least I've read that they exist. I'm just stuck on what rules compliment each other. Any help is greatly appreciated!!

If a cellular automaton is defined as c_i = f(c_1, c_2, ... , c_n) then this function f( ... ) needs to be invertible, i.e. it needs to be a bijection; there are many of them; the two most simple functions as:
c_i= c_i and c_i= ~c_i (~ means the inverse). The domain needs to have the same size as the co-domain of the function f.
kind regards,

Jos

[christopherx]

Hey Jos, cheers for the answer. I'm stuck on some of the more mathematical terms :P What on earth is a Bijection?

I understand the domain of the seed needs to be the same for both of them, for them to be true mathematical inverses. Can you give me an example of two rules that compliment each other in this way?

Sincerely, Chris.

[JosAH]

A bijection is an invertible function; for examples of bijections see my previous reply; e.g. f(c) == c and f(c) == ~c are invertible functions (bijections).

kind regards,

Jos