8 views

Skip to first unread message

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

Search

Clear search

Close search

Google apps

Main menu