Registered: Oct 2003
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