So, is Rule 54 universal?

[wwei23]

As of the time of this writing, Rule 110 and its relatives are the only known universal elementary cellular automata. If Rule 54 is proved universal, then this will be a huge achievement, as Rule 54 is isotropic. Note that my census files are in base 32. When converted into binary, only the last x*y bits are kept, where x and y are the bounding box. Note that here, it is 100*1. And the rule, of course, is W54.
Rule 54 can be emulated with HighLife, a trick I use in my soup-searching script to make it work!
Each bar is a cell in W54.

Code: Select all

x = 99, y = 10, rule = B36/S23:T100,10
o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3b
o3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo
3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo
3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo
3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo
3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo
3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o
3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo
3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bo3bo!

My census file:

W54 Census Patterns File 1.txt

(171.49 KiB) Downloaded 192 times

My script:

Code: Select all

import golly as g
filename = g.opendialog("Open Census File")
g.addlayer()

#Count soups
soups = 0

#Run indefinitely
search = True

while search:
    
    g.new("W54 Pattern")
    g.setrule("B36/S2:T100,1")
    g.select([-50,0,100,1])
    g.randfill(50)
    #All previous patterns
    pp = []
    
    while g.getcells([-50,0,100,1]) not in pp:
    
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Period finder
    
    p = 1
    pp = [g.getcells([-50,0,100,1])]
    g.run(1)
    
    while g.getcells([-50,0,100,1]) not in pp:
        
        p = p + 1
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Someone who plays the celllo
    celllist = g.getcells([-50,0,100,1])
    cellpos = []
    for x in range(0,len(celllist),2):
        
        cellpos.append(celllist[x])
    
    HEX=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"]
    HASH=""
    
    for x in range(-50,50,5):

        number=0
        if x in cellpos:

            number = number + 16

        if x + 1 in cellpos:

            number = number + 8

        if x + 2 in cellpos:

            number = number + 4

        if x + 3 in cellpos:

            number = number + 2

        if x + 4 in cellpos:

            number = number + 1

        HASH = HASH + HEX[number]
        
    f = open(filename,"a")
    f.write("P%s" % p+"\n"+HASH+"\n")
    f.close()
    
    soups = soups + 1

    g.show("Soups searched: %s" % soups)
    

Update:

Code: Select all

import golly as g
filename = g.opendialog("Open Census File")
#If you don't want to analyze the periods, then comment out this line...
periodname = g.opendialog("Open Period File")
g.addlayer()

#Count soups
soups = 0

#Run indefinitely
search = True

while search:
    
    g.new("W54 Pattern")
    g.setrule("B36/S2:T100,1")
    g.select([-50,0,100,1])
    g.randfill(50)
    #All previous patterns
    pp = []
    
    while g.getcells([-50,0,100,1]) not in pp:
    
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Period finder
    
    p = 1
    pp = [g.getcells([-50,0,100,1])]
    g.run(1)
    
    while g.getcells([-50,0,100,1]) not in pp:
        
        p = p + 1
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Someone who plays the celllo
    celllist = g.getcells([-50,0,100,1])
    cellpos = []
    for x in range(0,len(celllist),2):
        
        cellpos.append(celllist[x])
    
    HEX=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"]
    HASH=""
    
    for x in range(-50,50,5):

        number=0
        if x in cellpos:

            number = number + 16

        if x + 1 in cellpos:

            number = number + 8

        if x + 2 in cellpos:

            number = number + 4

        if x + 3 in cellpos:

            number = number + 2

        if x + 4 in cellpos:

            number = number + 1

        HASH = HASH + HEX[number]
        
    f = open(filename,"a")
    f.write("P%s" % p+"\n"+HASH+"\n")
    f.close()

    #...and these lines

    f = open(periodname,"a")
    f.write("P%s" % p+"\n")
    f.close
    
    soups = soups + 1

    g.show("Soups searched: %s" % soups)
    

