Most complex automaton you have ever made

[Wojowu]

As in topic - what is most complex cellular automaton you have ever created? I mean "complex" in terms of number of states, number of transitions or some other complexity measures you invent. Most complex CA I have created is 45-state automaton which can simulate any Turing machine

Code: Select all

n_states:45
neighborhood:Moore
symmetries:none
var a={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}
var b={a}
var c={a}
var d={a}
var e={a}
var f={a}
var g={a}
var h={a}
27,a,b,c,d,44,f,g,h,44
27,44,b,c,d,e,f,g,h,44
41,a,b,c,d,44,f,g,h,0
41,44,b,c,d,e,f,g,h,0
1,a,b,c,d,44,f,g,h,44
1,44,b,c,d,e,f,g,h,44
0,44,b,c,d,44,f,g,h,0
0,44,b,c,d,44,f,g,h,0
0,0,b,c,d,44,f,g,h,0
0,44,b,c,d,0,f,g,h,0
0,a,b,c,d,44,f,g,h,44
0,44,b,c,d,a,f,g,h,44
44,a,b,c,d,e,f,g,h,0
2,a,23,c,24,e,f,g,h,2
5,a,b,c,d,42,f,g,h,43
43,a,b,c,d,e,f,g,h,0
1,a,b,c,d,43,f,g,h,0
1,a,b,c,d,e,f,43,h,44
0,a,b,c,d,e,f,43,h,43
0,10,b,c,d,e,f,42,h,42
0,a,b,c,d,42,f,g,h,42
42,0,b,c,d,e,f,g,h,0
42,5,b,c,d,e,f,g,h,0
0,25,b,c,d,41,f,g,h,1
0,41,b,c,d,19,f,g,h,1
0,a,b,c,27,23,f,g,h,0
0,24,27,c,d,e,f,g,h,0
0,a,b,c,27,17,f,g,h,0
0,18,27,c,d,e,f,g,h,0
0,27,b,c,d,0,f,g,0,41
0,0,b,c,d,27,0,g,h,41
41,a,b,c,d,e,f,g,h,27
27,a,b,c,d,e,f,17,h,27
27,a,b,c,d,e,f,18,h,27
27,a,b,c,d,e,f,23,h,27
27,a,b,c,d,e,f,24,h,27
0,10,b,c,d,e,f,8,h,34
0,a,b,c,d,34,f,g,h,34
34,a,b,c,d,e,f,9,h,36
34,0,b,c,d,e,f,g,h,0
34,5,b,c,d,e,f,g,h,0
10,a,b,c,d,e,f,28,h,28
10,a,b,c,d,e,f,29,h,29
2,a,b,27,d,e,f,g,h,2
16,a,1,c,1,e,f,g,h,21
2,a,b,1,d,e,f,g,h,3
2,a,b,0,d,e,f,3,h,4
2,a,b,0,d,e,f,g,h,0
1,a,b,c,d,e,f,2,h,2
3,a,b,c,d,e,f,g,h,0
4,a,b,c,d,e,f,g,h,0
0,a,b,3,6,e,f,g,h,0
0,a,b,3,d,e,f,g,h,3
0,a,b,4,d,e,f,g,h,4
0,a,b,c,3,5,f,g,h,3
0,a,3,5,d,e,f,g,h,6
0,a,3,6,d,e,f,g,h,5
5,3,b,c,d,e,f,g,h,0
0,5,4,c,d,e,f,g,h,7
6,a,b,c,d,e,f,g,h,0
7,a,b,c,d,e,f,g,h,0
0,7,b,c,d,e,f,9,h,10
10,a,b,c,d,e,f,1,h,11
10,a,b,c,d,e,f,14,h,14
10,a,b,c,d,e,f,15,h,15
10,a,b,c,d,e,f,g,h,0
0,10,b,c,d,e,f,8,h,0
0,10,b,c,d,e,f,g,h,10
0,7,b,c,d,e,f,g,h,7
11,a,b,c,d,e,f,g,h,0
0,a,b,c,d,11,f,g,h,11
0,a,b,c,d,e,11,5,h,12
12,a,b,c,d,e,f,g,h,0
0,a,b,c,d,e,0,12,0,12
0,a,b,13,d,e,f,12,1,12
1,a,b,c,d,e,f,12,h,13
13,a,b,c,d,e,f,g,h,1
1,a,b,c,d,e,f,13,h,13
0,a,b,c,d,e,f,13,h,1
0,a,b,c,d,14,f,g,h,14
14,1,b,c,d,e,f,g,h,14
14,14,b,c,d,e,f,g,h,14
0,a,b,19,d,e,f,16,h,0
16,a,b,c,d,e,f,g,h,0
0,1,b,c,d,1,f,16,h,0
0,a,b,c,d,e,f,16,h,16
0,a,b,c,1,16,f,g,h,17
0,16,1,c,d,e,f,g,h,18
0,a,b,1,0,21,f,g,h,17
0,21,0,1,d,e,f,g,h,18
17,a,b,c,d,e,f,g,h,0
18,a,b,c,d,e,f,g,h,0
0,a,b,c,d,17,f,g,h,17
0,18,b,c,d,e,f,g,h,18
1,a,b,c,d,e,f,16,h,19
1,a,b,c,d,e,f,17,h,19
1,a,b,c,d,e,f,18,h,19
19,a,b,c,d,e,f,g,h,0
0,19,b,c,d,e,f,g,h,1
1,a,b,c,d,e,f,19,h,19
14,a,b,c,d,e,f,g,h,0
0,a,b,c,d,e,14,5,h,16
0,a,b,0,d,e,f,12,1,20
0,a,b,1,d,e,f,12,1,12
0,a,b,c,d,e,f,20,h,1
20,a,b,c,d,e,f,g,h,0
21,a,b,c,d,e,f,g,h,0
22,a,1,c,1,e,f,g,h,26
0,a,b,25,d,e,f,22,h,0
22,a,b,c,d,e,f,g,h,0
0,1,b,c,d,1,f,22,h,0
0,a,b,c,d,e,f,22,h,22
0,a,b,c,1,22,f,g,h,23
0,22,1,c,d,e,f,g,h,24
0,a,b,1,0,26,f,g,h,23
0,26,0,1,d,e,f,g,h,24
23,a,b,c,d,e,f,g,h,0
24,a,b,c,d,e,f,g,h,0
0,a,b,c,d,23,f,g,h,23
0,24,b,c,d,e,f,g,h,24
1,a,b,c,d,e,f,22,h,25
1,a,b,c,d,e,f,23,h,25
1,a,b,c,d,e,f,24,h,25
25,a,b,c,d,e,f,g,h,0
0,a,b,c,d,25,f,g,h,1
1,a,b,c,d,e,f,25,h,25
26,a,b,c,d,e,f,g,h,0
15,0,b,c,d,e,f,g,h,0
15,5,b,c,d,e,f,g,h,0
0,a,b,c,d,15,f,g,h,15
0,a,b,c,d,e,15,5,h,22
27,0,b,c,d,0,f,g,h,1
27,a,b,c,d,e,f,g,h,0
0,a,b,c,d,28,f,9,h,30
0,a,b,c,d,29,f,9,h,31
28,0,b,c,d,e,f,g,h,0
28,5,b,c,d,e,f,g,h,0
0,a,b,c,d,28,f,g,h,28
29,0,b,c,d,e,f,g,h,0
29,5,b,c,d,e,f,g,h,0
0,a,b,c,d,29,f,g,h,29
0,a,b,c,d,e,f,2,1,2
30,a,b,c,d,1,f,g,h,9
30,a,b,c,d,e,f,g,h,0
0,a,b,1,d,e,f,30,h,32
0,a,b,5,d,e,f,30,h,32
0,a,b,c,d,e,f,30,h,30
9,a,b,c,d,e,f,30,h,30
32,a,b,0,d,e,f,g,h,0
32,a,b,c,d,e,f,30,h,0
0,32,b,c,d,e,f,g,30,32
0,32,0,c,d,e,f,g,h,32
0,a,32,32,d,e,f,g,h,30
31,a,b,c,d,1,f,g,h,9
31,a,b,c,d,e,f,g,h,0
0,a,b,1,d,e,f,31,h,33
0,a,b,5,d,e,f,31,h,33
0,a,b,c,d,e,f,31,h,31
9,a,b,c,d,e,f,31,h,31
33,a,b,0,d,e,f,g,h,0
33,a,b,c,d,e,f,31,h,0
0,a,b,c,d,33,31,g,h,33
0,a,b,c,0,33,f,g,h,33
0,a,b,33,33,e,f,g,h,31
9,a,b,34,d,e,f,g,h,35
9,a,b,35,d,e,f,g,h,35
0,a,b,35,d,e,f,9,h,35
35,a,b,c,d,1,f,g,h,8
35,a,b,c,d,e,f,g,h,0
36,a,b,c,d,1,f,g,h,8
36,a,b,c,d,e,f,g,h,0
0,a,b,1,d,e,f,36,h,39
0,a,b,c,d,e,f,36,h,36
9,a,b,c,d,e,f,36,h,36
0,a,b,c,5,36,f,g,h,37
0,36,5,c,d,e,f,g,h,38
37,a,b,c,d,e,f,g,h,0
38,a,b,c,d,e,f,g,h,0
0,38,b,c,d,e,f,g,h,38
0,a,b,c,d,37,f,g,h,37
33,a,b,c,d,37,f,g,h,39
32,38,b,c,d,e,f,g,h,39
39,a,b,c,d,1,f,g,h,9
39,a,b,c,d,e,f,g,h,0
0,a,b,39,d,e,f,8,h,39
8,a,b,39,d,e,f,g,h,39
5,a,b,c,d,34,f,g,h,40
5,a,b,c,d,e,f,36,h,1
5,a,b,c,d,e,f,37,h,1
5,a,b,c,d,e,f,38,h,1
5,a,b,c,d,e,f,39,h,1
40,a,1,c,d,e,f,g,h,5
40,a,b,c,d,e,f,g,h,0
0,1,b,c,d,e,f,40,h,2
0,a,b,c,d,e,f,40,h,40
1,a,b,c,d,e,f,32,h,5
1,a,b,c,d,e,f,33,h,5

Here is demonstration of its possibilities, namely 5-state 2-color busy beaver

Code: Select all

x = 9, y = 67, rule = Turing
6.A$5.pP2.pC2$H.H.pOA$A.A$A.A$N.O$N.O$N.O$pD.pD$pD.pD$pD$pD$H.H2.A$A.
A$A.A$O.O$O.O$O.O$2.pD$2.pD$H.H2.A$A.A$N.A$N.O$N.O$pD.O$pD.pD$pD.pD$pD
$H.H2.A$A.A$A.A$N.N$N.N$N.N$2.pE$2.pE$2.pE$2.pE$2.pE$2.pE$2.pE$2.pE$H
.H2.A$A.A$N.A$N.pR$N$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$pE$
H.H.A$.A.A!

Also, what is most complex CA ever created? I think this one is Perrier loop, which is 64-state one.

[p46beth]

I usually limit my attention to *REASONABLY* simply rules, the most states I have used in one rule is the 9-state switch1329 and switch357.

Also, what is most complex CA ever created? I think this one is Perrier loop, which is 64-state one.

Oh I can beat that! How about a 23075230572038720857239857230987 state CA, in which each cell is the sum of its neighbors in the previous generation, mod 23075230572038720857239857230987? Or just replace 23075230572038720857239857230987 with any integer...

[Wojowu]

I knew that someone will invent something like that. But I think everyone understands what I mean with "complex" CA. I am thinking about automata in which every state reacts with another ones in some distinct way

[beebop]

Slightly off topic: How does that Turing machine rule work?

[Wojowu]

States 27 and 41 make tape. State 39 and 9 define current machine state. State 8 defines possible machine states. States 2-6 allow to read current tape symbol. State 7 searches for current state. State 1 and 5 to the right of 8 are used during state change. State 1 on tape is tape symbol. State 1 under 8 and 9 defines number which will be written on tape. 3 cells in state 14 or 15 mean "move tape down" or "move tape up", respectively. States 28 and 29 define state changes. Changing machine state by n requires 2^n cells this can surely be improved. State 10 reads instructions. State 40 allows to read tape once again. State 42 means Halt. State 44 clears blank symbols after halting, to prevent from infinite growth. Rest of states are used mostly to send instruction to desired location. I will add my collection of Turing machines in this rule a bit later (over 30 machines!). Some of them need pre-defined input, but most are Busy Beaver machines, which run on empty initial tape.

[Wojowu]

Here is my collection of simulators. I attached it to post