Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem Claudio Martins Pedro de Oliveira Universidade Presbiteriana Mackenzie São

Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem

Claudio MartinsPedro de Oliveira

Universidade Presbiteriana MackenzieSão Paulo, SP

Brazil

AUTOMATA 2015

Turku - Finland

1. The Modulo-n Problem in Cellular Automata

3

• Definition 1: The MODn ProblemIt consists of determining whether the number of 1-bits in a

cyclic binary string is multiple of n or not.

Definitions

• Example 1: Solution for the MOD2 Problem

• Example 2: Solution for the MOD3 Problem

MOD2

>>>

>>>

Initial Configuration Final Configuration

MOD3

>>>

>>>

>>>



4

• MOD2 (ill-defined Problem)

Examples of ill-defined problem

• MOD3 (ill-defined Problem)

It is always ill-defined for lattice sizes multiple of n !

MOD2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

>>>


MOD3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

>>>



5

• Definition 2: Rule Composition (temporal sequences of Rules)

Definitions

Solution for the MOD2 Problem [Lee, Xu and Chau, 2001]

’ = S() =

2

22222132

NNN

RR

Solution for the MOD3 Problem [Lee, Xu and Chau, 2003]

’ = S() = NN

NN

NN

NN RRRRE

33254 1324

Rjaj … R3

a3 R2a2 R1

a1

• Examples

2. The Partition of a Binary String

7

Definitions

• Definition 3: The Partition number The number of groups of 0s that is equal to the number of groups of 1s (because of the periodic boundary condition).

Partition

3

0

0

1

Configuration

3. Active State Transition

8

Definitions

• Definition 4: Active State Transition By active transition, we mean those that change the state value of the cell at the centre of the neighbourhood.

TransitionOutput

bit7 1 1 1 16 1 1 0 15 1 0 1 14 1 0 0 03 0 1 1 12 0 1 0 11 0 0 1 10 0 0 0 0

Rule 238

Neighbourhood

23810 = 111011102

4. The Replacement Rules (R)

9

Definition

• A rule that can replace n end bits, of a sequence of n or more consecutive identical bits, with n opposite bits.

Left end bits Right end bits

1 2 3 ... n -2 n -1 n .... n n -1 n -2 ... 3 2 1

↓ ↓ ↓ ↓ ↓ ↓ ↓....

↓ ↓ ↓ ↓ ↓ ↓ ↓....

↓ ↓ ↓ ↓ ↓ ↓ ↓....

....

....↓ ↓ ↓ ↓ ↓ ↓ ↓

....

↓ ↓ ↓ ↓ ↓ ↓ ↓....

↓ ↓ ↓ ↓ ↓ ↓ ↓....


10

Representation

0nR

1nR• to replace n 0s with n 1s, and to the opposite.

00,nR

01,1nR

02,2nR

0,0 nR• or require radius n.

• or … or … or require radius n-1.02,2 nR 0

1,1 nR

• MODn-conserving rules.

1 2 3 .... .... 3 2 1 1 2 3 .... .... 3 2 1↓ ↓ ↓ ↓ ↓ ↓

.... .... .... ....

1 2 3 .... .... 3 2 1 1 2 3 .... .... 3 2 1↓ ↓ ↓ ↓ ↓ ↓

.... .... .... ....

03R

00,3R

01,2R

03,0R

02,1R


11

Observations

Transition31 1 1 1 1 1 130 1 1 1 1 0 129 1 1 1 0 1 128 1 1 1 0 0 127 1 1 0 1 1 026 1 1 0 1 0 025 1 1 0 0 1 024 1 1 0 0 0 1 1st 0 from the left23 1 0 1 1 1 122 1 0 1 1 0 121 1 0 1 0 1 120 1 0 1 0 0 119 1 0 0 1 1 018 1 0 0 1 0 017 1 0 0 0 1 1 2nd 0 from the left16 1 0 0 0 0 1 2nd 0 from the left15 0 1 1 1 1 114 0 1 1 1 0 113 0 1 1 0 1 112 0 1 1 0 0 111 0 1 0 1 1 010 0 1 0 1 0 09 0 1 0 0 1 08 0 1 0 0 0 1 1st 0 from the left7 0 0 1 1 1 16 0 0 1 1 0 15 0 0 1 0 1 14 0 0 1 0 0 13 0 0 0 1 1 1 1st 0 from the right2 0 0 0 1 0 1 1st 0 from the right1 0 0 0 0 1 00 0 0 0 0 0 0

