A New Kind of Science: The NKS Forum > Pure NKS > Reversible rules of 3-states, page 1017
Author
 Thread
Guilherme Kronemberger
Mackenzie University
São Paulo - Brazil

Registered: Apr 2007
Posts: 2

Reversible rules of 3-states, page 1017

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?

__________________
Guilherme Kronemberger
Electronic Eng. - Brazil

Report this post to a moderator | IP: Logged

05-01-2007 10:04 PM
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 103

Attached are the 1800 rules.

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

Attachment: reversibleca3.nb
This has been downloaded 1252 time(s).

Report this post to a moderator | IP: Logged

05-02-2007 02:40 PM
Guilherme Kronemberger
Mackenzie University
São Paulo - Brazil

Registered: Apr 2007
Posts: 2

> 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.

__________________
Guilherme Kronemberger
Electronic Eng. - Brazil

Report this post to a moderator | IP: Logged

05-03-2007 06:42 PM
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 103

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.

Report this post to a moderator | IP: Logged

05-12-2007 03:35 AM

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-13 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives