ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

So, is Rule 54 universal?

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.

So, is Rule 54 universal?

Postby wwei23 » July 22nd, 2017, 11:25 am

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.
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 62 times

My script:
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:
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.
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 62 times

My script:
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:
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 50 times
User avatar
wwei23
 
Posts: 935
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: So, is Rule 54 universal?

Postby Naszvadi » July 24th, 2017, 6:46 am

wwei23 wrote: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
 
Posts: 302
Joined: May 7th, 2016, 8:53 am

Re: So, is Rule 54 universal?

Postby Naszvadi » July 25th, 2017, 9:06 am

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
 
Posts: 302
Joined: May 7th, 2016, 8:53 am

Re: So, is Rule 54 universal?

Postby Naszvadi » July 29th, 2017, 7:18 am

Naszvadi wrote:
wwei23 wrote: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:

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
Naszvadi
 
Posts: 302
Joined: May 7th, 2016, 8:53 am

Re: So, is Rule 54 universal?

Postby wwei23 » July 29th, 2017, 10:35 am

More soups:
W54 Census Patterns File 4.txt
(152.17 KiB) Downloaded 43 times

The periods of those soups:
W54 Periods 4.txt
(30.65 KiB) Downloaded 41 times

Updating the script again:
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)
   
User avatar
wwei23
 
Posts: 935
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: So, is Rule 54 universal?

Postby Naszvadi » July 30th, 2017, 2:26 pm

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


Let me help you tidying and summarizing a bit:

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:~$
Naszvadi
 
Posts: 302
Joined: May 7th, 2016, 8:53 am

Re: So, is Rule 54 universal?

Postby wwei23 » August 2nd, 2017, 5:32 pm

More soups and the periods:
W54 Patterns 5.txt
(231.7 KiB) Downloaded 42 times
W54 Periods 5.txt
(46.59 KiB) Downloaded 40 times
W54 Patterns 6.txt
(225.11 KiB) Downloaded 42 times
User avatar
wwei23
 
Posts: 935
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: So, is Rule 54 universal?

Postby wwei23 » August 4th, 2017, 9:53 am

(I have to double-post, because 3 is the maximum number of attachments per post.)
W54 Periods 6.txt
(32.64 KiB) Downloaded 41 times
User avatar
wwei23
 
Posts: 935
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe


Return to The Sandbox

Who is online

Users browsing this forum: No registered users and 2 guests

cron