Rule 4.059.296.252

Neighbourhood Output bit / Note

01,2R ↓ ↓

1 0 0 0 .... 0 0 0 1 1 0 0 0 .... 0 0 0 1

Radius

↓ ↓1 0 0 0 .... 0 0 0 1 1 0 0 0 .... 0 0 0 1

Radius

↓ ↓1 0 0 0 .... 0 0 0 1 1 0 0 0 .... 0 0 0 1

Radius =3 =3 =0 =0

=1 =2 =2 =1

=2 =1 =1 =2

24 & 8 * 1 0 0 0 1 1st 0 from the left17 & 16 1 0 0 0 * 1 2nd 0 from the left

3 & 2 0 0 0 1 * 1 1st 0 from the right

ActiveTransitions


Rule 4.059.296.252 01,2R

24 1 1 0 0 0 1 1st 0 from the left17 1 0 0 0 1 1 2nd 0 from the left16 1 0 0 0 0 1 2nd 0 from the left8 0 1 0 0 0 1 1st 0 from the left3 0 0 0 1 1 1 1st 0 from the right2 0 0 0 1 0 1 1st 0 from the right

ActiveTransition


Simplified Representation


12

Observations

Partition

1 2 3 4 5 6 7 8 9 10 11 12

t0 2t1 2t2 1t3 1

Appying on the Configuration01,2R

• The Partition can be reduced.

• There is no effect without n or more consecutive identical bits, or on a string with only 0s or only 1s.

Partition

1 2 3 4 5 6 7 8 9 10 11 12

t0 3t1 3t2 3t3 3

Appying on the Configuration01,2R

5. The Grouping Rules (G)

13

Definition and Representation

• A rule that can shift, to the left or to the right, strings of m bits (10m1 or 01m0), in order to group them with larger strings of the bit at concern.

1 2 3 .... m 1 2 3 .... m↓ ↓ ↓ ↓1 2 3 .... m 1 2 3 .... m

1 2 3 .... m 1 2 3 .... m↓ ↓ ↓ ↓1 2 3 .... m 1 2 3 .... m

1 0 0 0 1 1 0 0 0 1↓ ↓ ↓ ↓

0 0 0 1 1 1 1 0 0 0

1 0 0 0 0 1 1 0 0 0 0 1↓ ↓ ↓ ↓0 0 0 0 1 1 1 1 0 0 0 0

0mG�

0mG

1mG�

1mG

03G�

04G�

03G

04G


14

• or require radius m+1.0mG

1mG

• MODn-conserving rules.

↓ ↓

1 0 0 0 1 1 0 0 0 1

Radius

↓ ↓

1 0 0 0 0 1 1 0 0 0 0 1

Radius

= 0 = 4 = 1 = 3

= 0 = 1 = 5 = 4

03G�

04G�

Observations

• There is no effect without m consecutive identical bits, or on a string with only 0s or only 1s.


15

Observations

• The Partition can be reduced.

• They can cause only Shifts on the lattice (only identical blocks).

Partition

1 2 3 4 5 6 7 8 9 10 11 12

t0 3t1 3t2 2t3 2

Appying on the Configuration01G�

Partition

1 2 3 4 5 6 7 8 9 10 11 12

t0 3t1 3t2 3t3 3

Appying on the Configuration01G�


16

Observations

Transition31 1 1 1 1 1 130 1 1 1 1 0 129 1 1 1 0 1 0 1 on the left28 1 1 1 0 0 127 1 1 0 1 1 1 Isolated 026 1 1 0 1 0 1 Isolated 025 1 1 0 0 1 024 1 1 0 0 0 023 1 0 1 1 1 122 1 0 1 1 0 121 1 0 1 0 1 0 1 on the left20 1 0 1 0 0 119 1 0 0 1 1 018 1 0 0 1 0 017 1 0 0 0 1 016 1 0 0 0 0 015 0 1 1 1 1 114 0 1 1 1 0 113 0 1 1 0 1 0 1 on the left12 0 1 1 0 0 111 0 1 0 1 1 1 Isolated 010 0 1 0 1 0 1 Isolated 09 0 1 0 0 1 08 0 1 0 0 0 07 0 0 1 1 1 16 0 0 1 1 0 15 0 0 1 0 1 0 1 on the left4 0 0 1 0 0 13 0 0 0 1 1 02 0 0 0 1 0 01 0 0 0 0 1 00 0 0 0 0 0 0

