Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

For discussion of other cellular automata.
Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 4th, 2016, 8:42 pm

So this is Turing-complete.

It could be optimized. And also could be extended with other cell states to build an infinite embedded diagonal 1D-CA space.

The rule file is:

Code: Select all

@RULE rule110in2d

Embedding rule 110 elementary cellular automaton - it is Turing-complete
Naszvadi Peter, 2016

@TABLE

# Format: C,N,E,S,W,C'

n_states:15
neighborhood:vonNeumann
symmetries:permute
var a={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
var b={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
var c={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
var d={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
var e={0,1,2,3,4,5,6,7,8,9,10,11,13,14}
var f={0,1,2,3,4,5,6,7,8,9,10,11,13,14}
var g={0,1,2,3,4,5,6,7,8,9,10,11,13,14}
var h={0,1,2,3,4,5,6,7,8,9,10,13,14}
var i={0,1,2,3,4,5,6,7,8,9,10,13,14}
var j={0,1,2,3,4,5,6,7,8,9,10,13,14}
var k={0,1,2,4,5,6,7,8,9,10,13,14}
var l={0,1,2,4,5,6,7,8,9,10,13,14}
var m={0,1,2,4,5,6,7,8,9,10,13,14}

var n={0,1,2,3,4,5,6,8,9,10,11,12,13,14}
var o={0,1,2,3,4,5,6,8,9,10,11,12,13,14}
var p={0,1,2,3,4,5,6,8,9,10,11,12,13,14}

var q={0,1,2,4,5,6,7,8,9,10,11,12,13,14}

var r={0,1,2,3,4,5,6,8,9,10,13,14}
var s={0,1,2,3,4,5,6,8,9,10,13,14}
var t={0,1,2,3,4,5,6,8,9,10,13,14}

var u={0,1,2,4,5,6,7,8,9,10,11,12,13,14}
var v={0,1,2,4,5,6,7,8,9,10,11,12,13,14}

var w={0,1,2,5,6,9,10,11,12,13,14}
var x={0,1,2,5,6,9,10,11,12,13,14}
var y={0,1,2,5,6,9,10,11,12,13,14}
var z={0,1,2,5,6,9,10,11,12,13,14}

1,12,a,b,c,4
1,11,e,f,g,3
1,3,h,i,j,3
1,4,k,l,m,4
1,a,b,c,d,1
2,a,b,c,d,1
3,a,b,c,d,2
4,a,b,c,d,2
5,12,a,b,c,8
5,11,e,f,g,7
5,7,h,i,j,7
5,8,r,s,t,8
5,a,b,c,d,5
6,a,b,c,d,5
7,a,b,c,d,6
8,a,b,c,d,6
9,7,3,a,b,12
9,4,n,o,p,11
9,4,q,u,v,11
9,3,n,o,p,11
9,7,q,u,v,11
9,8,n,o,p,11
9,8,q,u,v,11
9,w,x,y,z,9
10,7,a,b,c,11
10,8,n,o,p,12
10,3,n,o,p,12
10,4,n,o,p,12
10,w,x,y,z,10
11,a,b,c,d,13
12,a,b,c,d,14
13,a,b,c,d,9
14,a,b,c,d,10

@COLORS

1 255 255 255
2 192 192 192
3 64 255 64
4 255 64 64
5 250 250 250
6 188 188 188
7 60 250 60
8 250 60 60
9 0 128 0
10 128 0 0
11 64 192 192
12 192 64 192
13 192 192 64
14 192 192 0
And an example pattern is (the crossroads denote the cells in Rule-110):

Code: Select all

x = 7, y = 15, rule = rule110in2d
LAA$
F.B$
EEKAA$
..F.B$
..EEKAA$
....F.B$
....EEK$
$
$
$
LAAAA$
F...A$
E...A$
E...B$
EEEEK$!
The result can be checked comparing with the output of this tiny python code:

Code: Select all

#!/usr/bin/env python
# rule transitions vector:
d=[0,1,1,1,0,1,1,0]
# initial space configuration:
a=[0,1,1,1]
for j in range(9): # nine generations
    print a
    a=[0]+a+[0]
    b=[]
    for i in range(1,len(a)-1):
        b=b+[d[4*a[i-1]+2*a[i]+a[i+1]]]
    a=b
Just for fun! :)

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 6th, 2016, 1:59 pm

Explanation of cell values:
  • empty cell: 0 ( or "." )
  • Wire type #1
    • top wire: 1 ( or "A" )
    • top wire sign tail: 2 ( or "B" )
    • top wire sign true: 3 ( or "C" )
    • top wire sign false: 4 ( or "D" )
  • Wire type #2
    • bottom wire: 5 ( or "E" )
    • bottom wire sign tail: 6 ( or "F" )
    • bottom wire sign true: 7 ( or "G" )
    • bottom wire sign false: 8 ( or "H" )
  • "Crossroads" (waits for colliding signs to create next generation signs)
    • state true: 9 ( or "I" )
    • state false: 10 ( or "J" )
    • state generating true sign on connected cells with wire values: 11 ( or "K" )
    • state generating false sign on connected cells with wire values: 12 ( or "L" )
    • intermediary state with true value: 13 ( or "M" )
    • intermediary state with false value: 14 ( or "N" )
A sign is moving:

Code: Select all

000000
000000
567555
000000
000000

Code: Select all

000000
000000
556755
000000
000000

Code: Select all

000000
000000
555675
000000
000000
I use promoted crossroad cell types with special meaning, containing temporary states. The trick about embedding the Rule-110 transition function is: a crossroad-type cell has a state too ("0"/false or "1"/true), and at the same time, there are two sign heads in two of the four connecting cells when they collide - and then generate the next cell state in the crossroads and "giving birth" to the new signals that will travel to the nearest crossroads.

Conjectured that one wire sign tail is reduntant, so a similar rule with less cell states may exist.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by wildmyron » December 7th, 2016, 3:02 am

That's quite a neat simulation. Thanks for the explanation of the cell states - that made it much clearer what is going on.

It's interesting that you can slow down the simulation as much as you want without increasing the spatial period of the crossroad cells.

Code: Select all

x = 14, y = 14, rule = rule110in2d
5.3A$4.2A.A$2.L2A.2A$2.F2.2A.3A$.2E2.B.2A.A$2E.2EK2A.2A$E.2E.F2.2A.3A
$3E.2E2.B.2A.A$3.2E.2EK2A.2A$3.E.2E.F2.2A$3.3E.2E2.B$6.2E.2EK$6.E.2E$
6.3E!
This doesn't seem like a desirable property but I suspect it's a consequence of the design of your rule in order to work with a totalistic neighbourhood. I suppose you considered such a simulation with a non-totalistic neighbourhood? It seems that a similar simulation could use many fewer states in that case.
Naszvadi wrote:Conjectured that one wire sign tail is reduntant, so a similar rule with less cell states may exist.
This is almost certainly true, it seems almost self-evident - but I wonder if the same thing can be done with even fewer states by having only one intermediate crossroad state for becoming on and off. What was the problem that was solved by having two intermediate states (i.e. for two successive ticks) instead of just the one?

In other words, if you removed state 13 and 14 and allowed 11 and 12 to transition directly to 9 and 10, would the resulting behaviour be any different?
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 7th, 2016, 9:30 am

wildmyron wrote:That's quite a neat simulation. Thanks for the explanation of the cell states - that made it much clearer what is going on.

It's interesting that you can slow down the simulation as much as you want without increasing the spatial period of the crossroad cells.

Code: Select all

x = 14, y = 14, rule = rule110in2d
5.3A$4.2A.A$2.L2A.2A$2.F2.2A.3A$.2E2.B.2A.A$2E.2EK2A.2A$E.2E.F2.2A.3A
$3E.2E2.B.2A.A$3.2E.2EK2A.2A$3.E.2E.F2.2A$3.3E.2E2.B$6.2E.2EK$6.E.2E$
6.3E!
...
Thank you! x2 :) With this technic, anybody can recognise that in Z^d, there is a relative simple totalistic TC-CA, with the similar transition functions.
wildmyron wrote:...
In other words, if you removed state 13 and 14 and allowed 11 and 12 to transition directly to 9 and 10, would the resulting behaviour be any different?
Well, you can try it - if a crossroad is in a sign-creation state AND its next state would be the next generation's state (instead of state "13"/"14", which are infertile), then 2 of the connecting cells will have a sign head. Which will trigger an other sign-creation state on the crossroads...

For reacting your unquoted recommendations, I am still working on optimizing this :)

And looking for techniques to embed rule110 somehow into life-like rules othen that GoL. A unit cell or an infinite halfspace of logic gates - where each row represents a generation in a 1D elementary rule - would be nice that implement the transition function of Rule-110!

Anyway, I am also looking for a binary TC-CA with Neumann-nbhgr, and also hunting for a ternary TC-CA also with Neumann-nbhgr with the following rule restrictions: 0-0000->0, 1-1111->1 (and if it is possible, 2-2222->2 should be included)

Something OT - I hate Moore-neighbourhood, because it is not edge-transitive, where each edge denotes a connection between two cells. Even asymmetrical if we denote the neighbourhoods with a hyperedge with 9 and 1 element subsets (edge-components) - two connecting hyperedge-pairs may have intersections containing different number of elements. That's the reason I am focusing cells on grids {3,6} {6,3}, and hyperbolic planar grids {3,n} = (three n-gons connected at each vertex), and multidimensional analogons. And for a bonus, a totalistic amphyrical TC 1D rule would be handy, too! Still wondering on (TC) cell spaces on uniform edge-transitive graphs that couldn't be realized on grids as the above examples

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by wildmyron » December 7th, 2016, 11:21 pm

Naszvadi wrote:
wildmyron wrote:...
In other words, if you removed state 13 and 14 and allowed 11 and 12 to transition directly to 9 and 10, would the resulting behaviour be any different?
Well, you can try it - if a crossroad is in a sign-creation state AND its next state would be the next generation's state (instead of state "13"/"14", which are infertile), then 2 of the connecting cells will have a sign head. Which will trigger an other sign-creation state on the crossroads...
Here's a rule which uses only one tail state and only one intermediate crossroad state for each of On and Off. The common tail state is state 2, but I have retained state 6 for compatibility. You can readily verify that state 6 is unused. It is thus a 12 state rule even though the rule table specifies n_states:13. It works by retaining the tail state for one extra tick when it is adjacent to a crossroad cell in an intermediate state, and preventing crossroad cells from transitioning when there is an adjacent cell in the tail state.

Code: Select all

@RULE rule110in2d12

Embedding rule 110 elementary cellular automaton - it is Turing-complete
Naszvadi Peter, 2016

State definitions from rule110in2d:
empty cell: 0 ( or "." )
Wire type #1
	top wire: 1 ( or "A" )
	top wire sign tail: 2 ( or "B" )
	top wire sign true: 3 ( or "C" )
	top wire sign false: 4 ( or "D" )
Wire type #2
	bottom wire: 5 ( or "E" )
	bottom wire sign tail: 6 ( or "F" )
	bottom wire sign true: 7 ( or "G" )
	bottom wire sign false: 8 ( or "H" )
"Crossroads" (waits for colliding signs to create next generation signs)
	state true: 9 ( or "I" )
	state false: 10 ( or "J" )
	state generating true sign on connected cells with wire values: 11 ( or "K" )
	state generating false sign on connected cells with wire values: 12 ( or "L" )
	intermediary state with true value: 13 ( or "M" )
	intermediary state with false value: 14 ( or "N" )

This 12 state version of rule110in2d has the following modifications
Two tail states replaced by a single tail state: 2
	state 6 remains for consistency but is unused in this ruletable
intermediate crossroad states (13 and 14) removed

@TABLE

# Format: C,N,E,S,W,C'

n_states:13
neighborhood:vonNeumann
symmetries:permute
var a={0,1,2,3,4,5,6,7,8,9,10,11,12}
var b={0,1,2,3,4,5,6,7,8,9,10,11,12}
var c={0,1,2,3,4,5,6,7,8,9,10,11,12}
var d={0,1,2,3,4,5,6,7,8,9,10,11,12}
var e={0,1,2,3,4,5,6,7,8,9,10,11}
var f={0,1,2,3,4,5,6,7,8,9,10,11}
var g={0,1,2,3,4,5,6,7,8,9,10,11}
var h={0,1,2,3,4,5,6,7,8,9,10}
var i={0,1,2,3,4,5,6,7,8,9,10}
var j={0,1,2,3,4,5,6,7,8,9,10}
var k={0,1,2,4,5,6,7,8,9,10}
var l={0,1,2,4,5,6,7,8,9,10}
var m={0,1,2,4,5,6,7,8,9,10}

var n={0,1,2,3,4,5,6,8,9,10,11,12}
var o={0,1,2,3,4,5,6,8,9,10,11,12}
var p={0,1,2,3,4,5,6,8,9,10,11,12}

var q={0,1,2,4,5,6,7,8,9,10,11,12}

var r={0,1,2,3,4,5,6,8,9,10}
var s={0,1,2,3,4,5,6,8,9,10}
var t={0,1,2,3,4,5,6,8,9,10}

var u={0,1,2,4,5,6,7,8,9,10,11,12}
var v={0,1,2,4,5,6,7,8,9,10,11,12}

var w={0,1,2,5,6,9,10,11,12}
var x={0,1,2,5,6,9,10,11,12}
var y={0,1,2,5,6,9,10,11,12}
var z={0,1,2,5,6,9,10,11,12}

# Top wire
1,12,a,b,c,4
1,11,e,f,g,3
1,3,h,i,j,3
1,4,k,l,m,4
1,a,b,c,d,1
3,a,b,c,d,2
4,a,b,c,d,2
2,1,11,a,b,2
2,1,12,a,b,2
2,1,a,b,c,1
2,3,a,b,c,1
2,4,a,b,c,1

# Bottom wire
5,12,a,b,c,8
5,11,e,f,g,7
5,7,h,i,j,7
5,8,r,s,t,8
5,a,b,c,d,5
7,a,b,c,d,2
8,a,b,c,d,2
2,5,11,a,b,2
2,5,12,a,b,2
2,5,a,b,c,5
2,7,a,b,c,5
2,8,a,b,c,5

# Crossroads
9,2,a,b,c,9
9,7,3,a,b,12
9,4,n,o,p,11
9,4,q,u,v,11
9,3,n,o,p,11
9,7,q,u,v,11
9,8,n,o,p,11
9,8,q,u,v,11
9,w,x,y,z,9
10,2,a,b,c,10
10,7,a,b,c,11
10,8,n,o,p,12
10,3,n,o,p,12
10,4,n,o,p,12
10,w,x,y,z,10
11,a,b,c,d,9
12,a,b,c,d,10

@COLORS

1 255 255 255
2 192 192 192
3 64 255 64
4 255 64 64
5 250 250 250
6 188 188 188
7 60 250 60
8 250 60 60
9 0 128 0
10 128 0 0
11 64 192 192
12 192 64 192
Here is a revised example pattern:

Code: Select all

x = 14, y = 34, rule = rule110in2d12
L2A$B.B$2EK2A$2.B.B$2.2EK2A$4.B.B$4.2EK4$L4A$B3.A$E3.A$E3.B$4EK6$5.3A
$4.2A.A$2.L2A.2A$2.B2.2A.3A$.2E2.B.2A.A$2E.2EK2A.2A$E.2E.B2.2A.3A$3E.
2E2.B.2A.A$3.2E.2EK2A.2A$3.E.2E.B2.2A$3.3E.2E2.B$6.2E.2EK$6.E.2E$6.3E
!
Naszvadi wrote:Anyway, I am also looking for a binary TC-CA with Neumann-nbhgr, and also hunting for a ternary TC-CA also with Neumann-nbhgr with the following rule restrictions: 0-0000->0, 1-1111->1 (and if it is possible, 2-2222->2 should be included)
Sounds like a significantly harder problem!

Can you please clarify the meaning of TC-CA? Elsewhere you refer to a "totalistic TC-CA" so I'm not sure if you just mean totalistic or something else.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 8th, 2016, 3:38 pm

wildmyron wrote:...
Naszvadi wrote:Anyway, I am also looking for a binary TC-CA with Neumann-nbhgr, and also hunting for a ternary TC-CA also with Neumann-nbhgr with the following rule restrictions: 0-0000->0, 1-1111->1 (and if it is possible, 2-2222->2 should be included)
Sounds like a significantly harder problem!

Can you please clarify the meaning of TC-CA? Elsewhere you refer to a "totalistic TC-CA" so I'm not sure if you just mean totalistic or something else.
TC = Turing-complete!

Dramatically reduced the necessary states: 7 states are enough to embed any kind of elementary CA in a totalistic CA that has a neighbourhood graph with an infinite path, and it has a generalized Neumann-neighbourhood.

Code: Select all

@RULE rule110in2d7n

Embedding rule 110 elementary cellular automaton - it is Turing-complete
Naszvadi Peter, 2016
This a simple supersymmetric embedding of Rule-110 into almost any
cellular automata grid!

@TABLE

# Format: C,N,E,S,W,C'

n_states:7
neighborhood:vonNeumann
symmetries:permute
var a={0,1,2,3,4,5,6}
var b={0,1,2,3,4,5,6}

1,5,4,a,b,2
1,6,4,a,b,2
2,6,4,a,b,1
3,1,6,a,b,4
3,2,6,a,b,4
4,2,6,a,b,3
5,3,2,a,b,6
5,4,2,a,b,6
6,4,2,a,b,5

@COLORS

1 255 255 255
2 128 255 0
3 192 192 192
4 64 255 0
5 128 128 128
6 0 255 0
A small python snippet that helped to generate the transitions:

Code: Select all

#!/usr/bin/env python
# 111 0
# 110 1
# 101 1
# 100 0
# 011 1
# 010 1
# 001 1
# 000 0
change = [0,1,0,0,0,1,0,1]

for i in [1,3,5]:
  nearupbase = i+2
  if nearupbase > 5: nearupbase -= 6
  neardnbase = i+4
  if neardnbase > 5: neardnbase -= 6
  for dn in range(2): # down cell value
    for ct in range(2): # center cell value
      for up in range(2): # up cell value
        if change[4*dn+2*ct+up]:
          print "%d,%d,%d,a,b,%d" % \
            (ct+i,dn+neardnbase,up+nearupbase,i+1-ct)
And an example pattern (repeats every 7th gens.):

Code: Select all

x = 41, y = 3, rule = rule110in2d7n
ACEBCEBDEBDFBDEACFACFBCFBDFBCEADEADFADFBD$
F.......................................F$
DBFDAFDAEDAECBFDBFCBFCAFCAEDBFDBEDBECBECA$
I will try answering the remainig questions :) Be patient (not as my family), I am on vacation ;)

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by wildmyron » December 8th, 2016, 10:38 pm

