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

Universal construction of complex patterns from 1 cell

For discussion of other cellular automata.

Universal construction of complex patterns from 1 cell

Postby blah » September 11th, 2017, 9:32 am

There are a lot of RuleLoader rules (proof somewhere here). If we take the binary logarithm of the amount of rules, we can basically conclude, though simplified, that we can encode 4 billion terabytes of information in one rule. We can thus have a significant ROM built into the ruletable itself.

Say you have a cell, O (for origin), which is a cell of state 1 surrounded by state 0. Counter cells then appear around the cell, which then count up through all their possible combinations, thus meaning that O is exposed to countless neighbourhood conditions. Each condition could make O take a certain state, which would have the effect of reading a ROM to the outside world.

As such, it is possible to build a 1-cell constructor for basically any arbitrary pattern. Here's one I prepared earlier (this is a rule):
monalisa.txt.zip
(169.04 KiB) Downloaded 34 times

Run it with this pattern:
x = 1, y = 1, rule = BLAHMONALISA
A!


Does anyone find this idea interesting or useful? I don't know if it really has any significant implications; I guess it might be nice as an example pattern in Golly, though there is plenty of room for optimisation, including an idea I had that would probably make it twice as fast. Also, please tell me if this idea has been discussed before.
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby Saka » September 11th, 2017, 9:42 am

I have been thinking about this since starting to learn RuleLoader, but as the person that I am, I'm too lazy to make these :P

Do you have a script or something to make these?
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2178
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 11th, 2017, 9:48 am

Saka wrote:I have been thinking about this since starting to learn RuleLoader, but as the person that I am, I'm too lazy to make these :P

So you came up with the idea of generating complex patterns from a single cell using counters, or are you speaking more generally?
Saka wrote:Do you have a script or something to make these?

I wrote a program in C++ to take an XPM and convert it to a set of transitions, and prepend the rule file itself to it, thus generating the version of the rule with the ROM of the picture built into it.
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby Saka » September 11th, 2017, 9:50 am

blah wrote:
Saka wrote:I have been thinking about this since starting to learn RuleLoader, but as the person that I am, I'm too lazy to make these :P

So you came up with the idea of generating complex patterns from a single cell using counters, or are you speaking more generally?

I was thinking of generating a painting with cell-specific instructions and stuff, starting from 1 cell.
blah wrote:
Saka wrote:Do you have a script or something to make these?

I wrote a program in C++ to take an XPM and convert it to a set of transitions, and prepend the rule file itself to it, thus generating the version of the rule with the ROM of the picture built into it.

Please share!
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2178
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 11th, 2017, 9:58 am

Saka wrote:Please share!

Sadly, it requires quite a bit of minimal configuration and tweaking, and it would take a while to explain, so I might as well spend that effort writing a program which is simpler to use rather than explaining how to use the hacked-together .c++ file that I wrote over the course of ~5 hours. Plus, unless you want to make a two-colour image, you'd have to manually write all the colours down; that's what I did with the mona lisa.

Saka wrote:I was thinking of generating a painting with cell-specific instructions and stuff, starting from 1 cell.

How detailed was that idea? Did you image it having a stationary core that all the signals came out of, like my implementation?
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby Saka » September 11th, 2017, 10:04 am

blah wrote:
Saka wrote:Please share!

Sadly, it requires quite a bit of minimal configuration and tweaking, and it would take a while to explain, so I might as well spend that effort writing a program which is simpler to use rather than explaining how to use the hacked-together .c++ file that I wrote over the course of ~5 hours. Plus, unless you want to make a two-colour image, you'd have to manually write all the colours down; that's what I did with the mona lisa.

What a shame (No sarcasm)
blah wrote:
Saka wrote:I was thinking of generating a painting with cell-specific instructions and stuff, starting from 1 cell.

How detailed was that idea? Did you image it having a stationary core that all the signals came out of, like my implementation?

Just finished writing a very simple implementation of it:
@RULE SAKASMILEY

#State 1 is the drawing state, so do state 2
@TABLE
n_states:14
neighborhood:vonNeumann
symmetries:none
#State 2
2,0,0,0,0,1
0,0,0,0,2,3
#State 3
0,0,0,0,3,4
3,0,0,0,1,0
#State 4
0,0,0,0,4,5
4,0,0,0,0,0
#State 5
5,0,0,0,0,1
0,5,0,0,0,6
#State 6
6,1,0,0,0,0
0,6,0,0,0,7
#State 7
7,0,0,0,0,1
0,0,7,0,0,8
#State 8
8,0,1,0,0,0
0,0,8,0,0,9
#State 9
9,0,0,0,0,0
0,0,9,0,0,10
#State 10
10,0,0,0,0,1
0,10,0,0,0,11
#State 11
11,1,0,0,0,0
0,0,0,0,11,12
#State 12
12,0,0,0,0,1
0,0,0,0,12,13
#State 13
13,0,0,0,1,1