Rule 3.704.675.536


01G�

Simplified Representation

29 1 1 1 0 1 0 1 on the left27 1 1 0 1 1 1 Isolated 026 1 1 0 1 0 1 Isolated 021 1 0 1 0 1 0 1 on the left13 0 1 1 0 1 0 1 on the left11 0 1 0 1 1 1 Isolated 010 0 1 0 1 0 1 Isolated 05 0 0 1 0 1 0 1 on the left

ActiveTransition


Rule 3.704.675.536 01G�

27, 26, 11 & 10 * 1 0 1 * 1 Isolated 029, 21, 13 & 5 * * 1 0 1 0 1 on the left

Output bit / NoteActive

TransitionsNeighbourhood

↓ ↓

1 0 1 1 0 1

Radius = 1= 2 = 1 = 0

01G�

6. Composing Replacement and Grouping Rules

18

• The correct temporal composition of the Replacement and the Grouping rules is:

The Correct Sequence of the Rules

n

N

n

NNN

n

NNN

nnnn RGGRGG 001...0

211

1...12

2222’ = S() =

n

N

n

NNN

n

NNN

nnnn RGGRGG 111...1

200

1...02

2222’ = S() =

or

• n-2 rules and n-2 rules are necessary. 0mG

1mG


21

• Necklaces are configurations of the form (0A1B)C : for positive integers A, B and C, where A < n and B < n, or A < n and B > n, but B is not multiple of n, or B < n and A > n, but A is not multiple of n, or B > n and A > n, but A and B are not multiple of n.

Necklace Configurations

• For Necklaces Grouping rules just cause Shifts on the lattice (only identical

blocks). Replacement rules cause no effect when A < n and B < n,

or may lead to periodic regimes (resulting Shifts) only when A > n or B > n, by continuously transforming (0A1B )C into (0A’1B’ )C, back and forth.


22

Necklace Configurations

• Example 2: A Replacement rule for the MOD4 Problem

(0712)2 (0316)2

• Example 1: A Replacement rule for the MOD3 Problem

(0711)2(0414)2(0117)2

Necklacet 0 (0711)2

t 1 (0414)2

t 2 (0117)2

t 3 (0117)2

t 4 (0414)2

t 5 (0711)2

t 6 (0711)2

t 7 (0414)2

t 8 (0117)2

t 9 (0117)2

t 10 (0414)2

t 11 (0711)2

t 12 (0711)2

InitialConfiguration

01,2R

11,2R

01,2R

11,2R

Necklacet 0 (0712)2

t 1 (0316)2

t 2 (0316)2

t 3 (0316)2

t 4 (0712)2

t 5 (0712)2

t 6 (0712)2

t 7 (0316)2

t 8 (0316)2

t 9 (0316)2

t 10 (0712)2

t 11 (0712)2

t 12 (0712)2

InitialConfiguration

01,3R

11,3R

01,3R

11,3R


23

• Let ’ = ,

What these compositions may cause in the lattice?

• Then ’ will be one of the following: 0N (Partition = 0); 1N (Partition = 0);

n

N

n

N

n

N

nNN

nnNN

n RGGRGG 001...0

211

1...12

0N-MODn(||1)1MODn(||1), (Partition = 1); ||1 is the quantity of 1-bits inside string N-MODn(||1) ≠ multiple of nMODn(||1) ≠ 0

Necklaces (0A1B )C, (Partition > 1).C > 1, B < n, A ≠ multiple of n, and (A+B)C = N.


26

Final Configurations for Lattice Size Not Multiple of N or Not Multiple of Any Factor of n

If MODn(N) = MODn(||1):

MODn(||1) ≠ 0: ’ = 1N

If MODn(N) ≠ MODn(||1):

MODn(||1) = 0: ’ = 0N

MODn(||1) ≠ 0: ’ = 0N-MODn(||1)1MODn(||1) or ’ =(0A1B)C (necklaces)

• For all initial configurations: When MODn(||1) = 0, the problem is solved, as defined. However, in order for all the other initial configurations to

lead to 1N, elementary rule 254 can be used.

7. The Modulo-n Problem Solution