That's quite a nice simplification. Very nice.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 9th, 2016, 7:20 pm

wildmyron wrote:That's quite a nice simplification. Very nice.
Thanks :) Any sort of 1D automaton with at most n states can be embedded into a _totalistic_ 1D automaton with at most 3*n states, the process/proof/construction is obvious from my previous posts.

On euclydian grids like Z^2, Z^3 etc. the space could be tiled with 1-codimensional hyperplanes containing exactly one 1D-cell, so 6 states are enough (no need for default passive state).

offtopic: Rule-110 is injected into B3/S238 (not typo) - trivial, a Game of Life pattern works there well!

Have a nice weekend everyone!

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 14th, 2016, 7:20 pm

6 states are enough to embed Rule-110.
(1 background, 1 helper, 4 "real" cell states)
And with very small number of transitions this time.

The rule is:

Code: Select all

@RULE rule110in2d6n

Embedding rule 110 elementary cellular automaton - it is Turing-complete
Naszvadi Peter, 2016
This a simple supersymmetric embedding of Rule-110 into almost any
cellular automata grid with at least 2 dimensions!

@TABLE

# Format: C,N,E,S,W,C'

n_states:6
neighborhood:vonNeumann
symmetries:permute

# false: 2, 4
# true: 3, 5
# connected cell has parity: 1 - means swap neighbours' order
# default empty cell: 0

2,2,5,0,0,3
2,3,5,0,0,3
3,3,5,0,0,2
2,4,3,1,0,3
2,5,3,1,0,3
3,5,3,1,0,2
4,4,3,0,0,5
4,5,3,0,0,5
5,5,3,0,0,4
4,2,5,1,0,5
4,3,5,1,0,5
5,3,5,1,0,4

@COLORS

1 255 255 255
2 188 255 0
3 255 128 0
4 192 255 0
5 255 120 0
And an example pattern is here:

Code: Select all

x = 13, y = 4, rule = rule110in2d6n
.CCEDCCDDCBDDA$
.EA.A.A.A.A.C$
.E.A.A.A.A.AC$
ABBDEBBEEBCEE$
14-length tiling, with period 7: "00010011011111", Ripped from universality proof's cardinal background pattern.

To be continued. The number of transitions can be reduced with at least 3.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 15th, 2016, 6:02 am

5 states are enough to embed Rule-110.

The rule is:

Code: Select all

@RULE rule110in2d5n

Embedding rule 110 elementary cellular automaton - it is Turing-complete
This theorem is used for proving the universality of this 2D rule
Naszvadi Peter, 2016
This is a simple embedding of Rule-110 into almost any
Euclidean 2+dimensional cellular automata grid!

@TABLE

# Format: C,N,E,S,W,C'

n_states:5
neighborhood:vonNeumann
symmetries:permute

# false: 2, 4
# true: 1, 3
# default empty cell: 0

# Example topology:
#
#...b[23]-c[01]
#     |     |
#   c[01]-d[01]-e[23]-f[01]
#                 |     |
#               f[01]-g[01]-h[23]-i[01]
#                             |     |
#                           i[01]-j[01]...
#
# means: b connected to c, c connected to b and d, etc.
# This hack for handling the noncommutativity of the
# neighbourhood arguments of the transition gate,
# is necessary because Rule-110 is not amphirical

# Currently needs 3+ dimensions to loop the tape without using
# thoroidal canonical hypersurface for realization of the
# neighbourhood graph of the cells

# TBD: transitions that correctly handles cut endpoints of tape

2,1,1,4,0,1
4,1,2,2,0,3
2,3,2,0,0,1
2,1,1,3,0,1
4,1,1,1,0,3
2,3,1,0,0,1
1,1,1,3,0,2
3,1,1,1,0,4
1,3,1,0,0,2

@COLORS

1 128 255 0
2 255 128 0
3 192 255 0
4 255 64 0
And an example pattern is (looped on thoroidal surface + 3 times repeated, period 7): 00010011011111

Code: Select all

x = 28, y = 14, rule = rule110in2d5n:T28,14
BB........................AC$
BDAB$
..BDAA$
....ADAA$
......ACAA$
........ADBB$
..........BCBB$
............BCAB$
..............BCAA$
................ACAB$
..................BDBA$
....................ADBA$
......................ACBA$
........................ACAA
Well there are 88 distinct 1D elementary cellular automata rules. Only W110 is known to be universal. But if we had a proof for universality of an amphirical one, it would be nice, because in that case, creating such rules in the topic would become trivial (needs at most 2-3 states, and some helper states to create isolated connected tape)

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 15th, 2016, 7:40 am

Naszvadi wrote:...

Well there are 88 distinct 1D elementary cellular automata rules. Only W110 is known to be universal. But if we had a proof for universality of an amphirical one, it would be nice, because in that case, creating such rules in the topic would become trivial (needs at most 2-3 states, and some helper states to create isolated connected tape)
Any regular mosaic on the hyperbolic plane is characterized by the Schläfli symbol {p,q}, where p is the side of a fundamental polygon, q is the number of intersecting polygons in each vertex.
We use the fact that a complete infitine binary tree is contained by all of the dual mosaic's edge graph, which is the p-gons' neighbour graph of the origin mosaic. And there is such containment, where assumed that p>4, then all vertices in the binary tree connected with edges in the containing graph, then this edge is in the tree, too.

And let's number the vertices of a complete binary tree: let its root become 0, and write to each vertex its distance from the root in number of edges. For each distance, pair a cell from a halfline-space of Rule-110, and place the cell's value onto the corresponding vertices of the binary tree (and into the p-gon). After this (infinite) process, fill the remaining p-gons with 0.

Now with the following transition function, the W110 is embed into {p,q}:
# 0 default state, 1=alive, 2=dead
2,1,2,2,0,...,0,1
2,1,1,1,0,...,0,1
1,1,1,1,0,...,0,2
# other states are stable

This is only a halfspace of W110. If we can inject an infinite ternary tree into the mosaic and the two trees are disjoint, then we could insert a whole Rule-110 automata. (I bet p>7 in this case)

Only 3 states needed anyway.

Edited, missed 2nd leaves cell value from rule transitions!

User avatar
_zM
Posts: 186
Joined: June 26th, 2016, 3:07 pm

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by _zM » December 15th, 2016, 11:03 am

W54 has also been proven universal, and it's much easier to implement.
moment

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 15th, 2016, 12:28 pm

_zM wrote:W54 has also been proven universal, and it's much easier to implement.
Wow! This is pretty cool! Is there an available proof of the universality of W54? And how to get it?

Thanks in advance!

Edit::append();

hope this helps: https://peerj.com/preprints/2553.pdf

User avatar
_zM
Posts: 186
Joined: June 26th, 2016, 3:07 pm

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by _zM » December 17th, 2016, 7:04 am

Somewhere on this forum there was a link to the paper in which the proof had been discussed, but I am on my phone right now, which makes it pretty hard to search for that kind of thing.
moment

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 17th, 2016, 1:16 pm

_zM wrote:Somewhere on this forum there was a link to the paper in which the proof had been discussed, but I am on my phone right now, which makes it pretty hard to search for that kind of thing.
Please #define Somewhere! I am curious. :?:

EDIT:

Are you still on phone?

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 18th, 2016, 11:33 am

Now, until _zM won't admit xe was wrong and xe believed that conjecture == proof show the proof, here is a stunning result:

In euclidean grids with dimension 6 or greater, there is a Turing-complete totalistic Neumann-nghbr CA with at most 3 states.

Construction based on this walk wegdes in inner unit hypercube centers in a 2^6 volume hypercube , in the following list, each hexaplet of binary digits represent a unit hypercube:
  1. 000000 3,6
  2. 000001 1,2
  3. 000010
  4. 000100
  5. 001000
  6. 010000
  7. 100000 1,2
  8. 000110 2,3
  9. 001010
  10. 001100
  11. 010001
  12. 100001
  13. 110000 2,3
  14. 000111 1,2
  15. 001011
  16. 001101
  17. 010011
  18. 010101
  19. 010110
  20. 011001
  21. 011010
  22. 011100
  23. 100011
  24. 100101
  25. 100110
  26. 101001
  27. 101010
  28. 101100
  29. 110010
  30. 110100
  31. 111000 1,2
  32. 010111 4,1
  33. 011101
  34. 011011
  35. 100111
  36. 101011
  37. 101101
  38. 110110
  39. 111010
  40. 111100 4,1
  41. 110111 3,1
  42. 111011
  43. 111101
  44. 111111 3,1
And we can place our cells into an infinite chain of 6d hypercubes with edge length 2, where its space diagonals are on the same line. And the unit cubes of all-1 "coordinates" are common with the all-0 "coordinated" unit cube of the following big hypercube.

The n,k pairs at the right of a hexaplet means that each word with x ones has exactly n neighbours with (x-1) ones, and k neighbours with (x+1) ones.

Based on my earlier post here, the construction of a transition rule in 6D-golly is obvious:
Naszvadi wrote:...

Now with the following transition function, the W110 is embed into {p,q}:
# 0 default state, 1=alive, 2=dead
2,1,2,2,0,...,0,1
2,1,1,1,0,...,0,1
1,1,1,1,0,...,0,2
# other states are stable

...

Only 3 states needed anyway.
The 6D "walks" were found by my model generator and by a MIP solver that processed it.

User avatar
_zM
Posts: 186
Joined: June 26th, 2016, 3:07 pm

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by _zM » December 18th, 2016, 1:05 pm

Naszvadi wrote:Now, until _zM won't admit he was wrong and he believed that conjecture == proof
I have to admit that I was misled by this thread:
viewtopic.php?p=6125#p6125
although the linked paper, http://uncomp.uwe.ac.uk/genaro/Papers/P ... -R54CA.pdf, does include a set of logic gates and glider guns that might help.

LAST MINUTE EDIT:
Interesting passage:
Paper wrote: So far we got enough collision scenarios to say that a counter machine can be simulated in Rule 54 CA[2]. We can
represent an infinite storage device by pattern of stationary localizations, breathers go; the information can be written in
the device (formation of go in collision of w! and w, Fig.5, first configuration), erased (go is annihilated in collision with w! or w, Fig.5, second and third configuration), read and shifted (Fig.6, sixth and ninth configuration); and, check of whether storage is empty can be implemented (Fig. 6, 15th configuration). These operations are enough to simulate a counter machine. The combination of counter machines will simulate a Turing machine, which must demonstrate Turing universality of Rule 54 CA.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » December 19th, 2016, 4:05 am

_zM wrote:...
I have to admit that I was misled by this thread:
viewtopic.php?p=6125#p6125
although the linked paper, http://uncomp.uwe.ac.uk/genaro/Papers/P ... -R54CA.pdf, does include a set of logic gates and glider guns that might help.

LAST MINUTE EDIT:
Interesting passage:
Paper wrote: So far we got enough collision scenarios to say that a counter machine can be simulated in Rule 54 CA[2]. We can
represent an infinite storage device by pattern of stationary localizations, breathers go; the information can be written in
the device (formation of go in collision of w! and w, Fig.5, first configuration), erased (go is annihilated in collision with w! or w, Fig.5, second and third configuration), read and shifted (Fig.6, sixth and ninth configuration); and, check of whether storage is empty can be implemented (Fig. 6, 15th configuration). These operations are enough to simulate a counter machine. The combination of counter machines will simulate a Turing machine, which must demonstrate Turing universality of Rule 54 CA.
This "article" or "publication" has poor quality. Not (just) typo-graphically. Glider phases - many supposals depend on this heavily. For example, in GoL it is important that glider phases can be altered easily via two suppressing guns with glider streams meeting in the right angle, one with the wanted phase, and the other's glider to be vanished once.

And in 1D elementary CAs, not too difficult to construct these particles like gates, gate chaining, devices etc. nowadays, even '80s computers' have enough resources for this purpose. I miss them.

As a mathematician, I would like to say that a few sentences with tons of garbage pictures and (no XOR 1000000000000+) codelines is not a proof.

The king is naked.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » January 6th, 2017, 12:46 pm

A not-too-subtle dump for all elementary 1D CA - a minial logical expression generator script for each rule - independent from golly:

Code: Select all

#! /usr/bin/env python
# Naszvadi P., 2017
# 1D CA expression generator, especially for unit cells
# Some rights and wrongs reserved: do not violate the laws of the author's country!

# globalis 1, we like antipatterns
toredek = [
'p',
'q',
'r',
'AND(y,y)',
'IOR(y,y)',
'NOT(y)',
'XOR(y,y)'
]

# globalis 2
kepletek = ['0','1']

# globalis 3
eredmeny = [(0,100,100,100,'')]*256

def AND(x,y):
  return(x&y)

def IOR(x,y):
  return(x|y)

def NOT(x):
  return(1-x)

def XOR(x,y):
  return(x^y)

def rekurziv(argum='x',melyseg=10,valtozo=0):
  # ez a lenyeg, amig van x az argumentumban, behelyettesit
  # global valtozoba general listat
  if 'x' in argum:
    if (valtozo<8) and (melyseg>0):
      for i in toredek:
        seged=argum.replace('x',i,1).replace('y','x')
        if    (not '(p,A' in seged) \
          and (not '(q,A' in seged) \
          and (not '(r,A' in seged) \
          and (not '(p,N' in seged) \
          and (not '(q,N' in seged) \
          and (not '(r,N' in seged) \
          and (not '(p,I' in seged) \
          and (not '(q,I' in seged) \
          and (not '(r,I' in seged) \
          and (not '(p,X' in seged) \
          and (not '(q,X' in seged) \
          and (not '(r,X' in seged) \
          and (not '(r,p' in seged) \
          and (not '(r,q' in seged) \
          and (not '(q,p' in seged) \
          and (not 'NOT(NOT(' in seged) \
          :
          rekurziv(seged,melyseg-1,valtozo+(i in ['p','q','r']))
  elif (not 'r,p' in argum) \
       and (not 'r,q' in argum) and (not 'q,p' in argum):
    kepletek.append(argum)

# void main()
rekurziv('x',10,0)

for i in kepletek:
  spaceid=0
  functypes=0
  if 'AND' in i: functypes+=1
  if 'IOR' in i: functypes+=1
  if 'NOT' in i: functypes+=1
  if 'XOR' in i: functypes+=1
  for (p,q,r) in ((1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0)):
    spaceid=spaceid<<1|eval('+'+i)
  if eredmeny[spaceid][1]==i.count('p')+i.count('q')+i.count('r'):
    if eredmeny[spaceid][2]==len(i):
      if eredmeny[spaceid][3]==functypes:
        if eredmeny[spaceid][4]>=i:
          eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
      elif eredmeny[spaceid][3]>functypes:
        eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
    elif eredmeny[spaceid][2]>len(i):
      eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
  elif eredmeny[spaceid][1]>i.count('p')+i.count('q')+i.count('r'):
    eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)

for i in eredmeny:
  print "%d %d %d %d %s" % i
And the results are (rule/number of substitutions/expression length in characters/distinct gates/expression):

Code: Select all