More soups:
As of the time of this writing, Rule 110 and its relatives are the only known universal elementary cellular automata. If Rule 54 is proved universal, then this will be a huge achievement, as Rule 54 is isotropic. Note that my census files are in base 32. When converted into binary, only the last x*y bits are kept, where x and y are the bounding box. Note that here, it is 100*1. And the rule, of course, is W54.
Rule 54 can be emulated with HighLife, a trick I use in my soup-searching script to make it work!
Each bar is a cell in W54.

Code: Select all

x = 99, y = 10, rule = B36/S23:T100,10
o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3b
o3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo
3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo
3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo
3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo3bo3bo3bo
3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o3bo3bo3bo
3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bo3bo$o
3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo
3bo3bo$o3bo3bo3bo3bo3bo3bo3bobo3bo3bo3bo3bo2bo3bo3bo3bobo3bo3bo3bo3bo
2bo3bo3bo3bo3bo!

My census file:

W54 Census Patterns File 1.txt

(171.49 KiB) Downloaded 192 times

My script:

Code: Select all

import golly as g
filename = g.opendialog("Open Census File")
g.addlayer()

#Count soups
soups = 0

#Run indefinitely
search = True

while search:
    
    g.new("W54 Pattern")
    g.setrule("B36/S2:T100,1")
    g.select([-50,0,100,1])
    g.randfill(50)
    #All previous patterns
    pp = []
    
    while g.getcells([-50,0,100,1]) not in pp:
    
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Period finder
    
    p = 1
    pp = [g.getcells([-50,0,100,1])]
    g.run(1)
    
    while g.getcells([-50,0,100,1]) not in pp:
        
        p = p + 1
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Someone who plays the celllo
    celllist = g.getcells([-50,0,100,1])
    cellpos = []
    for x in range(0,len(celllist),2):
        
        cellpos.append(celllist[x])
    
    HEX=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"]
    HASH=""
    
    for x in range(-50,50,5):

        number=0
        if x in cellpos:

            number = number + 16

        if x + 1 in cellpos:

            number = number + 8

        if x + 2 in cellpos:

            number = number + 4

        if x + 3 in cellpos:

            number = number + 2

        if x + 4 in cellpos:

            number = number + 1

        HASH = HASH + HEX[number]
        
    f = open(filename,"a")
    f.write("P%s" % p+"\n"+HASH+"\n")
    f.close()
    
    soups = soups + 1

    g.show("Soups searched: %s" % soups)
    

Update:

Code: Select all

import golly as g
filename = g.opendialog("Open Census File")
#If you don't want to analyze the periods, then comment out this line...
periodname = g.opendialog("Open Period File")
g.addlayer()

#Count soups
soups = 0

#Run indefinitely
search = True

while search:
    
    g.new("W54 Pattern")
    g.setrule("B36/S2:T100,1")
    g.select([-50,0,100,1])
    g.randfill(50)
    #All previous patterns
    pp = []
    
    while g.getcells([-50,0,100,1]) not in pp:
    
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Period finder
    
    p = 1
    pp = [g.getcells([-50,0,100,1])]
    g.run(1)
    
    while g.getcells([-50,0,100,1]) not in pp:
        
        p = p + 1
        pp.append(g.getcells([-50,0,100,1]))
        g.run(1)
        g.update()
    
    #Someone who plays the celllo
    celllist = g.getcells([-50,0,100,1])
    cellpos = []
    for x in range(0,len(celllist),2):
        
        cellpos.append(celllist[x])
    
    HEX=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"]
    HASH=""
    
    for x in range(-50,50,5):

        number=0
        if x in cellpos:

            number = number + 16

        if x + 1 in cellpos:

            number = number + 8

        if x + 2 in cellpos:

            number = number + 4

        if x + 3 in cellpos:

            number = number + 2

        if x + 4 in cellpos:

            number = number + 1

        HASH = HASH + HEX[number]
        
    f = open(filename,"a")
    f.write("P%s" % p+"\n"+HASH+"\n")
    f.close()

    #...and these lines

    f = open(periodname,"a")
    f.write("P%s" % p+"\n")
    f.close
    
    soups = soups + 1

    g.show("Soups searched: %s" % soups)
    