27

The Generic Solution

• The generalisation of the solution for MODn finally leads to:

Sn =

n

N

n

NNN

n

NNNN

nnnn RGGRGGE 001...0

211

1...12

22222254

• 2 Replacement rules, and (radius n-1)0nR

1nR

0mG

1mG

01G

11G

02G

12G

02nG

12nG

• All these rules may have radius n-1.

• n-2 Grouping rules, and

• and shift isolated bits (radius 2)

• and shift isolated pair of bits (radius 3)

• and so on, up to • and shift isolated strings of n-2 bits (radius n-1)

8. The Merging Operation

28

• What happens when we separate the active transitions of a rule or simply join active transitions of some rules in a single one?

Joining and Separating the Active State Transitions

TransitionOutput

bitOutput

bitOutput

bit7 1 1 1 1 1 1 1 1 1 1 1 16 1 1 0 1 1 1 0 1 1 1 0 15 1 0 1 1 + 1 0 1 1 = 1 0 1 1 ?4 1 0 0 0 1 0 0 1 1 0 0 13 0 1 1 1 0 1 1 1 0 1 1 12 0 1 0 1 0 1 0 1 0 1 0 11 0 0 1 1 0 0 1 0 0 0 1 10 0 0 0 0 0 0 0 0 0 0 0 0

Rule 238 Rule 252 Rule 254

Neighbourhood Neighbourhood Neighbourhood

t 0t 1t 2t 3t 4t 5t 6t 7t 8t 9

t 10t 11t 12

(R252 R238)N/2 (R238

R252)N/2 R254NR252

N/2 R238N/2 R238

N/2 R252N/2


29

• Of course it will not always work!

Decomposing the Active State Transitions of the Elementary Inverting Rule

TransitionOutput

bitOutput

bitOutput

bitOutput

bitOutput

bit7 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 16 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 15 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 04 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 13 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 12 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 00 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

TransitionOutput

bitOutput

bitOutput

bitOutput

bit7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 15 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 04 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 03 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 12 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 11 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Rule 196 Rule 200 Rule 206 Rule 205

Neighbourhood Neighbourhood Neighbourhood Neighbourhood

Rule 51 Rule 76 Rule 140 Rule 236 Rule 220

Neighbourhood Neighbourhood Neighbourhood Neighbourhood Neighbourhood


30

• Even the ordering of these rules can change the final result!

Decomposing the Active State Transitions of the Elementary Inverting Rule

t 0t 1t 2t 3t 4t 5t 6t 7t 8t 9

t 10t 11t 12t 13t 14t 15t 16

E 5116 (E205 E206 E200 E196 E220 E236 E140 E76)16 (E76 E206 E200 E196 E220 E236 E140 E205)16

9. Merging Replacement with Grouping Rules

31

• How about merging Replacement and Grouping rules?

The MOD3 Case

Transition Transition31 1 1 1 1 1 1 31 1 1 1 1 1 130 1 1 1 1 0 1 30 1 1 1 1 0 129 1 1 1 0 1 1 29 1 1 1 0 1 0 1 on the left28 1 1 1 0 0 1 28 1 1 1 0 0 127 1 1 0 1 1 0 27 1 1 0 1 1 1 Isolated 026 1 1 0 1 0 0 26 1 1 0 1 0 1 Isolated 025 1 1 0 0 1 0 25 1 1 0 0 1 024 1 1 0 0 0 1 1st 0 from the left 24 1 1 0 0 0 023 1 0 1 1 1 1 23 1 0 1 1 1 122 1 0 1 1 0 1 22 1 0 1 1 0 121 1 0 1 0 1 1 21 1 0 1 0 1 0 1 on the left20 1 0 1 0 0 1 20 1 0 1 0 0 119 1 0 0 1 1 0 19 1 0 0 1 1 018 1 0 0 1 0 0 18 1 0 0 1 0 017 1 0 0 0 1 1 2nd 0 from the left 17 1 0 0 0 1 016 1 0 0 0 0 1 2nd 0 from the left 16 1 0 0 0 0 015 0 1 1 1 1 1 15 0 1 1 1 1 114 0 1 1 1 0 1 14 0 1 1 1 0 113 0 1 1 0 1 1 13 0 1 1 0 1 0 1 on the left12 0 1 1 0 0 1 12 0 1 1 0 0 111 0 1 0 1 1 0 11 0 1 0 1 1 1 Isolated 010 0 1 0 1 0 0 10 0 1 0 1 0 1 Isolated 09 0 1 0 0 1 0 9 0 1 0 0 1 08 0 1 0 0 0 1 1st 0 from the left 8 0 1 0 0 0 07 0 0 1 1 1 1 7 0 0 1 1 1 16 0 0 1 1 0 1 6 0 0 1 1 0 15 0 0 1 0 1 1 5 0 0 1 0 1 0 1 on the left4 0 0 1 0 0 1 4 0 0 1 0 0 13 0 0 0 1 1 1 1st 0 from the right 3 0 0 0 1 1 02 0 0 0 1 0 1 1st 0 from the right 2 0 0 0 1 0 01 0 0 0 0 1 0 1 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0