0 0 1 0 0
1 3 20 2 NOT(IOR(IOR(p,q),r))
2 3 20 3 AND(NOT(IOR(p,q)),r)
3 2 13 2 NOT(IOR(p,q))
4 3 20 3 AND(NOT(IOR(p,r)),q)
5 2 13 2 NOT(IOR(p,r))
6 3 20 3 AND(NOT(p),XOR(q,r))
7 3 20 3 NOT(IOR(AND(q,r),p))
8 3 20 2 AND(AND(NOT(p),q),r)
9 3 20 3 NOT(IOR(XOR(q,r),p))
10 2 13 2 AND(NOT(p),r)
11 3 25 3 AND(IOR(NOT(q),r),NOT(p))
12 2 13 2 AND(NOT(p),q)
13 3 25 3 AND(IOR(NOT(r),q),NOT(p))
14 3 20 3 AND(IOR(q,r),NOT(p))
15 1 6 1 NOT(p)
16 3 20 3 AND(NOT(IOR(q,r)),p)
17 2 13 2 NOT(IOR(q,r))
18 3 20 3 AND(NOT(q),XOR(p,r))
19 3 20 3 NOT(IOR(AND(p,r),q))
20 3 20 3 AND(NOT(r),XOR(p,q))
21 3 20 3 NOT(IOR(AND(p,q),r))
22 5 29 3 XOR(IOR(AND(p,q),XOR(p,r)),q)
23 5 34 3 NOT(AND(IOR(AND(p,q),r),IOR(p,q)))
24 4 22 2 AND(XOR(p,q),XOR(p,r))
25 4 27 4 NOT(IOR(AND(p,q),XOR(q,r)))
26 4 22 3 XOR(IOR(AND(p,q),r),p)
27 4 27 3 NOT(XOR(AND(XOR(p,q),r),q))
28 4 22 3 XOR(IOR(AND(p,r),q),p)
29 4 27 3 NOT(XOR(AND(XOR(p,r),q),r))
30 3 15 2 XOR(IOR(q,r),p)
31 3 20 3 NOT(AND(IOR(q,r),p))
32 3 20 2 AND(AND(NOT(q),p),r)
33 3 20 3 NOT(IOR(XOR(p,r),q))
34 2 13 2 AND(NOT(q),r)
35 3 25 3 AND(IOR(NOT(p),r),NOT(q))
36 4 22 2 AND(XOR(p,q),XOR(q,r))
37 4 27 4 NOT(IOR(AND(p,q),XOR(p,r)))
38 4 22 3 XOR(IOR(AND(p,q),r),q)
39 4 27 3 NOT(XOR(AND(XOR(p,q),r),p))
40 3 15 2 AND(XOR(p,q),r)
41 5 34 4 NOT(IOR(AND(p,q),XOR(IOR(p,q),r)))
42 3 20 2 AND(NOT(AND(p,q)),r)
43 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),q))
44 4 22 3 AND(IOR(q,r),XOR(p,q))
45 3 20 3 XOR(IOR(NOT(r),q),p)
46 4 22 2 XOR(IOR(XOR(p,r),q),p)
47 3 25 3 IOR(AND(NOT(q),r),NOT(p))
48 2 13 2 AND(NOT(q),p)
49 3 25 3 AND(IOR(NOT(r),p),NOT(q))
50 3 20 3 AND(IOR(p,r),NOT(q))
51 1 6 1 NOT(q)
52 4 22 3 XOR(IOR(AND(q,r),p),q)
53 4 27 3 NOT(XOR(AND(XOR(q,r),p),r))
54 3 15 2 XOR(IOR(p,r),q)
55 3 20 3 NOT(AND(IOR(p,r),q))
56 4 22 3 AND(IOR(p,r),XOR(p,q))
57 3 20 3 XOR(IOR(NOT(r),p),q)
58 4 22 2 XOR(IOR(XOR(q,r),p),q)
59 3 25 3 IOR(AND(NOT(p),r),NOT(q))
60 2 8 1 XOR(p,q)
61 4 27 3 IOR(NOT(IOR(p,r)),XOR(p,q))
62 4 27 4 IOR(AND(NOT(p),r),XOR(p,q))
63 2 13 2 NOT(AND(p,q))
64 3 20 2 AND(AND(NOT(r),p),q)
65 3 20 3 NOT(IOR(XOR(p,q),r))
66 4 22 2 AND(XOR(p,r),XOR(q,r))
67 4 27 4 NOT(IOR(AND(p,r),XOR(p,q)))
68 2 13 2 AND(NOT(r),q)
69 3 25 3 AND(IOR(NOT(p),q),NOT(r))
70 4 22 3 XOR(IOR(AND(p,r),q),r)
71 4 27 3 NOT(XOR(AND(XOR(p,r),q),p))
72 3 15 2 AND(XOR(p,r),q)
73 5 34 4 NOT(IOR(AND(p,r),XOR(IOR(p,r),q)))
74 4 22 3 AND(IOR(q,r),XOR(p,r))
75 3 20 3 XOR(IOR(NOT(q),r),p)
76 3 20 2 AND(NOT(AND(p,r)),q)
77 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),r))
78 4 22 2 XOR(IOR(XOR(p,q),r),p)
79 3 25 3 IOR(AND(NOT(r),q),NOT(p))
80 2 13 2 AND(NOT(r),p)
81 3 25 3 AND(IOR(NOT(q),p),NOT(r))
82 4 22 3 XOR(IOR(AND(q,r),p),r)
83 4 27 3 NOT(XOR(AND(XOR(q,r),p),q))
84 3 20 3 AND(IOR(p,q),NOT(r))
85 1 6 1 NOT(r)
86 3 15 2 XOR(IOR(p,q),r)
87 3 20 3 NOT(AND(IOR(p,q),r))
88 4 22 3 AND(IOR(p,q),XOR(p,r))
89 3 20 3 XOR(IOR(NOT(q),p),r)
90 2 8 1 XOR(p,r)
91 4 27 3 IOR(NOT(IOR(p,q)),XOR(p,r))
92 4 22 2 XOR(IOR(XOR(q,r),p),r)
93 3 25 3 IOR(AND(NOT(p),q),NOT(r))
94 4 27 4 IOR(AND(NOT(p),q),XOR(p,r))
95 2 13 2 NOT(AND(p,r))
96 3 15 2 AND(XOR(q,r),p)
97 5 34 4 NOT(IOR(AND(q,r),XOR(IOR(q,r),p)))
98 4 22 3 AND(IOR(p,r),XOR(q,r))
99 3 20 3 XOR(IOR(NOT(p),r),q)
100 4 22 3 AND(IOR(p,q),XOR(q,r))
101 3 20 3 XOR(IOR(NOT(p),q),r)
102 2 8 1 XOR(q,r)
103 4 27 3 IOR(NOT(IOR(p,q)),XOR(q,r))
104 5 29 3 AND(IOR(p,q),XOR(AND(p,q),r))
105 3 20 2 NOT(XOR(XOR(p,q),r))
106 3 15 2 XOR(AND(p,q),r)
107 5 34 4 IOR(NOT(IOR(p,q)),XOR(AND(p,q),r))
108 3 15 2 XOR(AND(p,r),q)
109 5 34 4 IOR(NOT(IOR(p,r)),XOR(AND(p,r),q))
110 4 27 4 IOR(AND(NOT(p),q),XOR(q,r))
111 3 20 3 IOR(NOT(p),XOR(q,r))
112 3 20 2 AND(NOT(AND(q,r)),p)
113 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(q,r)),r))
114 4 22 2 XOR(IOR(XOR(p,q),r),q)
115 3 25 3 IOR(AND(NOT(r),p),NOT(q))
116 4 22 2 XOR(IOR(XOR(p,r),q),r)
117 3 25 3 IOR(AND(NOT(q),p),NOT(r))
118 4 27 4 IOR(AND(NOT(q),p),XOR(q,r))
119 2 13 2 NOT(AND(q,r))
120 3 15 2 XOR(AND(q,r),p)
121 5 34 4 IOR(NOT(IOR(q,r)),XOR(AND(q,r),p))
122 4 27 4 IOR(AND(NOT(q),p),XOR(p,r))
123 3 20 3 IOR(NOT(q),XOR(p,r))
124 4 27 4 IOR(AND(NOT(r),p),XOR(p,q))
125 3 20 3 IOR(NOT(r),XOR(p,q))
126 4 22 2 IOR(XOR(p,q),XOR(p,r))
127 3 20 2 NOT(AND(AND(p,q),r))
128 3 15 1 AND(AND(p,q),r)
129 4 27 3 NOT(IOR(XOR(p,q),XOR(p,r)))
130 3 20 3 AND(NOT(XOR(p,q)),r)
131 4 32 4 AND(IOR(NOT(p),r),NOT(XOR(p,q)))
132 3 20 3 AND(NOT(XOR(p,r)),q)
133 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(p,r)))
134 5 29 3 AND(IOR(q,r),XOR(XOR(p,q),r))
135 3 20 3 NOT(XOR(AND(q,r),p))
136 2 8 1 AND(q,r)
137 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(q,r)))
138 3 20 3 AND(IOR(NOT(p),q),r)
139 4 27 3 IOR(AND(q,r),NOT(IOR(p,q)))
140 3 20 3 AND(IOR(NOT(p),r),q)
141 4 27 3 IOR(AND(q,r),NOT(IOR(p,r)))
142 5 29 2 XOR(AND(XOR(p,q),XOR(q,r)),r)
143 3 20 3 IOR(AND(q,r),NOT(p))
144 3 20 3 AND(NOT(XOR(q,r)),p)
145 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(q,r)))
146 5 29 3 AND(IOR(p,r),XOR(XOR(p,q),r))
147 3 20 3 NOT(XOR(AND(p,r),q))
148 5 29 3 AND(IOR(p,q),XOR(XOR(p,q),r))
149 3 20 3 NOT(XOR(AND(p,q),r))
150 3 15 1 XOR(XOR(p,q),r)
151 5 34 3 IOR(NOT(IOR(p,q)),XOR(XOR(p,q),r))
152 4 27 4 AND(IOR(p,q),NOT(XOR(q,r)))
153 2 13 2 NOT(XOR(q,r))
154 3 20 3 XOR(AND(NOT(q),p),r)
155 4 27 4 NOT(AND(IOR(p,q),XOR(q,r)))
156 3 20 3 XOR(AND(NOT(r),p),q)
157 4 27 4 NOT(AND(IOR(p,r),XOR(q,r)))
158 5 29 3 IOR(AND(q,r),XOR(IOR(q,r),p))
159 3 20 3 NOT(AND(XOR(q,r),p))
160 2 8 1 AND(p,r)
161 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(p,r)))
162 3 20 3 AND(IOR(NOT(q),p),r)
163 4 27 3 IOR(AND(p,r),NOT(IOR(p,q)))
164 4 27 4 AND(IOR(p,q),NOT(XOR(p,r)))
165 2 13 2 NOT(XOR(p,r))
166 3 20 3 XOR(AND(NOT(p),q),r)
167 4 27 4 NOT(AND(IOR(p,q),XOR(p,r)))
168 3 15 2 AND(IOR(p,q),r)
169 3 20 3 NOT(XOR(IOR(p,q),r))
170 1 1 0 r
171 3 20 2 IOR(NOT(IOR(p,q)),r)
172 4 22 2 XOR(AND(XOR(q,r),p),q)
173 4 27 4 IOR(AND(q,r),NOT(XOR(p,r)))
174 3 20 3 IOR(AND(NOT(p),q),r)
175 2 13 2 IOR(NOT(p),r)
176 3 20 3 AND(IOR(NOT(q),r),p)
177 4 27 3 IOR(AND(p,r),NOT(IOR(q,r)))
178 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),r)
179 3 20 3 IOR(AND(p,r),NOT(q))
180 3 20 3 XOR(AND(NOT(r),q),p)
181 4 27 4 NOT(AND(IOR(q,r),XOR(p,r)))
182 5 29 3 IOR(AND(p,r),XOR(IOR(p,r),q))
183 3 20 3 NOT(AND(XOR(p,r),q))
184 4 22 2 XOR(AND(XOR(p,r),q),p)
185 4 27 4 IOR(AND(p,r),NOT(XOR(q,r)))
186 3 20 3 IOR(AND(NOT(q),p),r)
187 2 13 2 IOR(NOT(q),r)
188 4 22 3 IOR(AND(p,r),XOR(p,q))
189 4 27 3 IOR(NOT(XOR(p,r)),XOR(p,q))
190 3 15 2 IOR(XOR(p,q),r)
191 3 20 3 IOR(NOT(AND(p,q)),r)
192 2 8 1 AND(p,q)
193 4 32 4 AND(IOR(NOT(r),p),NOT(XOR(p,q)))
194 4 27 4 AND(IOR(p,r),NOT(XOR(p,q)))
195 2 13 2 NOT(XOR(p,q))
196 3 20 3 AND(IOR(NOT(r),p),q)
197 4 27 3 IOR(AND(p,q),NOT(IOR(p,r)))
198 3 20 3 XOR(AND(NOT(p),r),q)
199 4 27 4 NOT(AND(IOR(p,r),XOR(p,q)))
200 3 15 2 AND(IOR(p,r),q)
201 3 20 3 NOT(XOR(IOR(p,r),q))
202 4 22 2 XOR(AND(XOR(q,r),p),r)
203 4 27 4 IOR(AND(q,r),NOT(XOR(p,q)))
204 1 1 0 q
205 3 20 2 IOR(NOT(IOR(p,r)),q)
206 3 20 3 IOR(AND(NOT(p),r),q)
207 2 13 2 IOR(NOT(p),q)
208 3 20 3 AND(IOR(NOT(r),q),p)
209 4 27 3 IOR(AND(p,q),NOT(IOR(q,r)))
210 3 20 3 XOR(AND(NOT(q),r),p)
211 4 27 4 NOT(AND(IOR(q,r),XOR(p,q)))
212 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),q)
213 3 20 3 IOR(AND(p,q),NOT(r))
214 5 29 3 IOR(AND(p,q),XOR(IOR(p,q),r))
215 3 20 3 NOT(AND(XOR(p,q),r))
216 4 22 2 XOR(AND(XOR(p,q),r),p)
217 4 27 4 IOR(AND(p,q),NOT(XOR(q,r)))
218 4 22 3 IOR(AND(p,q),XOR(p,r))
219 4 27 3 IOR(NOT(XOR(p,q)),XOR(p,r))
220 3 20 3 IOR(AND(NOT(r),p),q)
221 2 13 2 IOR(NOT(r),q)
222 3 15 2 IOR(XOR(p,r),q)
223 3 20 3 IOR(NOT(AND(p,r)),q)
224 3 15 2 AND(IOR(q,r),p)
225 3 20 3 NOT(XOR(IOR(q,r),p))
226 4 22 2 XOR(AND(XOR(p,r),q),r)
227 4 27 4 IOR(AND(p,r),NOT(XOR(p,q)))
228 4 22 2 XOR(AND(XOR(p,q),r),q)
229 4 27 4 IOR(AND(p,q),NOT(XOR(p,r)))
230 4 22 3 IOR(AND(p,q),XOR(q,r))
231 4 27 3 IOR(NOT(XOR(p,q)),XOR(q,r))
232 5 29 2 AND(IOR(AND(p,q),r),IOR(p,q))
233 5 34 4 IOR(AND(p,q),NOT(XOR(IOR(p,q),r)))
234 3 15 2 IOR(AND(p,q),r)
235 3 20 3 IOR(NOT(XOR(p,q)),r)
236 3 15 2 IOR(AND(p,r),q)
237 3 20 3 IOR(NOT(XOR(p,r)),q)
238 2 8 1 IOR(q,r)
239 3 20 2 IOR(IOR(NOT(p),q),r)
240 1 1 0 p
241 3 20 2 IOR(NOT(IOR(q,r)),p)
242 3 20 3 IOR(AND(NOT(q),r),p)
243 2 13 2 IOR(NOT(q),p)
244 3 20 3 IOR(AND(NOT(r),q),p)
245 2 13 2 IOR(NOT(r),p)
246 3 15 2 IOR(XOR(q,r),p)
247 3 20 3 IOR(NOT(AND(q,r)),p)
248 3 15 2 IOR(AND(q,r),p)
249 3 20 3 IOR(NOT(XOR(q,r)),p)
250 2 8 1 IOR(p,r)
251 3 20 2 IOR(IOR(NOT(q),p),r)
252 2 8 1 IOR(p,q)
253 3 20 2 IOR(IOR(NOT(r),p),q)
254 3 15 1 IOR(IOR(p,q),r)
255 0 1 0 1

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by calcyman » January 6th, 2017, 2:41 pm

Naszvadi wrote:A not-too-subtle dump for all elementary 1D CA - a minial logical expression generator script for each rule - independent from golly:
Nice. There's similar code on Hacker's Delight:

http://www.hackersdelight.org/hdcodetxt/boole.c.txt

Also, I computed minimal Boolean circuits for all 65536 four-input gates; the output is used by rule2asm.py (in apgmera) to convert outer-totalistic 2D CAs into efficient x86 assembly code.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
praosylen
Posts: 2443
Joined: September 13th, 2014, 5:36 pm
Location: Pembina University, Home of the Gliders
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by praosylen » January 6th, 2017, 4:54 pm

calcyman wrote:Also, I computed minimal Boolean circuits for all 65536 four-input gates; the output is used by rule2asm.py (in apgmera) to convert outer-totalistic 2D CAs into efficient x86 assembly code.
I wonder what employing a similar method for non-totalistic rules would result in. Possibly there could result some Boolean circuits small enough to adapt for use in apgmera?
former username: A for Awesome
praosylen#5847 (Discord)

The only decision I made was made
of flowers, to jump universes to one of springtime in
a land of former winter, where no invisible walls stood,
or could stand for more than a few hours at most...

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » January 6th, 2017, 5:09 pm

And a generated report on all 1D elementary equivalence classes using my latest scripts:
  1. cellular automata class: [0 255]
    • 0 0 1 0 0
    • 255 0 1 0 1
  2. cellular automata class: [1 127]
    • 1 3 20 2 NOT(IOR(IOR(p,q),r))
    • 127 3 20 2 NOT(AND(AND(p,q),r))
  3. cellular automata class: [2 16 191 247]
    • 2 3 20 3 AND(NOT(IOR(p,q)),r)
    • 16 3 20 3 AND(NOT(IOR(q,r)),p)
    • 191 3 20 3 IOR(NOT(AND(p,q)),r)
    • 247 3 20 3 IOR(NOT(AND(q,r)),p)
  4. cellular automata class: [3 17 63 119]
    • 3 2 13 2 NOT(IOR(p,q))
    • 17 2 13 2 NOT(IOR(q,r))
    • 63 2 13 2 NOT(AND(p,q))
    • 119 2 13 2 NOT(AND(q,r))
  5. cellular automata class: [4 223]
    • 4 3 20 3 AND(NOT(IOR(p,r)),q)
    • 223 3 20 3 IOR(NOT(AND(p,r)),q)
  6. cellular automata class: [5 95]
    • 5 2 13 2 NOT(IOR(p,r))
    • 95 2 13 2 NOT(AND(p,r))
  7. cellular automata class: [6 20 159 215]
    • 6 3 20 3 AND(NOT(p),XOR(q,r))
    • 20 3 20 3 AND(NOT(r),XOR(p,q))
    • 159 3 20 3 NOT(AND(XOR(q,r),p))
    • 215 3 20 3 NOT(AND(XOR(p,q),r))
  8. cellular automata class: [7 21 31 87]
    • 7 3 20 3 NOT(IOR(AND(q,r),p))
    • 21 3 20 3 NOT(IOR(AND(p,q),r))
    • 31 3 20 3 NOT(AND(IOR(q,r),p))
    • 87 3 20 3 NOT(AND(IOR(p,q),r))
  9. cellular automata class: [8 64 239 253]
    • 8 3 20 2 AND(AND(NOT(p),q),r)
    • 64 3 20 2 AND(AND(NOT(r),p),q)
    • 239 3 20 2 IOR(IOR(NOT(p),q),r)
    • 253 3 20 2 IOR(IOR(NOT(r),p),q)
  10. cellular automata class: [9 65 111 125]
    • 9 3 20 3 NOT(IOR(XOR(q,r),p))
    • 65 3 20 3 NOT(IOR(XOR(p,q),r))
    • 111 3 20 3 IOR(NOT(p),XOR(q,r))
    • 125 3 20 3 IOR(NOT(r),XOR(p,q))
  11. cellular automata class: [10 80 175 245]
    • 10 2 13 2 AND(NOT(p),r)
    • 80 2 13 2 AND(NOT(r),p)
    • 175 2 13 2 IOR(NOT(p),r)
    • 245 2 13 2 IOR(NOT(r),p)
  12. cellular automata class: [11 47 81 117]
    • 11 3 25 3 AND(IOR(NOT(q),r),NOT(p))
    • 47 3 25 3 IOR(AND(NOT(q),r),NOT(p))
    • 81 3 25 3 AND(IOR(NOT(q),p),NOT(r))
    • 117 3 25 3 IOR(AND(NOT(q),p),NOT(r))
  13. cellular automata class: [12 68 207 221]
    • 12 2 13 2 AND(NOT(p),q)
    • 68 2 13 2 AND(NOT(r),q)
    • 207 2 13 2 IOR(NOT(p),q)
    • 221 2 13 2 IOR(NOT(r),q)
  14. cellular automata class: [13 69 79 93]
    • 13 3 25 3 AND(IOR(NOT(r),q),NOT(p))
    • 69 3 25 3 AND(IOR(NOT(p),q),NOT(r))
    • 79 3 25 3 IOR(AND(NOT(r),q),NOT(p))
    • 93 3 25 3 IOR(AND(NOT(p),q),NOT(r))
  15. cellular automata class: [14 84 143 213]
    • 14 3 20 3 AND(IOR(q,r),NOT(p))
    • 84 3 20 3 AND(IOR(p,q),NOT(r))
    • 143 3 20 3 IOR(AND(q,r),NOT(p))
    • 213 3 20 3 IOR(AND(p,q),NOT(r))
  16. cellular automata class: [15 85]
    • 15 1 6 1 NOT(p)
    • 85 1 6 1 NOT(r)
  17. cellular automata class: [18 183]
    • 18 3 20 3 AND(NOT(q),XOR(p,r))
    • 183 3 20 3 NOT(AND(XOR(p,r),q))
  18. cellular automata class: [19 55]
    • 19 3 20 3 NOT(IOR(AND(p,r),q))
    • 55 3 20 3 NOT(AND(IOR(p,r),q))
  19. cellular automata class: [22 151]
    • 22 5 29 3 XOR(IOR(AND(p,q),XOR(p,r)),q)
    • 151 5 34 3 IOR(NOT(IOR(p,q)),XOR(XOR(p,q),r))
  20. cellular automata class: [23]
    • 23 5 34 3 NOT(AND(IOR(AND(p,q),r),IOR(p,q)))
  21. cellular automata class: [24 66 189 231]
    • 24 4 22 2 AND(XOR(p,q),XOR(p,r))
    • 66 4 22 2 AND(XOR(p,r),XOR(q,r))
    • 189 4 27 3 IOR(NOT(XOR(p,r)),XOR(p,q))
    • 231 4 27 3 IOR(NOT(XOR(p,q)),XOR(q,r))
  22. cellular automata class: [25 61 67 103]
    • 25 4 27 4 NOT(IOR(AND(p,q),XOR(q,r)))
    • 61 4 27 3 IOR(NOT(IOR(p,r)),XOR(p,q))
    • 67 4 27 4 NOT(IOR(AND(p,r),XOR(p,q)))
    • 103 4 27 3 IOR(NOT(IOR(p,q)),XOR(q,r))
  23. cellular automata class: [26 82 167 181]
    • 26 4 22 3 XOR(IOR(AND(p,q),r),p)
    • 82 4 22 3 XOR(IOR(AND(q,r),p),r)
    • 167 4 27 4 NOT(AND(IOR(p,q),XOR(p,r)))
    • 181 4 27 4 NOT(AND(IOR(q,r),XOR(p,r)))
  24. cellular automata class: [27 39 53 83]
    • 27 4 27 3 NOT(XOR(AND(XOR(p,q),r),q))
    • 39 4 27 3 NOT(XOR(AND(XOR(p,q),r),p))
    • 53 4 27 3 NOT(XOR(AND(XOR(q,r),p),r))
    • 83 4 27 3 NOT(XOR(AND(XOR(q,r),p),q))
  25. cellular automata class: [28 70 157 199]
    • 28 4 22 3 XOR(IOR(AND(p,r),q),p)
    • 70 4 22 3 XOR(IOR(AND(p,r),q),r)
    • 157 4 27 4 NOT(AND(IOR(p,r),XOR(q,r)))
    • 199 4 27 4 NOT(AND(IOR(p,r),XOR(p,q)))
  26. cellular automata class: [29 71]
    • 29 4 27 3 NOT(XOR(AND(XOR(p,r),q),r))
    • 71 4 27 3 NOT(XOR(AND(XOR(p,r),q),p))
  27. cellular automata class: [30 86 135 149]
    • 30 3 15 2 XOR(IOR(q,r),p)
    • 86 3 15 2 XOR(IOR(p,q),r)
    • 135 3 20 3 NOT(XOR(AND(q,r),p))
    • 149 3 20 3 NOT(XOR(AND(p,q),r))
  28. cellular automata class: [32 251]
    • 32 3 20 2 AND(AND(NOT(q),p),r)
    • 251 3 20 2 IOR(IOR(NOT(q),p),r)
  29. cellular automata class: [33 123]
    • 33 3 20 3 NOT(IOR(XOR(p,r),q))
    • 123 3 20 3 IOR(NOT(q),XOR(p,r))
  30. cellular automata class: [34 48 187 243]
    • 34 2 13 2 AND(NOT(q),r)
    • 48 2 13 2 AND(NOT(q),p)
    • 187 2 13 2 IOR(NOT(q),r)
    • 243 2 13 2 IOR(NOT(q),p)
  31. cellular automata class: [35 49 59 115]
    • 35 3 25 3 AND(IOR(NOT(p),r),NOT(q))
    • 49 3 25 3 AND(IOR(NOT(r),p),NOT(q))
    • 59 3 25 3 IOR(AND(NOT(p),r),NOT(q))
    • 115 3 25 3 IOR(AND(NOT(r),p),NOT(q))
  32. cellular automata class: [36 219]
    • 36 4 22 2 AND(XOR(p,q),XOR(q,r))
    • 219 4 27 3 IOR(NOT(XOR(p,q)),XOR(p,r))
  33. cellular automata class: [37 91]
    • 37 4 27 4 NOT(IOR(AND(p,q),XOR(p,r)))
    • 91 4 27 3 IOR(NOT(IOR(p,q)),XOR(p,r))
  34. cellular automata class: [38 52 155 211]
    • 38 4 22 3 XOR(IOR(AND(p,q),r),q)
    • 52 4 22 3 XOR(IOR(AND(q,r),p),q)
    • 155 4 27 4 NOT(AND(IOR(p,q),XOR(q,r)))
    • 211 4 27 4 NOT(AND(IOR(q,r),XOR(p,q)))
  35. cellular automata class: [40 96 235 249]
    • 40 3 15 2 AND(XOR(p,q),r)
    • 96 3 15 2 AND(XOR(q,r),p)
    • 235 3 20 3 IOR(NOT(XOR(p,q)),r)
    • 249 3 20 3 IOR(NOT(XOR(q,r)),p)
  36. cellular automata class: [41 97 107 121]
    • 41 5 34 4 NOT(IOR(AND(p,q),XOR(IOR(p,q),r)))
    • 97 5 34 4 NOT(IOR(AND(q,r),XOR(IOR(q,r),p)))
    • 107 5 34 4 IOR(NOT(IOR(p,q)),XOR(AND(p,q),r))
    • 121 5 34 4 IOR(NOT(IOR(q,r)),XOR(AND(q,r),p))
  37. cellular automata class: [42 112 171 241]
    • 42 3 20 2 AND(NOT(AND(p,q)),r)
    • 112 3 20 2 AND(NOT(AND(q,r)),p)
    • 171 3 20 2 IOR(NOT(IOR(p,q)),r)
    • 241 3 20 2 IOR(NOT(IOR(q,r)),p)
  38. cellular automata class: [43 113]
    • 43 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),q))
    • 113 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(q,r)),r))
  39. cellular automata class: [44 100 203 217]
    • 44 4 22 3 AND(IOR(q,r),XOR(p,q))
    • 100 4 22 3 AND(IOR(p,q),XOR(q,r))
    • 203 4 27 4 IOR(AND(q,r),NOT(XOR(p,q)))
    • 217 4 27 4 IOR(AND(p,q),NOT(XOR(q,r)))
  40. cellular automata class: [45 75 89 101]
    • 45 3 20 3 XOR(IOR(NOT(r),q),p)
    • 75 3 20 3 XOR(IOR(NOT(q),r),p)
    • 89 3 20 3 XOR(IOR(NOT(q),p),r)
    • 101 3 20 3 XOR(IOR(NOT(p),q),r)
  41. cellular automata class: [46 116 139 209]
    • 46 4 22 2 XOR(IOR(XOR(p,r),q),p)
    • 116 4 22 2 XOR(IOR(XOR(p,r),q),r)
    • 139 4 27 3 IOR(AND(q,r),NOT(IOR(p,q)))
    • 209 4 27 3 IOR(AND(p,q),NOT(IOR(q,r)))
  42. cellular automata class: [50 179]
    • 50 3 20 3 AND(IOR(p,r),NOT(q))
    • 179 3 20 3 IOR(AND(p,r),NOT(q))
  43. cellular automata class: [51]
    • 51 1 6 1 NOT(q)
  44. cellular automata class: [54 147]
    • 54 3 15 2 XOR(IOR(p,r),q)
    • 147 3 20 3 NOT(XOR(AND(p,r),q))
  45. cellular automata class: [56 98 185 227]
    • 56 4 22 3 AND(IOR(p,r),XOR(p,q))
    • 98 4 22 3 AND(IOR(p,r),XOR(q,r))
    • 185 4 27 4 IOR(AND(p,r),NOT(XOR(q,r)))
    • 227 4 27 4 IOR(AND(p,r),NOT(XOR(p,q)))
  46. cellular automata class: [57 99]
    • 57 3 20 3 XOR(IOR(NOT(r),p),q)
    • 99 3 20 3 XOR(IOR(NOT(p),r),q)
  47. cellular automata class: [58 114 163 177]
    • 58 4 22 2 XOR(IOR(XOR(q,r),p),q)
    • 114 4 22 2 XOR(IOR(XOR(p,q),r),q)
    • 163 4 27 3 IOR(AND(p,r),NOT(IOR(p,q)))
    • 177 4 27 3 IOR(AND(p,r),NOT(IOR(q,r)))
  48. cellular automata class: [60 102 153 195]
    • 60 2 8 1 XOR(p,q)
    • 102 2 8 1 XOR(q,r)
    • 153 2 13 2 NOT(XOR(q,r))
    • 195 2 13 2 NOT(XOR(p,q))
  49. cellular automata class: [62 118 131 145]
    • 62 4 27 4 IOR(AND(NOT(p),r),XOR(p,q))
    • 118 4 27 4 IOR(AND(NOT(q),p),XOR(q,r))
    • 131 4 32 4 AND(IOR(NOT(p),r),NOT(XOR(p,q)))
    • 145 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(q,r)))
  50. cellular automata class: [72 237]
    • 72 3 15 2 AND(XOR(p,r),q)
    • 237 3 20 3 IOR(NOT(XOR(p,r)),q)
  51. cellular automata class: [73 109]
    • 73 5 34 4 NOT(IOR(AND(p,r),XOR(IOR(p,r),q)))
    • 109 5 34 4 IOR(NOT(IOR(p,r)),XOR(AND(p,r),q))
  52. cellular automata class: [74 88 173 229]
    • 74 4 22 3 AND(IOR(q,r),XOR(p,r))
    • 88 4 22 3 AND(IOR(p,q),XOR(p,r))
    • 173 4 27 4 IOR(AND(q,r),NOT(XOR(p,r)))
    • 229 4 27 4 IOR(AND(p,q),NOT(XOR(p,r)))
  53. cellular automata class: [76 205]
    • 76 3 20 2 AND(NOT(AND(p,r)),q)
    • 205 3 20 2 IOR(NOT(IOR(p,r)),q)
  54. cellular automata class: [77]
    • 77 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),r))
  55. cellular automata class: [78 92 141 197]
    • 78 4 22 2 XOR(IOR(XOR(p,q),r),p)
    • 92 4 22 2 XOR(IOR(XOR(q,r),p),r)
    • 141 4 27 3 IOR(AND(q,r),NOT(IOR(p,r)))
    • 197 4 27 3 IOR(AND(p,q),NOT(IOR(p,r)))
  56. cellular automata class: [90 165]
    • 90 2 8 1 XOR(p,r)
    • 165 2 13 2 NOT(XOR(p,r))
  57. cellular automata class: [94 133]
    • 94 4 27 4 IOR(AND(NOT(p),q),XOR(p,r))
    • 133 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(p,r)))
  58. cellular automata class: [104 233]
    • 104 5 29 3 AND(IOR(p,q),XOR(AND(p,q),r))
    • 233 5 34 4 IOR(AND(p,q),NOT(XOR(IOR(p,q),r)))
  59. cellular automata class: [105]
    • 105 3 20 2 NOT(XOR(XOR(p,q),r))
  60. cellular automata class: [106 120 169 225]
    • 106 3 15 2 XOR(AND(p,q),r)
    • 120 3 15 2 XOR(AND(q,r),p)
    • 169 3 20 3 NOT(XOR(IOR(p,q),r))
    • 225 3 20 3 NOT(XOR(IOR(q,r),p))
  61. cellular automata class: [108 201]
    • 108 3 15 2 XOR(AND(p,r),q)
    • 201 3 20 3 NOT(XOR(IOR(p,r),q))
  62. cellular automata class: [110 124 137 193]
    • 110 4 27 4 IOR(AND(NOT(p),q),XOR(q,r))
    • 124 4 27 4 IOR(AND(NOT(r),p),XOR(p,q))
    • 137 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(q,r)))
    • 193 4 32 4 AND(IOR(NOT(r),p),NOT(XOR(p,q)))
  63. cellular automata class: [122 161]
    • 122 4 27 4 IOR(AND(NOT(q),p),XOR(p,r))
    • 161 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(p,r)))
  64. cellular automata class: [126 129]
    • 126 4 22 2 IOR(XOR(p,q),XOR(p,r))
    • 129 4 27 3 NOT(IOR(XOR(p,q),XOR(p,r)))
  65. cellular automata class: [128 254]
    • 128 3 15 1 AND(AND(p,q),r)
    • 254 3 15 1 IOR(IOR(p,q),r)
  66. cellular automata class: [130 144 190 246]
    • 130 3 20 3 AND(NOT(XOR(p,q)),r)
    • 144 3 20 3 AND(NOT(XOR(q,r)),p)
    • 190 3 15 2 IOR(XOR(p,q),r)
    • 246 3 15 2 IOR(XOR(q,r),p)
  67. cellular automata class: [132 222]
    • 132 3 20 3 AND(NOT(XOR(p,r)),q)
    • 222 3 15 2 IOR(XOR(p,r),q)
  68. cellular automata class: [134 148 158 214]
    • 134 5 29 3 AND(IOR(q,r),XOR(XOR(p,q),r))
    • 148 5 29 3 AND(IOR(p,q),XOR(XOR(p,q),r))
    • 158 5 29 3 IOR(AND(q,r),XOR(IOR(q,r),p))
    • 214 5 29 3 IOR(AND(p,q),XOR(IOR(p,q),r))
  69. cellular automata class: [136 192 238 252]
    • 136 2 8 1 AND(q,r)
    • 192 2 8 1 AND(p,q)
    • 238 2 8 1 IOR(q,r)
    • 252 2 8 1 IOR(p,q)
  70. cellular automata class: [138 174 208 244]
    • 138 3 20 3 AND(IOR(NOT(p),q),r)
    • 174 3 20 3 IOR(AND(NOT(p),q),r)
    • 208 3 20 3 AND(IOR(NOT(r),q),p)
    • 244 3 20 3 IOR(AND(NOT(r),q),p)
  71. cellular automata class: [140 196 206 220]
    • 140 3 20 3 AND(IOR(NOT(p),r),q)
    • 196 3 20 3 AND(IOR(NOT(r),p),q)
    • 206 3 20 3 IOR(AND(NOT(p),r),q)
    • 220 3 20 3 IOR(AND(NOT(r),p),q)
  72. cellular automata class: [142 212]
    • 142 5 29 2 XOR(AND(XOR(p,q),XOR(q,r)),r)
    • 212 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),q)
  73. cellular automata class: [146 182]
    • 146 5 29 3 AND(IOR(p,r),XOR(XOR(p,q),r))
    • 182 5 29 3 IOR(AND(p,r),XOR(IOR(p,r),q))
  74. cellular automata class: [150]
    • 150 3 15 1 XOR(XOR(p,q),r)
  75. cellular automata class: [152 188 194 230]
    • 152 4 27 4 AND(IOR(p,q),NOT(XOR(q,r)))
    • 188 4 22 3 IOR(AND(p,r),XOR(p,q))
    • 194 4 27 4 AND(IOR(p,r),NOT(XOR(p,q)))
    • 230 4 22 3 IOR(AND(p,q),XOR(q,r))
  76. cellular automata class: [154 166 180 210]
    • 154 3 20 3 XOR(AND(NOT(q),p),r)
    • 166 3 20 3 XOR(AND(NOT(p),q),r)
    • 180 3 20 3 XOR(AND(NOT(r),q),p)
    • 210 3 20 3 XOR(AND(NOT(q),r),p)
  77. cellular automata class: [156 198]
    • 156 3 20 3 XOR(AND(NOT(r),p),q)
    • 198 3 20 3 XOR(AND(NOT(p),r),q)
  78. cellular automata class: [160 250]
    • 160 2 8 1 AND(p,r)
    • 250 2 8 1 IOR(p,r)
  79. cellular automata class: [162 176 186 242]
    • 162 3 20 3 AND(IOR(NOT(q),p),r)
    • 176 3 20 3 AND(IOR(NOT(q),r),p)
    • 186 3 20 3 IOR(AND(NOT(q),p),r)
    • 242 3 20 3 IOR(AND(NOT(q),r),p)
  80. cellular automata class: [164 218]
    • 164 4 27 4 AND(IOR(p,q),NOT(XOR(p,r)))
    • 218 4 22 3 IOR(AND(p,q),XOR(p,r))
  81. cellular automata class: [168 224 234 248]
    • 168 3 15 2 AND(IOR(p,q),r)
    • 224 3 15 2 AND(IOR(q,r),p)
    • 234 3 15 2 IOR(AND(p,q),r)
    • 248 3 15 2 IOR(AND(q,r),p)
  82. cellular automata class: [170 240]
    • 170 1 1 0 r
    • 240 1 1 0 p
  83. cellular automata class: [172 202 216 228]
    • 172 4 22 2 XOR(AND(XOR(q,r),p),q)
    • 202 4 22 2 XOR(AND(XOR(q,r),p),r)
    • 216 4 22 2 XOR(AND(XOR(p,q),r),p)
    • 228 4 22 2 XOR(AND(XOR(p,q),r),q)
  84. cellular automata class: [178]
    • 178 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),r)
  85. cellular automata class: [184 226]
    • 184 4 22 2 XOR(AND(XOR(p,r),q),p)
    • 226 4 22 2 XOR(AND(XOR(p,r),q),r)
  86. cellular automata class: [200 236]
    • 200 3 15 2 AND(IOR(p,r),q)
    • 236 3 15 2 IOR(AND(p,r),q)
  87. cellular automata class: [204]
    • 204 1 1 0 q
  88. cellular automata class: [232]
    • 232 5 29 2 AND(IOR(AND(p,q),r),IOR(p,q))