This:
x = 1, y = 1, rule = SAKASMILEY
B!
Everyone, please stop posting B/S about CA
x = 17, y = 10, rule = B3/S23
b2ob2obo5b2o$11b4obo$2bob3o2bo2b3o$bo3b2o4b2o$o2bo2bob2o3b4o$bob2obo5b
o2b2o$2b2o4bobo2b3o$bo3b5ob2obobo$2bo5bob2o$4bob2o2bobobo!

(Check gen 2)
User avatar
Saka
 
Posts: 2178
Joined: June 19th, 2015, 8:50 pm
Location: In the kingdom of Sultan Hamengkubuwono X

Re: Universal construction of complex patterns from 1 cell

Postby muzik » September 11th, 2017, 10:55 am

Could a concept similar to this be used to make a 1-cell spaceship of any speed up to (m,n)c/256, assuming said speed is possible in the given neighbourhood?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2595
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 11th, 2017, 12:06 pm

muzik wrote:Could a concept similar to this be used to make a 1-cell spaceship of any speed up to (m,n)c/256, assuming said speed is possible in the given neighbourhood?

It would be relatively simple to make a rule which allows (m,n)c/p spaceships for allowable values of m,n, and p, but what do you mean "up to (m,n)c/256"? Why would 2^8 be the limit?
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby muzik » September 11th, 2017, 12:14 pm

Well, that would be the limit were the ship to stay as a single cell forever. If that wasn't the case, i'm pretty sure the range of speeds would be a lot higher.
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2595
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 11th, 2017, 12:22 pm

muzik wrote:Well, that would be the limit were the ship to stay as a single cell forever. If that wasn't the case, i'm pretty sure the range of speeds would be a lot higher.

Well, I thought you meant the ship would only have to be a single cell in at least one phase. Otherwise you're not talking about my idea; that would be something unrelated. To be fair, I guess you did say "a concept similar to this".

Either way, there are only a finite number of RuleLoader rules. Therefore, there are only a finite number of one-cell speeds, though they can probably get pretty slow; I can imagine someone making a rule where a single cell creates a computer which computes graham's number and writes it in binary and counts up to it and moves one cell or something; something that you could never run in its entirety.
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby dvgrn » September 13th, 2017, 3:13 pm

blah wrote:Does anyone find this idea interesting or useful? I don't know if it really has any significant implications; I guess it might be nice as an example pattern in Golly, though there is plenty of room for optimisation, including an idea I had that would probably make it twice as fast.

Interesting, definitely. Useful -- that's always a loaded word. It's useful as a way to teach people how to creatively misuse rule-table format, if nothing else...!

The rule table is big enough that I'd like to add a ZIP file, ironically enough, to Very Large Patterns in Golly's online archives. It will be the smallest Very Large Pattern ever, unless you can figure out how to pull a similar trick starting from empty space.

(It seems obviously impossible, since in a normal universe there's no way to pick a cell to start from. But maybe it's possible to work in from the corners of a non-torus bounded grid somehow, by taking advantage of the different number of neighbors at a corner...?)