Rule 4.059.296.252 Rule 3.704.675.536

Neighbourhood Output bit / Note Neighbourhood Output bit / Note

01G�

01,2R

24 1 1 0 0 0 1 1st 0 from the left17 1 0 0 0 1 1 2nd 0 from the left16 1 0 0 0 0 1 2nd 0 from the left8 0 1 0 0 0 1 1st 0 from the left3 0 0 0 1 1 1 1st 0 from the right2 0 0 0 1 0 1 1st 0 from the right


3 & 2 0 0 0 1 * 1 1st 0 from the right

ActiveTransitions


ActiveTransition


Rule 4.059.296.252 01,2R

29 1 1 1 0 1 0 1 on the left27 1 1 0 1 1 1 Isolated 026 1 1 0 1 0 1 Isolated 021 1 0 1 0 1 0 1 on the left13 0 1 1 0 1 0 1 on the left11 0 1 0 1 1 1 Isolated 010 0 1 0 1 0 1 Isolated 05 0 0 1 0 1 0 1 on the left


ActiveTransitions


ActiveTransition


Rule 3.704.675.536 01G�


32

• Replacement rule and the Grouping rule have different active state transitions.

The MOD3 Case

• Merging these two rules, and , results the rule .

01,2R

01G�

01,2R

01G�

01,2M

�

• Can these 3 alternatives perform the same tasks?

NNNRG

01,2

01

� NNNGR

01

01,2

� NNM

01,2

� , , or

ActiveTransitions



3 & 2 0 0 0 1 * 1 1st 0 from the right


Rule 3.721.649.628 01,2M

�


33

The MOD3 Case

t 0t 1t 2t 3t 4t 5t 6t 7t 8t 9

t 10t 11t 12t 13t 14t 15t 16t 17t 18t 19t 20t 21t 22t 23t 24t 25t 26t 27t 28t 29t 30t 31t 32t 33t 34t 35t 36t 37t 38t 39t 40t 41t 42t 43t 44t 45t 46t 47t 48t 49t 50t 51t 52

21301,2

1301

RG

� 21301

1301,2

GR� 213

01,2

M�


34

• From a superficial analysis, we would say no!

The MOD3 Case

• But, going back to the initial goals, these three alternatives transform the lattice into a final configuration as desired.

• All final configurations have at most two consecutive 0s, and there are no isolated 0s and isolated pairs of 0s occurring

simultaneously.


35

• Applying : rule instead of and , and rule instead of and , the solution S3 is simplified to Ss3 :

The MOD3 Case

03M 1

3M13R

11G

03R

01G

S3 =

332322 0

301

13

11254

NNNNNN

RGRGE

Ss3 =

32 0

313254

NN NN

MME


36

• Comparing S3’ and Ss3’

The MOD3 Case

Amountof 1s

Final Configuration with some Necklaces

No. OfConfigs.

Amountof 1s

Final Configuration with some Necklaces

No. OfConfigs.

Amountof 1s

Final Configuration with some Partial Necklaces

No. OfConfigs.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21845 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 218450 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 19232 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 14576 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 47680 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 2608 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 656 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1568

0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1440 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 640 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 64

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 40 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2

16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 21845 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2184565536

Original Sequence S3' Simplified Sequence Ss3'

2 2 2

5

8 8

TOTAL TOTAL 65536

• Summary of all final configurations left, after applying these two solutions to all possible initial configurations with N=16.

33232 0

301

13

11

NNNNN

RGRG

303

13

N

NNMMS3’ = Ss3’ =