I will make some similar reports on ternary 1D outer-totalistic cellular automata.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » January 7th, 2017, 1:58 pm

Naszvadi wrote:A not-too-subtle dump for all elementary 1D CA - a minial logical expression generator script for each rule - independent from golly:

Code: Select all

python cr@p
And the results are (rule/number of substitutions/expression length in characters/distinct gates/expression):

Code: Select all

rule list
Updated the code - quality, license and weather haven't been changed (yet)

Code: Select all

#! /usr/bin/env python
# The same description and "license" as in the previous version

# globalis 1, we like antipatterns
toredek = [
'p',
'q',
'r',
'AND(y,y)',
'IOR(y,y)',
'NOT(y)',
'XOR(y,y)',
'AND(y,y,y)',
'IOR(y,y,y)',
'XOR(y,y,y)'
,'AND(y,y,y,y)',
'IOR(y,y,y,y)',
'XOR(y,y,y,y)'
]

# globalis 2
kepletek = ['0','1']

# globalis 3
eredmeny = [(0,100,100,100,'')]*256

def AND(x,y,z=1,w=1):
  return(x&y&z&w)

def IOR(x,y,z=0,w=0):
  return(x|y|z|w)

def NOT(x):
  return(1-x)

def XOR(x,y,z=0,w=0):
  return(x^y^z^w)