More soups:

W54 Census Patterns File 2.txt

(53.29 KiB) Downloaded 178 times

[Naszvadi]

As of the time of this writing, Rule 110 and its relatives are the only known universal elementary cellular automata. If Rule 54 is proved universal, then this will be a huge achievement, as Rule 54 is isotropic.
...

Greetings!

W54 had already been "discussed" here: ../forums/viewtopic.php?f=11&t=2598#p38435

What I have to add is about some remarks of mine on the cited paper:
http://uncomp.uwe.ac.uk/genaro/Papers/P ... -R54CA.pdf

Well, on page 12 (111. in original paper), the pull/push reactions including necessary and forbidden glider phases are remained still unclear. It is subtle but important to know for oscillators, for example when constructing a counter. And also the quality of the pictures, so called "figures", they should be only illustrations and a decent formal description of initial generations ought to be included together, but the latter is missing, e.g. fig. 5 on page 5. (104.)

I'd rather use the term "amphirical" instead of "isotropic" for W54, but both seems to be correct.

What's more (not moore): if someone wanted to embed into margolus 1D rules with small number of states, she should be aware about the property that 010 and 101 triplets are assigned to different outcomes according to W54's transition rule. So somehow W54 violates symmetry.

[EDITED #1]
oops, 010 and 101 have the same child.

[Naszvadi]

Anyway, if an amphirical Wolfram automata is universal, will yield a corollary - the corresponding containing isotropic automata would be universal, too. See here some tricks for embedding Wolfram rules: ../forums/viewtopic.php?f=11&t=2598&p=47242#p47242

[Naszvadi]

As of the time of this writing, Rule 110 and its relatives are the only known universal elementary cellular automata. If Rule 54 is proved universal, then this will be a huge achievement, as Rule 54 is isotropic.
...

Greetings!

W54 had already been "discussed" here: ../forums/viewtopic.php?f=11&t=2598#p38435

What I have to add is about some remarks of mine on the cited paper:
http://uncomp.uwe.ac.uk/genaro/Papers/P ... -R54CA.pdf

Well, on page 12 (111. in original paper), the pull/push reactions including necessary and forbidden glider phases are remained still unclear. It is subtle but important to know for oscillators, for example when constructing a counter. And also the quality of the pictures, so called "figures", they should be only illustrations and a decent formal description of initial generations ought to be included together, but the latter is missing, e.g. fig. 5 on page 5. (104.)

I'd rather use the term "amphirical" instead of "isotropic" for W54, but both seems to be correct.

What's more (not moore): if someone wanted to embed into margolus 1D rules with small number of states, she should be aware about the property that 010 and 101 triplets are assigned to different outcomes according to W54's transition rule. So somehow W54 violates symmetry.

[EDITED #1]
oops, 010 and 101 have the same child.

Followup for the so-called article, I've made earlier an 1D Wolfram CA simulator:

Code: Select all

A=0001;B=0111;C=1101 ; ./ca1d1.sh --nodelay --alphabet _1 --rule 54 $A$A$A$B$A$A$C$A$B$B$A$B$C$A$C$B$A$C$C$B$B$B$C$B$C$C$A$A$C$C$C --skip 4 | perl -pe 's/([_1]{4})/$1 eq "___1" ? "A" : $1 eq "_111" ? "B" : "C"/eg'
       0 AAABAACABBABCACBACCBBBCBCCAACCC
       4 AAAABCAAABBAACAAACAABBAACAACCCA

where

• 0001 is assigned to "A"
• 0111 is assigned to "B"
• 1101 is assigned to "C"

An initial generation in a space, which contains only the following upper there sequences, will contain only those too in the following 4*n generations.

Stay tuned!

The transition rule of the contained 3-state CA is:

• AAA A
• AAB A
• AAC C
• ABA A
• ABB A
• ABC A
• ACA A
• ACB A
• ACC C
• BAA B
• BAB B
• BAC A
• BBA B
• BBB B
• BBC B
• BCA A
• BCB A
• BCC C
• CAA A
• CAB A
• CAC C
• CBA A
• CBB A
• CBC A
• CCA A
• CCB A
• CCC C

[wwei23]

More soups:

W54 Census Patterns File 4.txt

(152.17 KiB) Downloaded 176 times

The periods of those soups:

W54 Periods 4.txt

(30.65 KiB) Downloaded 168 times

Updating the script again:

Code: Select all

import golly as g
filename = g.opendialog("Open Census File")
#If you don't want to analyze the periods, then comment out this line...
periodname = g.opendialog("Open Period File")
special = g.opendialog("Open Emergency File")
LENGTH=-1
while LENGTH % 10 != 0:

    LENGTH=int(g.getstring("Supply a torus width divisible by 10","100"))

g.addlayer()

#Count soups
soups = 0

#Run indefinitely
search = True

while search:
    
    g.new("W54 Pattern")
    g.setrule("B36/S2:T"+str(LENGTH)+",1")
    g.select([-LENGTH/2,0,LENGTH,1])
    g.randfill(50)
    #All previous patterns
    pp = []
    
    while g.getcells([-LENGTH/2,0,LENGTH,1]) not in pp:
    
        pp.append(g.getcells([-LENGTH/2,0,LENGTH,1]))
        g.run(1)
        g.update()
    
    #Period finder
    
    p = 1
    pp = [g.getcells([-LENGTH/2,0,LENGTH,1])]
    g.run(1)
    
    while g.getcells([-LENGTH/2,0,LENGTH,1]) not in pp:
        
        p = p + 1
        pp.append(g.getcells([-LENGTH/2,0,LENGTH,1]))
        g.run(1)
        g.update()
    
    #Someone who plays the celllo
    celllist = g.getcells([-LENGTH/2,0,LENGTH,1])
    cellpos = []
    for x in range(0,len(celllist),2):
        
        cellpos.append(celllist[x])
    
    HEX=["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"]
    HASH=""
    
    for x in range(-LENGTH/2,LENGTH/2,5):

        number=0
        if x in cellpos:

            number = number + 16

        if x + 1 in cellpos:

            number = number + 8

        if x + 2 in cellpos:

            number = number + 4

        if x + 3 in cellpos:

            number = number + 2

        if x + 4 in cellpos:

            number = number + 1

        HASH = HASH + HEX[number]
        
    f = open(filename,"a")
    f.write("P%s" % p+"\n"+HASH+"\n")
    f.close()

    #...and these lines

    f = open(periodname,"a")
    f.write("P%s" % p+"\n")
    f.close

    if (p != 4) and (p != 32) and (p < 100):

        f = open(special,"a")
        f.write("P%s" % p+"\n"+HASH+"\n")
        f.close()
    
    soups = soups + 1

    g.show("Soups searched: %s" % soups)
    

[Naszvadi]

...
The periods of those soups:
/messy attachment/
...

Let me help you tidying and summarizing a bit:

Code: Select all

user@errorlevel:0:~$ sort -n -tP -k2,2 /tmp/W54\ Periods\ 4.txt | uniq -c
      1 
   2390 P4
     34 P32
      8 P100
     18 P104
   1112 P120
      1 P152
     21 P208
      4 P326
      3 P392
      2 P706
      2 P1550
      2 P1650
      1 P1700
    568 P3200
     16 P3300
      1 P3500
    493 P6100
     90 P6300
     56 P6500
      8 P8700
     25 P8900
      1 P12700
      8 P19076
    566 P91900
user@errorlevel:0:~$

[wwei23]

More soups and the periods:

W54 Patterns 5.txt

(231.7 KiB) Downloaded 176 times

W54 Periods 5.txt

(46.59 KiB) Downloaded 173 times

W54 Patterns 6.txt

(225.11 KiB) Downloaded 168 times

[wwei23]

(I have to double-post, because 3 is the maximum number of attachments per post.)

W54 Periods 6.txt

(32.64 KiB) Downloaded 183 times