37

The MOD3 Case – Partial Necklaces

• The lattice “gets locked” on these configurations when the partial simplified solution is applied.

• Partial Necklaces in the MOD3 Problem, are configurations of the form ((03)+(01)+ )+ or ((13)+(10)+ )+.

0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1

0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1

Necklace= (01)3= 03 = 03= 01 = 01

= (03)2 = (01)5

Necklace

Necklace


38

The MOD3 Case – Partial NecklacesS'3 in 0000000101010101 S'3 in 0000100001010101 Ss'3 in 0000000101010101 Ss'3 in 0000100001010101

(0301)2(01)3 <<>> (1310)2(10)306(01)5 <<>> 16(10)5


39

Merging Rules Results ?

The MOD4 Case

04M14M

14R

11G

04R

01G

02G

12G

• The first problem is related to the Grouping rules ( and ) because of possible shifts of isolated 0s and isolated pairs of 0s simultaneously.

01G

02G

• Next figure shows the joining of these rules and also the temporal evolution of an initial configuration where the problem occurs.

+ + =

+ + =


40

The MOD4 Case and the Problem of Shifts

Output bit112 80 48 16 * * 1 0 0 0 0 197 96 33 32 * 1 0 0 0 0 * 17 6 5 4 0 0 0 0 1 * * 1

67 66 3 2 * 0 0 0 0 1 * 1123 122 107 106 91 90 75 74 59 58 43 42 27 26 11 10 * * * 1 0 1 * 0119 118 117 116 87 86 85 84 55 54 53 52 23 22 21 20 * * 1 0 1 * * 1121 105 89 73 57 41 25 9 * * * 1 0 0 1 0103 102 101 100 39 38 37 36 * 1 0 0 1 * * 1

+ + = Rule 321600197915107966665688126986998903292

Active State Transitions Neighbourhood

02,2R

01G�

02G�

02,2R 0

1G�

02G�

7

t 0t 1t 2t 3t 4t 5t 6t 7t 8t 9

t 10t 11t 12t 13 t 14t 15t 16t 17

302,2

701

702 RGG��

0

201

02,2 GGR

��


41

• A solution is to change the displacement step of rule .

Removing and Inserting Active Transitions to Change the Displacement Step of the Rule

01G�

• Instead moving just 1 position, move 2 positions, whenever possible.

• The new rule with this feature: . 2,01G�

Output bit119 118 117 116 87 86 85 84 55 54 53 52 23 22 21 20 * * 1 0 1 * * 1123 122 107 106 91 90 75 74 59 58 43 42 27 26 11 10 * * * 1 0 1 * 0

Output bit119 118 117 116 87 86 85 84 55 54 53 52 23 22 21 20 * * 1 0 1 * * 1

107 106 75 74 43 42 11 10 * * 0 1 0 1 * 0125 109 93 77 61 45 29 13 * * * 1 1 0 1 0

= Rule 324253482922812750238312970506082513664

TA's Neighbourhood

= Rule 297668273963817264613187722719825810176


2,01G�

01G�


42

• Finally, the second problem: a simultaneous shift of a single bit and its respective pair of bits will continue to occur when there is a string as *100101*.

Removing Active State Transitions to Eliminate Remaining Shifts

• Some active state transitions should be turned off.

1 0 0 1 0 1 1 0 0 1 0 1↓ ↓ ↓ ↓ ↓ ↓

0 0 1 0 1 1 0 0 0 1 1 1

INSTEAD BETTER

• Rules and become and . 2,01G�

02G�

2,0*1G

�0*2G

�


43


• For clarity purposes, notice that: String **0101* has been instantiated into strings

000101*, 010101*, 100101*, 110101*, and String *1001** into *100100, *100101, *100110, *100111.

Output bit119 118 117 116 87 86 85 84 55 54 53 52 23 22 21 20 * * 1 0 1 * * 1

11 10 0 0 0 1 0 1 * 043 42 0 1 0 1 0 1 * 0

75 74 1 0 0 1 0 1 * 1107 106 1 1 0 1 0 1 * 0

125 109 93 77 61 45 29 13 * * * 1 1 0 1 0

Output bit121 105 89 73 57 41 25 9 * * * 1 0 0 1 0103 39 * 1 0 0 1 1 1 1

102 38 * 1 0 0 1 1 0 1101 37 * 1 0 0 1 0 1 0