def rekurziv(argum='x',melyseg=10,valtozo=0):
  # ez a lenyeg, amig van x az argumentumban, behelyettesit
  # global valtozoba general listat
  if 'x' in argum:
    if (valtozo<7) and (melyseg>0):
      for i in toredek:
        seged=argum.replace('x',i,1).replace('y','x')
        if    (not 'p,A' in seged) \
          and (not 'q,A' in seged) \
          and (not 'r,A' in seged) \
          and (not 'p,N' in seged) \
          and (not 'q,N' in seged) \
          and (not 'r,N' in seged) \
          and (not 'p,I' in seged) \
          and (not 'q,I' in seged) \
          and (not 'r,I' in seged) \
          and (not 'p,X' in seged) \
          and (not 'q,X' in seged) \
          and (not 'r,X' in seged) \
          and (not 'r,p' in seged) \
          and (not 'r,q' in seged) \
          and (not 'q,p' in seged) \
          and (not 'NOT(NOT(' in seged) \
          and (not 'AND(AND(' in seged) \
          and (not 'IOR(IOR(' in seged) \
          and (not 'XOR(XOR(' in seged) \
          :
          rekurziv(seged,melyseg-1,valtozo+(i in ['p','q','r']))
  elif (not 'r,p' in argum) \
       and (not 'r,q' in argum) and (not 'q,p' in argum):
    kepletek.append(argum)

# void main()
rekurziv('x',10,0)

for i in kepletek:
  spaceid=0
  functypes=0
  if 'AND' in i: functypes+=1
  if 'IOR' in i: functypes+=1
  if 'NOT' in i: functypes+=1
  if 'XOR' in i: functypes+=1
  for (p,q,r) in ((1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0)):
    spaceid=spaceid<<1|eval('+'+i)
  if eredmeny[spaceid][1]==i.count('p')+i.count('q')+i.count('r'):
    if eredmeny[spaceid][2]==len(i):
      if eredmeny[spaceid][3]==functypes:
        if eredmeny[spaceid][4]>=i:
          eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
      elif eredmeny[spaceid][3]>functypes:
        eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
    elif eredmeny[spaceid][2]>len(i):
      eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)
  elif eredmeny[spaceid][1]>i.count('p')+i.count('q')+i.count('r'):
    eredmeny[spaceid]=(spaceid,i.count('p')+i.count('q')+i.count('r'),len(i),functypes,i)

for i in eredmeny:
  print "%d %d %d %d %s" % i
And the generated rule list now simplified, allows at most 4 arguments in AND, IOR and XOR functions:

Code: Select all

$ time ./holy_cr4p_diz_iz_a_generator.py
0 0 1 0 0
1 3 15 2 NOT(IOR(p,q,r))
2 3 20 2 AND(NOT(p),NOT(q),r)
3 2 13 2 NOT(IOR(p,q))
4 3 20 2 AND(NOT(p),NOT(r),q)
5 2 13 2 NOT(IOR(p,r))
6 3 20 3 AND(NOT(p),XOR(q,r))
7 3 20 3 NOT(IOR(AND(q,r),p))
8 3 15 2 AND(NOT(p),q,r)
9 3 20 3 NOT(IOR(XOR(q,r),p))
10 2 13 2 AND(NOT(p),r)
11 3 25 3 AND(IOR(NOT(q),r),NOT(p))
12 2 13 2 AND(NOT(p),q)
13 3 25 3 AND(IOR(NOT(r),q),NOT(p))
14 3 20 3 AND(IOR(q,r),NOT(p))
15 1 6 1 NOT(p)
16 3 20 2 AND(NOT(q),NOT(r),p)
17 2 13 2 NOT(IOR(q,r))
18 3 20 3 AND(NOT(q),XOR(p,r))
19 3 20 3 NOT(IOR(AND(p,r),q))
20 3 20 3 AND(NOT(r),XOR(p,q))
21 3 20 3 NOT(IOR(AND(p,q),r))
22 5 29 3 AND(NOT(AND(p,q)),XOR(p,q,r))
23 5 34 3 NOT(AND(IOR(AND(p,q),r),IOR(p,q)))
24 4 22 2 AND(XOR(p,q),XOR(p,r))
25 4 27 4 NOT(IOR(AND(p,q),XOR(q,r)))
26 4 22 3 XOR(IOR(AND(p,q),r),p)
27 4 27 3 NOT(XOR(AND(XOR(p,q),r),q))
28 4 22 3 XOR(IOR(AND(p,r),q),p)
29 4 27 3 NOT(XOR(AND(XOR(p,r),q),r))
30 3 15 2 XOR(IOR(q,r),p)
31 3 20 3 NOT(AND(IOR(q,r),p))
32 3 15 2 AND(NOT(q),p,r)
33 3 20 3 NOT(IOR(XOR(p,r),q))
34 2 13 2 AND(NOT(q),r)
35 3 25 3 AND(IOR(NOT(p),r),NOT(q))
36 4 22 2 AND(XOR(p,q),XOR(q,r))
37 4 27 4 NOT(IOR(AND(p,q),XOR(p,r)))
38 4 22 3 XOR(IOR(AND(p,q),r),q)
39 4 27 3 NOT(XOR(AND(XOR(p,q),r),p))
40 3 15 2 AND(XOR(p,q),r)
41 5 29 4 NOT(IOR(AND(p,q),XOR(p,q,r)))
42 3 20 2 AND(NOT(AND(p,q)),r)
43 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),q))
44 4 22 3 AND(IOR(q,r),XOR(p,q))
45 3 20 3 XOR(IOR(NOT(r),q),p)
46 4 22 2 XOR(IOR(XOR(p,r),q),p)
47 3 25 3 IOR(AND(NOT(q),r),NOT(p))
48 2 13 2 AND(NOT(q),p)
49 3 25 3 AND(IOR(NOT(r),p),NOT(q))
50 3 20 3 AND(IOR(p,r),NOT(q))
51 1 6 1 NOT(q)
52 4 22 3 XOR(IOR(AND(q,r),p),q)
53 4 27 3 NOT(XOR(AND(XOR(q,r),p),r))
54 3 15 2 XOR(IOR(p,r),q)
55 3 20 3 NOT(AND(IOR(p,r),q))
56 4 22 3 AND(IOR(p,r),XOR(p,q))
57 3 20 3 XOR(IOR(NOT(r),p),q)
58 4 22 2 XOR(IOR(XOR(q,r),p),q)
59 3 25 3 IOR(AND(NOT(p),r),NOT(q))
60 2 8 1 XOR(p,q)
61 4 27 3 IOR(NOT(IOR(p,r)),XOR(p,q))
62 4 27 4 IOR(AND(NOT(p),r),XOR(p,q))
63 2 13 2 NOT(AND(p,q))
64 3 15 2 AND(NOT(r),p,q)
65 3 20 3 NOT(IOR(XOR(p,q),r))
66 4 22 2 AND(XOR(p,r),XOR(q,r))
67 4 27 4 NOT(IOR(AND(p,r),XOR(p,q)))
68 2 13 2 AND(NOT(r),q)
69 3 25 3 AND(IOR(NOT(p),q),NOT(r))
70 4 22 3 XOR(IOR(AND(p,r),q),r)
71 4 27 3 NOT(XOR(AND(XOR(p,r),q),p))
72 3 15 2 AND(XOR(p,r),q)
73 5 29 4 NOT(IOR(AND(p,r),XOR(p,q,r)))
74 4 22 3 AND(IOR(q,r),XOR(p,r))
75 3 20 3 XOR(IOR(NOT(q),r),p)
76 3 20 2 AND(NOT(AND(p,r)),q)
77 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(p,r)),r))
78 4 22 2 XOR(IOR(XOR(p,q),r),p)
79 3 25 3 IOR(AND(NOT(r),q),NOT(p))
80 2 13 2 AND(NOT(r),p)
81 3 25 3 AND(IOR(NOT(q),p),NOT(r))
82 4 22 3 XOR(IOR(AND(q,r),p),r)
83 4 27 3 NOT(XOR(AND(XOR(q,r),p),q))
84 3 20 3 AND(IOR(p,q),NOT(r))
85 1 6 1 NOT(r)
86 3 15 2 XOR(IOR(p,q),r)
87 3 20 3 NOT(AND(IOR(p,q),r))
88 4 22 3 AND(IOR(p,q),XOR(p,r))
89 3 20 3 XOR(IOR(NOT(q),p),r)
90 2 8 1 XOR(p,r)
91 4 27 3 IOR(NOT(IOR(p,q)),XOR(p,r))
92 4 22 2 XOR(IOR(XOR(q,r),p),r)
93 3 25 3 IOR(AND(NOT(p),q),NOT(r))
94 4 27 4 IOR(AND(NOT(p),q),XOR(p,r))
95 2 13 2 NOT(AND(p,r))
96 3 15 2 AND(XOR(q,r),p)
97 5 29 4 NOT(IOR(AND(q,r),XOR(p,q,r)))
98 4 22 3 AND(IOR(p,r),XOR(q,r))
99 3 20 3 XOR(IOR(NOT(p),r),q)
100 4 22 3 AND(IOR(p,q),XOR(q,r))
101 3 20 3 XOR(IOR(NOT(p),q),r)
102 2 8 1 XOR(q,r)
103 4 27 3 IOR(NOT(IOR(p,q)),XOR(q,r))
104 5 29 3 AND(IOR(p,q),XOR(AND(p,q),r))
105 3 15 2 NOT(XOR(p,q,r))
106 3 15 2 XOR(AND(p,q),r)
107 5 29 4 NOT(AND(IOR(p,q),XOR(p,q,r)))
108 3 15 2 XOR(AND(p,r),q)
109 5 29 4 NOT(AND(IOR(p,r),XOR(p,q,r)))
110 4 27 4 IOR(AND(NOT(p),q),XOR(q,r))
111 3 20 3 IOR(NOT(p),XOR(q,r))
112 3 20 2 AND(NOT(AND(q,r)),p)
113 5 34 3 NOT(XOR(AND(XOR(p,q),XOR(q,r)),r))
114 4 22 2 XOR(IOR(XOR(p,q),r),q)
115 3 25 3 IOR(AND(NOT(r),p),NOT(q))
116 4 22 2 XOR(IOR(XOR(p,r),q),r)
117 3 25 3 IOR(AND(NOT(q),p),NOT(r))
118 4 27 4 IOR(AND(NOT(q),p),XOR(q,r))
119 2 13 2 NOT(AND(q,r))
120 3 15 2 XOR(AND(q,r),p)
121 5 29 4 NOT(AND(IOR(q,r),XOR(p,q,r)))
122 4 27 4 IOR(AND(NOT(q),p),XOR(p,r))
123 3 20 3 IOR(NOT(q),XOR(p,r))
124 4 27 4 IOR(AND(NOT(r),p),XOR(p,q))
125 3 20 3 IOR(NOT(r),XOR(p,q))
126 4 22 2 IOR(XOR(p,q),XOR(p,r))
127 3 15 2 NOT(AND(p,q,r))
128 3 10 1 AND(p,q,r)
129 4 27 3 NOT(IOR(XOR(p,q),XOR(p,r)))
130 3 20 3 AND(NOT(XOR(p,q)),r)
131 4 32 4 AND(IOR(NOT(p),r),NOT(XOR(p,q)))
132 3 20 3 AND(NOT(XOR(p,r)),q)
133 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(p,r)))
134 5 24 3 AND(IOR(q,r),XOR(p,q,r))
135 3 20 3 NOT(XOR(AND(q,r),p))
136 2 8 1 AND(q,r)
137 4 32 4 AND(IOR(NOT(p),q),NOT(XOR(q,r)))
138 3 20 3 AND(IOR(NOT(p),q),r)
139 4 27 3 IOR(AND(q,r),NOT(IOR(p,q)))
140 3 20 3 AND(IOR(NOT(p),r),q)
141 4 27 3 IOR(AND(q,r),NOT(IOR(p,r)))
142 5 29 2 XOR(AND(XOR(p,q),XOR(q,r)),r)
143 3 20 3 IOR(AND(q,r),NOT(p))
144 3 20 3 AND(NOT(XOR(q,r)),p)
145 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(q,r)))
146 5 24 3 AND(IOR(p,r),XOR(p,q,r))
147 3 20 3 NOT(XOR(AND(p,r),q))
148 5 24 3 AND(IOR(p,q),XOR(p,q,r))
149 3 20 3 NOT(XOR(AND(p,q),r))
150 3 10 1 XOR(p,q,r)
151 5 29 3 IOR(NOT(IOR(p,q)),XOR(p,q,r))
152 4 27 4 AND(IOR(p,q),NOT(XOR(q,r)))
153 2 13 2 NOT(XOR(q,r))
154 3 20 3 XOR(AND(NOT(q),p),r)
155 4 27 4 NOT(AND(IOR(p,q),XOR(q,r)))
156 3 20 3 XOR(AND(NOT(r),p),q)
157 4 27 4 NOT(AND(IOR(p,r),XOR(q,r)))
158 5 24 3 IOR(AND(q,r),XOR(p,q,r))
159 3 20 3 NOT(AND(XOR(q,r),p))
160 2 8 1 AND(p,r)
161 4 32 4 AND(IOR(NOT(q),p),NOT(XOR(p,r)))
162 3 20 3 AND(IOR(NOT(q),p),r)
163 4 27 3 IOR(AND(p,r),NOT(IOR(p,q)))
164 4 27 4 AND(IOR(p,q),NOT(XOR(p,r)))
165 2 13 2 NOT(XOR(p,r))
166 3 20 3 XOR(AND(NOT(p),q),r)
167 4 27 4 NOT(AND(IOR(p,q),XOR(p,r)))
168 3 15 2 AND(IOR(p,q),r)
169 3 20 3 NOT(XOR(IOR(p,q),r))
170 1 1 0 r
171 3 20 2 IOR(NOT(IOR(p,q)),r)
172 4 22 2 XOR(AND(XOR(q,r),p),q)
173 4 27 4 IOR(AND(q,r),NOT(XOR(p,r)))
174 3 20 3 IOR(AND(NOT(p),q),r)
175 2 13 2 IOR(NOT(p),r)
176 3 20 3 AND(IOR(NOT(q),r),p)
177 4 27 3 IOR(AND(p,r),NOT(IOR(q,r)))
178 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),r)
179 3 20 3 IOR(AND(p,r),NOT(q))
180 3 20 3 XOR(AND(NOT(r),q),p)
181 4 27 4 NOT(AND(IOR(q,r),XOR(p,r)))
182 5 24 3 IOR(AND(p,r),XOR(p,q,r))
183 3 20 3 NOT(AND(XOR(p,r),q))
184 4 22 2 XOR(AND(XOR(p,r),q),p)
185 4 27 4 IOR(AND(p,r),NOT(XOR(q,r)))
186 3 20 3 IOR(AND(NOT(q),p),r)
187 2 13 2 IOR(NOT(q),r)
188 4 22 3 IOR(AND(p,r),XOR(p,q))
189 4 27 3 IOR(NOT(XOR(p,r)),XOR(p,q))
190 3 15 2 IOR(XOR(p,q),r)
191 3 20 2 IOR(NOT(p),NOT(q),r)
192 2 8 1 AND(p,q)
193 4 32 4 AND(IOR(NOT(r),p),NOT(XOR(p,q)))
194 4 27 4 AND(IOR(p,r),NOT(XOR(p,q)))
195 2 13 2 NOT(XOR(p,q))
196 3 20 3 AND(IOR(NOT(r),p),q)
197 4 27 3 IOR(AND(p,q),NOT(IOR(p,r)))
198 3 20 3 XOR(AND(NOT(p),r),q)
199 4 27 4 NOT(AND(IOR(p,r),XOR(p,q)))
200 3 15 2 AND(IOR(p,r),q)
201 3 20 3 NOT(XOR(IOR(p,r),q))
202 4 22 2 XOR(AND(XOR(q,r),p),r)
203 4 27 4 IOR(AND(q,r),NOT(XOR(p,q)))
204 1 1 0 q
205 3 20 2 IOR(NOT(IOR(p,r)),q)
206 3 20 3 IOR(AND(NOT(p),r),q)
207 2 13 2 IOR(NOT(p),q)
208 3 20 3 AND(IOR(NOT(r),q),p)
209 4 27 3 IOR(AND(p,q),NOT(IOR(q,r)))
210 3 20 3 XOR(AND(NOT(q),r),p)
211 4 27 4 NOT(AND(IOR(q,r),XOR(p,q)))
212 5 29 2 XOR(AND(XOR(p,q),XOR(p,r)),q)
213 3 20 3 IOR(AND(p,q),NOT(r))
214 5 24 3 IOR(AND(p,q),XOR(p,q,r))
215 3 20 3 NOT(AND(XOR(p,q),r))
216 4 22 2 XOR(AND(XOR(p,q),r),p)
217 4 27 4 IOR(AND(p,q),NOT(XOR(q,r)))
218 4 22 3 IOR(AND(p,q),XOR(p,r))
219 4 27 3 IOR(NOT(XOR(p,q)),XOR(p,r))
220 3 20 3 IOR(AND(NOT(r),p),q)
221 2 13 2 IOR(NOT(r),q)
222 3 15 2 IOR(XOR(p,r),q)
223 3 20 2 IOR(NOT(p),NOT(r),q)
224 3 15 2 AND(IOR(q,r),p)
225 3 20 3 NOT(XOR(IOR(q,r),p))
226 4 22 2 XOR(AND(XOR(p,r),q),r)
227 4 27 4 IOR(AND(p,r),NOT(XOR(p,q)))
228 4 22 2 XOR(AND(XOR(p,q),r),q)
229 4 27 4 IOR(AND(p,q),NOT(XOR(p,r)))
230 4 22 3 IOR(AND(p,q),XOR(q,r))
231 4 27 3 IOR(NOT(XOR(p,q)),XOR(q,r))
232 5 29 2 AND(IOR(AND(p,q),r),IOR(p,q))
233 5 29 4 IOR(AND(p,q),NOT(XOR(p,q,r)))
234 3 15 2 IOR(AND(p,q),r)
235 3 20 3 IOR(NOT(XOR(p,q)),r)
236 3 15 2 IOR(AND(p,r),q)
237 3 20 3 IOR(NOT(XOR(p,r)),q)
238 2 8 1 IOR(q,r)
239 3 15 2 IOR(NOT(p),q,r)
240 1 1 0 p
241 3 20 2 IOR(NOT(IOR(q,r)),p)
242 3 20 3 IOR(AND(NOT(q),r),p)
243 2 13 2 IOR(NOT(q),p)
244 3 20 3 IOR(AND(NOT(r),q),p)
245 2 13 2 IOR(NOT(r),p)
246 3 15 2 IOR(XOR(q,r),p)
247 3 20 2 IOR(NOT(q),NOT(r),p)
248 3 15 2 IOR(AND(q,r),p)
249 3 20 3 IOR(NOT(XOR(q,r)),p)
250 2 8 1 IOR(p,r)
251 3 15 2 IOR(NOT(q),p,r)
252 2 8 1 IOR(p,q)
253 3 15 2 IOR(NOT(r),p,q)
254 3 10 1 IOR(p,q,r)
255 0 1 0 1
Time:

Code: Select all

real	59m24.143s
user	59m23.414s

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » January 8th, 2017, 3:35 pm

Naszvadi wrote:
wildmyron wrote:...
Naszvadi wrote:...
...
...
And an example pattern (repeats every 7th gens.):

Code: Select all

x = 41, y = 3, rule = rule110in2d7n
ACEBCEBDEBDFBDEACFACFBCFBDFBCEADEADFADFBD$
F.......................................F$
DBFDAFDAEDAECBFDBFCBFCAFCAEDBFDBEDBECBECA$
...
Here is a spiral rule, of which any kind of 1D CA could be embedded into a specific 2D outer totalistic Neumann-nghbr rule:

Code: Select all

@RULE spiralgrowth1

2d spiral growth, for creating a spacefilling wire fast!
By NASZVADI P., 2016, 2017

@TABLE

# Format: C,N,E,S,W,C'

n_states:8
neighborhood:vonNeumann
symmetries:permute

# Meanings:
# 0 = background
# 1 = nuclear bomb
# 2 = wall
# 3 = signtail
# 4 = wallhead
# 5 = signhead
# 6 = signhead in space
# 7- = embedded 1D CA or Turing-machine

var a={0,1,2,3,4,5,6,7}
var b={0,1,2,3,4,5,6,7}
var c={0,1,2,3,4,5,6,7}
var d={0,1,2,3,4,5,6,7}
var e={1,2,3,4,5,6,7}

1,a,b,c,d,0
e,1,b,c,d,1
3,a,b,c,d,7
4,3,a,b,c,2
5,a,b,c,d,3
6,a,b,c,d,3
0,4,4,0,0,2
0,5,0,0,0,6
0,6,0,0,0,4
0,4,6,0,0,4
0,2,6,0,0,5
0,4,5,a,b,4
0,2,5,a,b,5
0,5,0,0,0,4

@COLORS

1 0 255 255
2 255 64 0
3 96 255 96
4 255 0 0
5 0 192 0
6 0 255 255
7 0 0 255
An example pattern:

Code: Select all

x = 6, y = 3, rule = spiralgrowth1
.DBBBB$
ECGGCE$
BBBBD!
The rule transition function is unoptimized, TBD. A W54, a W73 and a W110 demo - coming soon! The 7state-embedding of W110 can be merged to states 7 and above, FYI. Enjoy!

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Embedding Rule-110 into a 2D totalistic Neumann-nbhr. CA

Post by Naszvadi » July 25th, 2017, 9:02 am

Another way to simulate amphirical Wolfram rules with Life-like isotropic rules including odd ones:

"bars":
B3i6i/S2i:B36/S2:T[n],1

Code: Select all

abcdefghijkl +---+---+---+---+---+---+---+---+
abcdefghijkl |111|110|101|100|011|010|001|000|
abcdefghijkl +---+---+---+---+---+---+---+---+
abcdefghijkl |S8 |S5i|B6i|B3i| / |S2i| / |B0 |
abcdefghijkl +---+---+---+---+---+---+---+---+
diagonals:
B2e3ak4eq5c6n/S2n3c4c:T[n]+1,1

Code: Select all

abcdefghijklm +---+---+---+---+---+---+---+---+
bcdefghijklmn |111|110|101|100|011|010|001|000|
cdefghijklmno +---+---+---+---+---+---+---+---+
defghijklmnop |S6n|S6e|B4e|B2e|   |S2n|   |B0 |
efghijklmnopq |S7c|S5a|B5c|B3a| / |S3c| / |B1c|
fghijklmnopqr |S8 |S5k|B6n|B3k|   |S4c|   |B2n|
ghijklmnopqrs |   |S4w|   |B4q|   |   |   |   |
hijklmnopqrst +---+---+---+---+---+---+---+---+
knightpaths:
B1c2a4az5j/S3j4z:T[n]+2,1

Code: Select all

aaabbbcccdddeeefff +---+---+---+---+---+---+---+---+
abbbcccdddeeefffgg |111|110|101|100|011|010|001|000|
bbcccdddeeefffgggh +---+---+---+---+---+---+---+---+
cccdddeeefffggghhh |   |S4a|B4z|B1c|   |S3j|   |   |
cdddeeefffggghhhii |S8 |S6a|B5j|B2a| / |S4z| / |B0 |
ddeeefffggghhhiiij |   |S7c|   |B4a|   |   |   |   |
eeefffggghhhiiijjj +---+---+---+---+---+---+---+---+
thick diagonals:
B1c3a4q/S4q:B134/S4:T[n]+1,1

Code: Select all

aabbccddeeffgghhiijj +---+---+---+---+---+---+---+---+
abbccddeeffgghhiijjk |111|110|101|100|011|010|001|000|
bbccddeeffgghhiijjkk +---+---+---+---+---+---+---+---+
bccddeeffgghhiijjkkl |S8 |S5a|B4q|B1c| / |S4q| / |B0 |
ccddeeffgghhiijjkkll |   |S7c|   |B3a|   |   |   |   |
cddeeffgghhiijjkkllm +---+---+---+---+---+---+---+---+
bars in Neumann rules:
B12/S2V:T[n],1

Code: Select all

abcdefghijkl +---+---+---+---+---+---+---+---+
abcdefghijkl |111|110|101|100|011|010|001|000|
abcdefghijkl +---+---+---+---+---+---+---+---+
abcdefghijkl |S4V|S3V|B2V|B1V| / |S2V| / |B0V|
abcdefghijkl +---+---+---+---+---+---+---+---+
alternating cornered paths:
B1c2a4z5a6e/S2e4z:B12456/S24:T[n*4]+2,2

Code: Select all

aaabcccdeeefggghi +---+---+---+---+---+---+---+---+
abbbcdddefffghhhi |111|110|101|100|011|010|001|000|
abcccdeeefggghiii +---+---+---+---+---+---+---+---+
bbcdddefffghhhijj |   |S7c|B6e|B1c| / |S2e| / |   |
cccdeeefggghiiijk |S8 |S6a|B4z|B2a| / |S4z| / |B0 |
cdddefffghhhijjjk |   |S3a|   |B5a| / |   | / |   |
cdeeefggghiiijkkk +---+---+---+---+---+---+---+---+
I gave for all as an example the W54-equivalent minimal rules, and if there were nontotalistic versions, I gave them too.

Running W54

Code: Select all

x = 0, y = 0, rule = B12456/S24:T44+2,2
2bo$3o!
Now comes W73, an odd one:

Code: Select all

x = 0, y = 0, rule = B0/S5:T47,1
ob2o2b3o!
The Golly version I am using does not support B0 substring in non-totalistic rules, so only "bars" can be used for Wolfram odds' simulation.

There may be typos, errors, any suggestions, corrections are kindly welcome!

Post Reply