reversible (3,1) cellular automata

8 views
Skip to first unread message

McIntosh Harold V.-UAP

unread,
Sep 23, 1997, 3:00:00 AM9/23/97
to c...@think.com

A little over two years ago I posted a list of 48 clusters of (3,1)
[trinary, first neighbor] cellular automaton rules which were also
reversible via (3,1) rules. It was left open whether there were other
automata which required longer neighborhoods for their reversal.

By a cluster is meant the equivalence class arising from reflecting
the rule, and independently permuting the cell states and the value
of the evolved state. Thus a cluster for a (k,r) automaton could
encompass as many as 2(k!)^2 rules; fewer in the case of symmetries.
When a rule is reversible, so is the entire cluster.

The rule numbers below are reported in Wolfram's notation, but in
base 27 so as to shorten the number of "digits" which have to be
written. Think of hexadecimal, with digits 0-9, A-Q. The number
given is the least of its cluster, but somewhat more visually
interesting rules result if permutations are made to make the
rule totally quiescent.

It would seem that if (3,2) rules are considered - that is, those
with five-cell neighborhoods - there are 52 new reversible rule
clusters. Since any reversing rule can be embedded in a longer
neighborhood, redundancy was avoided by excluding the (3,1) rules
already found; but it is possible that some of the new rules could
have been found amongst (3,3/2) rules, which were not scanned.

Whilst (3,1) reversibles tend to be rules where all configurations
have period 2; shifting rules often require longer reversing
neighborhoods because of centering conventions, and show up more
often in the new list.

Here are the additional clusters:

suniq, l = 343: (cluster) 000DQQQDD (rule) 000DQQQDD
suniq, l = 281: (cluster) 000QDDDQQ (rule) JBJJBJJBJ
suniq, l = 534: (cluster) 0DQ0DQD68 (rule) 1CO1EQ1CQ
suniq, l = 168: (cluster) 0DQ0DQM0N (rule) C3QDQ0DQ0
suniq, l = 323: (cluster) 0DQ0HM0QD (rule) 2OD0QDQ0D
suniq, l = 444: (cluster) 0DQ0QD0HM (rule) DQ0DI8D0Q
suniq, l = 317: (cluster) 0DQ0QDI8D (rule) 0QD1QCQ0D
suniq, l = 171: (cluster) 0DQ1CQ1LH (rule) D6K4Q9DQ0
suniq, l = 602: (cluster) 0DQ1CQC1Q (rule) 0DQ1CQC1Q
suniq, l = 179: (cluster) 0DQ1CQD0Q (rule) D6KD8ID8I
suniq, l = 363: (cluster) 0DQ1QA1QA (rule) 0HM0HI4HM
suniq, l = 186: (cluster) 0DQ2DOA3Q (rule) AQ3BP3DQ0
suniq, l = 263: (cluster) 0DQ2DOD0Q (rule) N0GN97N0G
suniq, l = 545: (cluster) 0DQ6MB6DK (rule) 0DQ6MB6DK
suniq, l = 412: (cluster) 0DQ6OD6OD (rule) C9QQ0DC9Q
suniq, l = 488: (cluster) 0DQ9Q40QD (rule) D0QE0P0DQ
suniq, l = 554: (cluster) 0DQHE00DQ (rule) 0DQQ410DQ
suniq, l = 142: (cluster) 0DQKD66DK (rule) DQ0EP0PE0
suniq, l = 549: (cluster) 0DQQD03AQ (rule) 0DQQD03AQ
suniq, l = 117: (cluster) 0DQQD06DK (rule) EP0DQ0QD0
suniq, l = 137: (cluster) 0EHQD00EH (rule) D86D86QD0
suniq, l = 176: (cluster) 0EP0DQD0Q (rule) A8LD8ID8I
suniq, l = 233: (cluster) 0EP0MH0MH (rule) Q0DO2D2OD
suniq, l = 395: (cluster) 0EP0QDI8D (rule) 2FM0HM0QD
suniq, l = 364: (cluster) 0GH0HGH0G (rule) 3HJ08IDHM
suniq, l = 423: (cluster) 0GN9Q40QD (rule) D6KH0MD0Q
suniq, l = 608: (cluster) 0HEHE00EH (rule) 0HEHE00EH
suniq, l = 244: (cluster) 0HM04HIMH (rule) K0GG0NN3G
suniq, l = 491: (cluster) 0HM08M9HM (rule) D0QD0Q0GH
suniq, l = 588: (cluster) 0HM9MH0M8 (rule) 1CQ1CQL1N
suniq, l = 320: (cluster) 0HMIHM0H4 (rule) 2OC2PD2OD
suniq, l = 374: (cluster) 0MH08M9HM (rule) 3QAA853QA
suniq, l = 372: (cluster) 0MH0HM0QD (rule) 0QDAQ33QA
suniq, l = 201: (cluster) 0MH0M98MH (rule) EH00QDEH0
suniq, l = 470: (cluster) 0MH0QD0HM (rule) C1QD0Q1CQ
suniq, l = 247: (cluster) 0MH4MH0IH (rule) OIDD0QOID
suniq, l = 370: (cluster) 0MHIHM0H4 (rule) 3QAJP33QA
suniq, l = 312: (cluster) 0MPMP00PM (rule) 3Q44Q3Q34
suniq, l = 268: (cluster) 0NG0MH0MH (rule) N0GM0HN0G
suniq, l = 107: (cluster) 0NM0MNM0N (rule) GQNA8LA03
suniq, l = 270: (cluster) 0Q0DDDQ0Q (rule) QQQD000DD
suniq, l = 564: (cluster) 1C0PEQ7CK (rule) 6MB049QMH
suniq, l = 229: (cluster) 3DKKD66GK (rule) K4BQ94Q94
suniq, l = 98: (cluster) JLLJLLJLL (rule) L5LL5LL5L
suniq, l = 85: (cluster) K4FQ49Q49 (rule) QD0OD2DQ0
suniq, l = 33: (cluster) K4FQD0Q49 (rule) Q1CQD0HM0
suniq, l = 51: (cluster) K4FQMH049 (rule) O6D6DOOD6
suniq, l = 74: (cluster) KD60DQQD0 (rule) PE0QD0DQ0
suniq, l = 27: (cluster) KD66DKQD0 (rule) KD68DIKD6
suniq, l = 14: (cluster) KD66MJKD6 (rule) PE2PC0EP0
suniq, l = 90: (cluster) KDGKD6K36 (rule) KDIKDIDQ0
suniq, l = 65: (cluster) KG6KD6KD3 (rule) KG6KD6KD3


Reply all
Reply to author
Forward
0 new messages