100 36 * 1 0 0 1 0 0 1

= Rule 336299833476273345402472786266733739264


= Rule 297668273963817264613187722719825810176Active State Transitions Neighbourhood

2,01G�

02G�


44

• The same rationale leads us to rule , composed by , , and .


2,1*1G

�1*2G

�

Output bit

112 80 48 16 * * 1 0 0 0 0 197 96 33 32 * 1 0 0 0 0 * 17 6 5 4 0 0 0 0 1 * * 1

67 66 3 2 * 0 0 0 0 1 * 1

119 118 117 116 87 86 85 84 55 54 53 52 23 22 21 20 * * 1 0 1 * * 111 10 0 0 0 1 0 1 * 0

43 42 0 1 0 1 0 1 * 0107 106 1 1 0 1 0 1 * 0

125 109 93 77 61 45 29 13 * * * 1 1 0 1 0

121 105 89 73 57 41 25 9 * * * 1 0 0 1 0103 39 * 1 0 0 1 1 1 1

102 38 * 1 0 0 1 1 0 1100 36 * 1 0 0 1 0 0 1

= Rule 295014986420811337252501870505639399932


0*2

2,0*1

02,2

02,2 GGRM

��

12,2R

12,2M

�

• Wolfram number: 255816358659918533639648036274123862084

10. The Modulo-n Problem Simplified Solution

45

• Testing the same procedure for MOD5 and obtaining similar results, we conclude that the simplified solution that can solve the MODn problem is :

The Generic Simplified Solution

Ss4 =

42 0

414254

NN NN

MME

Ssn =

n

NN N

nNn MME 012

254

• The solution S4 is simplified to Ss4 :

• It has only 3 rules, one elementary, and two with radius n-1• The size N of the binary string cannot be multiple of n• N and n have to be numbers relatively prime.

11. Concluding Remarks and Next Steps

46

• To solve the MOD5 problem and to merge satisfactorily the rules , and , or rules , and we have to disable active transitions in the rule pairs involved in simultaneous shifts of strings, as shown below :

Concluding Remarks

• stands for either or

3,0*1G

2,0*2G

0*3G

3,1*1G

2,1*2G

1*3G

G 0G 1G


47

• For the suitability of and , we then have to disable 5 pairs of groups of active transitions. In general, this number depends on n, as below:

Concluding Remarks

2 Steps 3 Steps 4 Steps

G 3* G 2* G 2* G 4* G 3* G 2* G 3* G 2* G 2* G 5* G 4* G 3* G 2* G 4* G 3* G 2* G 3* G 2* G 2*

G 4* 1G 3* 1 G 3* 1 1 1

G 2* 1 G 2* 1 1 1 G 2* 1 1 1 1 1 1G 1* 1 1 1 G 1* 1 1 1 1 1 G 1* 1 1 1 1 1 1 1 1 1 1

G 3* 1G 2* 1 1 G 2* 1 1 1

G 1* 1 G 1* 1 1 1 G 1* 1 1 1 1 1 1

G 2* 1G 1* 1 G 1* 1 1 1

4 Steps G 1* 1

2(Cn -3,2) 3(Cn -4,2) 4(Cn -5,2)

Subtotal 2 3 4

Total

3 Steps

Pairs of groups of active state transitions to be disabled

1 Stepn =6

1 Step 2 Stepsn =7

1 Step 2 Steps

9

Cn -2,2 Cn -2,2 2(Cn -3,2) Cn -2,2 2(Cn -3,2)

n =5

35

1 Step

2 Steps

3 Steps

5 15

3(Cn -4,2)

3 6 6 10 12

05M

15M


48

• The solution to the MODn problem was generalised for any value of n.

Concluding Remarks

• The generalised solution was simplified by merging cellular automata rules through the joining of the active transitions.

• In order to merge rules for performing equivalent operation, tasks were modified and conflicts solved, following a standard that allowed us to generalise the MODn simplified solution.

• Much study is still necessary for the understanding and the generalisation of these mergings.

Acknowledgements

55

Thank You Very Much!

Muito Obrigado!

IPM – Instituto Presbiteriano Mackenzie

MackPesquisa – Fundo Mackenzie de Pesquisa

We are grateful to:

Documents

Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem Claudio Martins Pedro de Oliveira Universidade Presbiteriana Mackenzie São