Registered: Apr 2007
Posts: 2

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

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

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

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