(Well, no, never mind -- I think cells outside the border are still counted, they're just always OFF.)

(So it would have to be a non-torus bounded grid multistate B0-type rule...)

Anyway -- should I wait for a twice-as-fast version of the Mona Lisa Rule, or just go ahead and collect this version to check in?
dvgrn
Moderator
 
Posts: 3987
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 13th, 2017, 5:09 pm

dvgrn wrote:Anyway -- should I wait for a twice-as-fast version of the Mona Lisa Rule, or just go ahead and collect this version to check in?

I've thought about it, and my twice-as-fast idea contradicts itself (it required stopping the arm when it would already be at c), but I could probably make one where the horizontal arms extrude at c/2 instead of c/3 by sending "start" and "stop" signals to the arm at c. Either way, I don't really feel like going back and optimising it; there's a certain point where further optimisation is just boring, and I think I've reached that, although I did generate this interesting image while trying to remove redundant transitions:

accidentalderivativeart.png
accidentalderivativeart.png (49.68 KiB) Viewed 580 times

Anyway, yeah, you should use the rule as it is rather than waiting.

(Doesn't Golly have a bug where on an unbounded grid, running a RuleLoader rule with b0 results in exponentially bigger squares? Maybe you could make something happen at one of the corners. Bounded grids would probably be easier to use, though; just make everything go from state 0 straight to some other state. I'll try that.)

(Golly just crashed, and I misspelled it "Folly" when I wrote that, so maybe this is a bad idea.)
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby dvgrn » September 19th, 2017, 9:09 pm

Just a minor note, now that I've built the attached file anyway:

In cases where you're making a ZIP file of rule text that goes with a particular pattern, it might as well be in the following form. That way when you File > Open the archive directly in Golly, the rule gets installed automatically and the pattern opens, all in one swell foop.

monalisa.zip
Trivial one-cell pattern and Mona-Lisa-making rule in one super convenient package
(159.19 KiB) Downloaded 16 times
dvgrn
Moderator
 
Posts: 3987
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Universal construction of complex patterns from 1 cell

Postby gameoflifemaniac » September 20th, 2017, 10:30 am

How about a rule that prints ITSELF?
https://www.youtube.com/watch?v=q6EoRBvdVPQ
One big dirty Oro. Yeeeeeeeeee...
User avatar
gameoflifemaniac
 
Posts: 379
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E

Re: Universal construction of complex patterns from 1 cell

Postby blah » September 20th, 2017, 11:35 am

gameoflifemaniac wrote:How about a rule that prints ITSELF?

If we just imagine it's a binary format corresponding to the .rule file, it probably exists.

I guess you'd have to have the ROM output into a tape that stores all the states O has taken, in addition to having that ROM be used to construct a computer. The computer would then be programmed to print the beginning of the .rule, and then it would go through the history of O's states and construct a set of transitions out of that.

Kind of like a Von Neumann machine, but the instruction tape would come first, and the computer would kind of be built by it. Also it wouldn't be a direct replicator, just a quine.

Maybe there's a simpler way to do that.
succ
User avatar
blah
 
Posts: 174
Joined: April 9th, 2016, 7:22 pm

Re: Universal construction of complex patterns from 1 cell

Postby Andrew » September 20th, 2017, 6:19 pm

dvgrn wrote:In cases where you're making a ZIP file of rule text that goes with a particular pattern, it might as well be in the following form. ...

A minor annoyance with this approach is that it opens the Help window. It's easy to avoid that by creating a zip file with a single Lua script that writes the .rule file in the right place and then writes and opens a temporary pattern file. The script's general structure looks like this:

local g = golly()
rulename = g.getdir("rules").."BLAHMONALISA.rule"
f = io.open(rulename, "w")
if f then
    f:write(
[[
@RULE BLAHMONALISA

etc...

]]
    )
    f:close()
end

pattname = g.getdir("temp").."monalisa.rle"
f = io.open(pattname, "w")
if f then
    f:write(
[[
x = 1, y = 1, rule = BLAHMONALISA
A!
]]
    )
    f:close()
end
g.open(pattname)
g.show("Rule file was created: "..rulename)


Here's the resulting zip file:
Attachments
monalisa2.zip
(169.66 KiB) Downloaded 10 times
User avatar
Andrew
Moderator
 
Posts: 629
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

Re: Universal construction of complex patterns from 1 cell

Postby Apple Bottom » September 20th, 2017, 6:22 pm

Andrew wrote:A minor annoyance with this approach is that it opens the Help window. It's easy to avoid that by creating a zip file with a single Lua script that writes the .rule file in the right place and then writes and opens a temporary pattern file.


I'd say that's not a bug but a feature -- I liked it that Golly informed me that it had installed a new rule earlier, when I tried dvgrn's ZIP file. I usually would expect that merely *opening* a file (a pattern, even if it is in ZIP form and comes with a custom rule) is a stateless action that leaves Golly unchanged when you close the file again, so I was quite happy that Golly informed me that an enduring change had indeed been made.
Living proof that a little knowledge is a dangerous thing.

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!
User avatar
Apple Bottom
 
Posts: 743
Joined: July 27th, 2015, 2:06 pm

Re: Universal construction of complex patterns from 1 cell

Postby Andrew » September 20th, 2017, 6:32 pm

Apple Bottom wrote:I liked it that Golly informed me that it had installed a new rule earlier, when I tried dvgrn's ZIP file.

Well, it would be trivial to add a g.note call to my version stating that a .rule file has been created. That would be even more informative than Dave's version, given that the Help window is opened behind the main window and you have to bring it to the front to see what it says.

EDIT: A g.show call at the very end of the script would be better than g.note. That's a nicer compromise for people like me who don't want to see any sort of window or dialog appear and people like AB who'd like to be notified that a .rule file was created. I've updated the above zip file to call g.show.
User avatar
Andrew
Moderator
 
Posts: 629
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 5 guests