[Reversible rules of 3-states, page 1017] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Reversible rules of 3-states, page 1017

(Click here to view the original thread with full colors/images)


Posted by: Guilherme Kronemberger

On page 1017 it says:
"for k=3, r=1 there are 1800 reversible rules, in 172 families"

Which are these 1800 rules? Can someone pass me a notebook with the numbers of this rules?

And about the families: given a rule number, is there a simple way to tell what are the others rules from that familie?


Posted by: Todd Rowland

Attached are the 1800 rules.

Some of these are quite interesting and deserve in depth investigation.


Posted by: Guilherme Kronemberger

> Attached are the 1800 rules.
>
> Some of these are quite interesting and deserve in depth
> investigation.

Many thanks, Todd.

But let me ask you just a question: did you get them from sieving the entire k=3_r=1 space, or from actually constructing them somehow? If it was the latter, would you please let us know how.

Thanks once again.


Posted by: Todd Rowland

That data was generated by Stephen Wolfram for his work for a NKS. We can try to figure out more details of how it was created at the summer school.

But it is not so hard to see how one can use symmetries to reduce the search.

For instance, a reversible CA is reversible on any finite sized initial condition. From size 1, one step is a permutation on the colors. For three colors, there are 6 possibilities (compared to the 3^3 possible maps). From size 2, there are 3 unequal pairs, and so 3! permutations, and with each permutation there are 2 possible reversible CA partial rules in each case. For size 3, there are 24 unequal triples (equivalent as elements in the group action induced by translation), each representing 8 orbits. A reversible CA induces a permutation of these orbits, and for each such permutation there are 3^8 shift invariant maps.

Considering the size 1 and the unequal size 3 cases, we recover a CA rule. So there are Times[6,8!,3^8] cases to consider. This can be reduced further since among the permutations of three colors, there are only 3 kinds which can be considered separately.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings