Salt, a 3D reversible, universal CA
Salt, a 3D reversible, universal CA
You might find "Circular Motion of Strings in Cellular Automata and Other Suprises" interesting.
It can be found at digitalphilosophy.org
Also, you can see, run and discover new configurations of Salt CA at busyboxes.org
It can be found at digitalphilosophy.org
Also, you can see, run and discover new configurations of Salt CA at busyboxes.org
Re: Salt, a 3D reversible, universal CA
The emergence of circular motion got me thinking why is reversibility considered such an important criterion in academic CA research.
Obviously, a goal here is to understand our own universe, which appears to be reversible at micro-scales. However, it seems to me that a kind of reversibility could well arise by emergence.
Consider a Life-life CA that supports spaceships and does not explode, and a pattern consisting of a very large active region as well as a diagonally greatly separated equally large area of ash. What will happen here is
1) The active region emits a number of ships towards the ash, then dies down to become ash itself.
2) The ash reacts with the incoming ships, and produces itself a number of ships, some of which will head back towards the original region.
3) The return ships trigger a new wave of activity at the original active region.
4) Etc.
Now, furthermore assume that the overall reactivity of this CA is such that one incoming salvo will trigger one of equal size and no change to the size of the ash blob. In this case, the pattern thus becomes a kind of "pinball gun", with waves of ships bouncing back and forth (plus sending some to the other six directions each round).
At sufficiently large scales, the energy of the salvo will appear to be a conserved quantity; the exact number of ships will not be constant, but will vary around some statistical average (depending on the size of the ash blobs: salvos in general can random-walk in size, but ones too big will miss the target or collide with too many return ships, while ones too small will not do either, so the stability of the situation requires them to more probably random-walk upwards). There'll also be a relationship between the size of an active area and the number of ships it will output/have input. Likewise, the situation will appear to be reversible in a certain way: an active region of a certain size in the southwest of an ash blob can have several precedessors, but since activity probably will die down, by far most of these will be due to a ship salvo of a certain size coming in from the SW.
Situations where kickback reactions etc. insert new ships into a salvo would however seem to not be negligible in probability (a given number of ticks ago, a periodic ship has exactly one ancestor that is also a periodic ship), so salvos will not itself be reversible if made up of independant ships… we'd need a type of salvo that can interact among itself while retaining its momentum and size, on average.
Obviously, a goal here is to understand our own universe, which appears to be reversible at micro-scales. However, it seems to me that a kind of reversibility could well arise by emergence.
Consider a Life-life CA that supports spaceships and does not explode, and a pattern consisting of a very large active region as well as a diagonally greatly separated equally large area of ash. What will happen here is
1) The active region emits a number of ships towards the ash, then dies down to become ash itself.
2) The ash reacts with the incoming ships, and produces itself a number of ships, some of which will head back towards the original region.
3) The return ships trigger a new wave of activity at the original active region.
4) Etc.
Now, furthermore assume that the overall reactivity of this CA is such that one incoming salvo will trigger one of equal size and no change to the size of the ash blob. In this case, the pattern thus becomes a kind of "pinball gun", with waves of ships bouncing back and forth (plus sending some to the other six directions each round).
At sufficiently large scales, the energy of the salvo will appear to be a conserved quantity; the exact number of ships will not be constant, but will vary around some statistical average (depending on the size of the ash blobs: salvos in general can random-walk in size, but ones too big will miss the target or collide with too many return ships, while ones too small will not do either, so the stability of the situation requires them to more probably random-walk upwards). There'll also be a relationship between the size of an active area and the number of ships it will output/have input. Likewise, the situation will appear to be reversible in a certain way: an active region of a certain size in the southwest of an ash blob can have several precedessors, but since activity probably will die down, by far most of these will be due to a ship salvo of a certain size coming in from the SW.
Situations where kickback reactions etc. insert new ships into a salvo would however seem to not be negligible in probability (a given number of ticks ago, a periodic ship has exactly one ancestor that is also a periodic ship), so salvos will not itself be reversible if made up of independant ships… we'd need a type of salvo that can interact among itself while retaining its momentum and size, on average.
Re: Salt, a 3D reversible, universal CA
If you read the paper: Circular Motion of Strings... at digitalphilosophy.org, you will understand why microscopic reversibility is a key ingredient (both of physics and models of physics). The SALT model is CPT reversible, as is true of physics.
- Tim Hutton
- Posts: 64
- Joined: May 20th, 2010, 7:30 am
- Contact:
Re: Salt, a 3D reversible, universal CA
Hello. Are you Ed Fredkin?edf wrote:You might find "Circular Motion of Strings in Cellular Automata and Other Suprises" interesting.
It can be found at digitalphilosophy.org
Also, you can see, run and discover new configurations of Salt CA at busyboxes.org
I've been meaning to play with Salt. Superficially it looks a little similar to CA models of connected particles, as explored here:
- http://cell-auto.com/simple_membranes/ (Tim Tyler)
- http://www.sq3.org.uk/Evolution/Squirm/ (me)
- http://www.sq3.org.uk/Evolution/Squirm3/playground/ (me)
- http://elm.eeng.dcu.ie/~alife/bmcm-ecal97/node5.html (Varela, Maturana and Uribe; McMullin)
- Critters (supports linked chain oscillators - thanks to Ivan Zvolsky for pointing out the similarity)
- Lattice Molecular Automata / Lattice Polymer Automata
http://code.google.com/p/reaction-diffusion/
Thanks,
Tim
Last edited by Tim Hutton on April 10th, 2013, 7:37 am, edited 2 times in total.
- Tim Hutton
- Posts: 64
- Joined: May 20th, 2010, 7:30 am
- Contact:
Re: Salt, a 3D reversible, universal CA
Here's the 2D Salt CA running in Ready. I implemented it as a 4-state CA with a radius-3 Moore neighborhood.
To run this for yourself, here's the Ready file with the implementation written in OpenCL: salt_2D.vti
Edit: I've made a 3-state version that is nicer to explore in Ready since you can draw more easily: salt2D_demo.vti (fixed link)
I'll have a look at the 3D version next.
Fun!
Tim
To run this for yourself, here's the Ready file with the implementation written in OpenCL: salt_2D.vti
Edit: I've made a 3-state version that is nicer to explore in Ready since you can draw more easily: salt2D_demo.vti (fixed link)
I'll have a look at the 3D version next.
Fun!
Tim
Last edited by Tim Hutton on November 18th, 2013, 6:37 pm, edited 2 times in total.
- Tim Hutton
- Posts: 64
- Joined: May 20th, 2010, 7:30 am
- Contact:
Re: Salt, a 3D reversible, universal CA
Here's the 3D version:
salt3D_circular330.vti (download and open in Ready)
This is an 8-cell strand, moving in an approximately circular path (if you trace the average location over time) in 330 steps. As they say in the paper, with longer strands this approximation gets better and better. If you look at the simple way the strand moves, this is really surprising!
Their web interface for this pattern is: http://busyboxes.org/o
salt3D_circular330.vti (download and open in Ready)
This is an 8-cell strand, moving in an approximately circular path (if you trace the average location over time) in 330 steps. As they say in the paper, with longer strands this approximation gets better and better. If you look at the simple way the strand moves, this is really surprising!
Their web interface for this pattern is: http://busyboxes.org/o
Last edited by Tim Hutton on November 18th, 2013, 7:00 pm, edited 1 time in total.
- Tim Hutton
- Posts: 64
- Joined: May 20th, 2010, 7:30 am
- Contact:
Re: Salt, a 3D reversible, universal CA
If 3D strands move in an increasingly-good approximation to a circle, is it also true that the average location of the cells in the vibrating strings in the 2D version moves in a sine wave over time? Could we prove that, by modelling the movement of each cell?
Edit: I've been exploring the 2D system. It is certainly very close to a sine wave but doesn't seem to quite converge: comparison, convergence
I don't even know if a simple system like this *could* yield a perfect sine wave. Maybe it just happens to give a curve that is very similar to a sine wave? Edit: Stephan Rafler points out that NURBS curves can never give a perfect sine wave but they can give a perfect circle.
Edit: I've been exploring the 2D system. It is certainly very close to a sine wave but doesn't seem to quite converge: comparison, convergence
I don't even know if a simple system like this *could* yield a perfect sine wave. Maybe it just happens to give a curve that is very similar to a sine wave? Edit: Stephan Rafler points out that NURBS curves can never give a perfect sine wave but they can give a perfect circle.
Re: Salt, a 3D reversible, universal CA
I found an interesting family of gliders based on one of the examples
in Dan Miller's BusyBoxes CA, which exhibits both circular motion and
translation:
The original glider was this one:
http://busyboxes.org/?hash=PB0jwU0vAB0
it is basically the circular motion configuration, and a single stationary cell, which gets nudged over
every full rotation, and nudges the entire configuration over with it.
So the entire thing travels in a straight line, with a velocity that
is inversely dependent on the period of the circular glider.
Here's one with seven cells in the circular motion glider:
http://busyboxes.org/?size=60&trail=250 ... EpklMnL2A4
And here's two of the gliders with different periods (thus a different translation velocities)
http://busyboxes.org/?size=60&trail=250 ... xYfAHnLBG4
When these collide with fixed cells, you can get different periods, like this
length five glider hits a red cell , and turns into a lengt four glider
http://busyboxes.org/?size=60&trail=250 ... 3HgB5XvWB4
It's also interesting when some other forms of gliders collide, they can form one of these
circular translating gliders for a period of time.
Here two 'linear' gliders meet, forms a length five circular glider for three cycles, then
turns back into two linear gliders with deflected paths
http://busyboxes.org/?size=60&trail=250 ... k6ODm8APL0
in Dan Miller's BusyBoxes CA, which exhibits both circular motion and
translation:
The original glider was this one:
http://busyboxes.org/?hash=PB0jwU0vAB0
it is basically the circular motion configuration, and a single stationary cell, which gets nudged over
every full rotation, and nudges the entire configuration over with it.
So the entire thing travels in a straight line, with a velocity that
is inversely dependent on the period of the circular glider.
Here's one with seven cells in the circular motion glider:
http://busyboxes.org/?size=60&trail=250 ... EpklMnL2A4
And here's two of the gliders with different periods (thus a different translation velocities)
http://busyboxes.org/?size=60&trail=250 ... xYfAHnLBG4
When these collide with fixed cells, you can get different periods, like this
length five glider hits a red cell , and turns into a lengt four glider
http://busyboxes.org/?size=60&trail=250 ... 3HgB5XvWB4
It's also interesting when some other forms of gliders collide, they can form one of these
circular translating gliders for a period of time.
Here two 'linear' gliders meet, forms a length five circular glider for three cycles, then
turns back into two linear gliders with deflected paths
http://busyboxes.org/?size=60&trail=250 ... k6ODm8APL0
Re: Salt, a 3D reversible, universal CA
Here's an animation of the length 7 circular glider with translation
-
- Posts: 549
- Joined: April 9th, 2013, 11:03 pm
Re: Salt, a 3D reversible, universal CA
Would it be possible to make a rule file for Golly for the 2D version? It's not too important, but it would be nice. Thanks.
- Tim Hutton
- Posts: 64
- Joined: May 20th, 2010, 7:30 am
- Contact:
Re: Salt, a 3D reversible, universal CA
Hi Sphenocorona,Sphenocorona wrote:Would it be possible to make a rule file for Golly for the 2D version? It's not too important, but it would be nice. Thanks.
No, I'm afraid not. The rule uses a 7x7 neighborhood (radius-3 Moore), which Golly doesn't currently support. It could be emulated as a radius-1 Moore neighborhood but we'd need each cell to represent 3x3 cells of the Salt CA, so with 3 Salt states we'd need 3^9 = 19683 states in the emulating CA, which is out of reach of Golly at the moment.
Re: Salt, a 3D reversible, universal CA
I was playing with collisions of different kinds of gliders, circular and linear.
Here is two circular gliders (one which is using a 'even' cell, and the other an 'odd' cell)
in a collision, which results in the 'even' circular glider getting split into two linear gliders,
and the 'odd' circular glider proceeding along it's original path:
http://busyboxes.org/?size=100&trail=25 ... Da4zy-AHo3
And here's some interactions between two kinds of linear glider, where
both of them get knocked into different modes of oscillation.
For example this linear glider seems to have two modes, fast and
slow, which it toggles between when it hits a lone cell:
http://busyboxes.org/?size=40&trail=250 ... 2Fw8R0hzA5
And these also, where two linear gliders collide and change direction
and mode/speed. It's a little bit suggestive of something like a
transfer of momentum in some way.
http://busyboxes.org/?size=60&trail=250 ... wEngISBEE1
Here is two circular gliders (one which is using a 'even' cell, and the other an 'odd' cell)
in a collision, which results in the 'even' circular glider getting split into two linear gliders,
and the 'odd' circular glider proceeding along it's original path:
http://busyboxes.org/?size=100&trail=25 ... Da4zy-AHo3
And here's some interactions between two kinds of linear glider, where
both of them get knocked into different modes of oscillation.
For example this linear glider seems to have two modes, fast and
slow, which it toggles between when it hits a lone cell:
http://busyboxes.org/?size=40&trail=250 ... 2Fw8R0hzA5
And these also, where two linear gliders collide and change direction
and mode/speed. It's a little bit suggestive of something like a
transfer of momentum in some way.
http://busyboxes.org/?size=60&trail=250 ... wEngISBEE1
Re: Salt, a 3D reversible, universal CA
These interactions are really intriguing. It would be interesting to try to catalog the various ways gliders can interact, and the resulting changes in velocity/direction that occur.
Re: Salt, a 3D reversible, universal CA
Tim Hutton has added the Busyboxes rule to his 'ready' program http://code.google.com/p/reaction-diffusion/Sphenocorona wrote:Would it be possible to make a rule file for Golly for the 2D version? It's not too important, but it would be nice. Thanks.
Also, in case it's not clear to everyone, anyone can build/run/modify Busyboxes configurations at busyboxes.com, and share them as URL's, as some have already done on this forum. There is no registration needed.
The source code for the website is published here: https://github.com/danx0r/BusyBoxes
We are very interested in getting more CA enthusiasts to take a look at this CA and help us explore its possibilities.
-dan miller (co-author of the papers on Busyboxes)
Re: Salt, a 3D reversible, universal CA
Hi Dan. I've had a few pleasant hours playing with BusyBoxes and the above code -- the Salt CA is truly fascinating!danx0r wrote:The source code for the website is published here: https://github.com/danx0r/BusyBoxes
Minor errors:
- In readme.md there are a couple of dead links to bbx.logqr.com.
- The BusyBoxes code has problems with odd-sized grids.
I managed to fix the grid problems, and also made other changes that I think improve the display:
By displaying 3 grids we can draw 3 shadows showing the current cursor position, which can be helpful when it is obscured by lots of cells. All my changes are flagged by "AKT" in the following attachment. Feel free to use or ignore any of them!
- Attachments
-
- index.html.zip
- (13.95 KiB) Downloaded 352 times
Re: Salt, a 3D reversible, universal CA
The 3-shadow thing looks like a cool idea! I will try to review these changes and get them on the site ASAP.Andrew wrote:danx0r wrote: By displaying 3 grids we can draw 3 shadows showing the current cursor position, which can be helpful when it is obscured by lots of cells. All my changes are flagged by "AKT" in the following attachment. Feel free to use or ignore any of them!
As to odd-sized grids, they should probably be discouraged, as they break the symmetry of odd and even cell positions which is kind of central to the Salt neighborhood idea. I'll see what you did on that, it may be best to simply disallow them.
-dan miller
Re: Salt, a 3D reversible, universal CA
Ah, good point -- I didn't think about that. Probably best just to add 1 if an odd size is requested.danx0r wrote:As to odd-sized grids, they should probably be discouraged, as they break the symmetry of odd and even cell positions which is kind of central to the Salt neighborhood idea.
EDIT: Actually, odd-sized grids seem to work just fine. The various gliders I tested behave the same in both odd and even-sized grids. Or maybe some configurations work but others don't?
Re: Salt, a 3D reversible, universal CA
Hmm... well it only becomes an issue if you set mode=wrap, in which case reversibility is broken: http://busyboxes.org/?size=23&mode=wrap&hash=GJR0Andrew wrote: EDIT: Actually, odd-sized grids seem to work just fine. The various gliders I tested behave the same in both odd and even-sized grids. Or maybe some configurations work but others don't?
To avoid confusion I'd prefer to disallow odd-size grids by default, as it turns this into a very different kind of CA, with strange boundary conditions where the grid wraps around.
Thanks for looking into the issue - dan
Re: Salt, a 3D reversible, universal CA
If I understand it correctly, classic guns, puffers, slideguns or replicators are impossible in this CA, as a consequence of reversibility, though fuse-like patterns with similar properties seem feasible.
Ivan Fomichev
Re: Salt, a 3D reversible, universal CA
'up' cells (roughly equivalent to live cells in GOL) cannot be created or destroyed. However it is possible that some interesting configurations could be built using initial conditions where there is an infinite pattern of cells, such as this:codeholic wrote:If I understand it correctly, classic guns, puffers, slideguns or replicators are impossible in this CA, as a consequence of reversibility, though fuse-like patterns with similar properties seem feasible.
http://busyboxes.org/?size=20&mode=wrap ... cXeHUHOHC0
a repeated 5x5 pattern with two additional cells...
Re: Salt, a 3D reversible, universal CA
Golly 3.2 now supports Busy Boxes. Start up 3D.lua (in Scripts/Lua), then copy the following patterns to the clipboard and select Open Clipboard from 3D.lua's File menu:
The above examples use the default "mirror" mode. The next example uses BusyBoxesW (the W specifies wrap mode):
More details about Busy Boxes, including links to the papers by Fredkin and Miller, can be found in 3D.lua's help (type H or hit the "?" button).
Code: Select all
3D version=1 size=40 pos=9,17,14
# circular motion (p330 oscillator)
x=3 y=10 z=11 rule=BusyBoxes
9$bbo/9$o/7$o//6$o/4$o//3$o/$o//o!
Code: Select all
3D version=1 size=24 pos=11,12,12
# p3966 oscillator
x=5 y=2 z=2 rule=BusyBoxes
o3bo$3o/oobbo$oo!
Code: Select all
3D version=1 size=40 pos=11,19,15 gen=4
# 0,2,2c/264 spaceship found by hminsky
x=3 y=11 z=10 rule=BusyBoxesW
10$bbo//8$o$bbo/6$o//5$o/3$o//$$o/o!
Re: Salt, a 3D reversible, universal CA
The 2nd paper by Miller and Fredkin (https://arxiv.org/abs/1206.2060) includes coordinates for many patterns. Here is a little script for 3D.lua that lets you copy and paste those coordinates into a dialog box and create the desired pattern:
Here are some patterns created using the script:
Anchored string showing wavelike behavior, from page 5
(rotated about X axis so it looks nicer in 3D.lua's default view):
A 6,6,6c/246 glider, from page 7:
String orbiting around a cell, from page 10:
A 6-cell oscillator with period 1200, from page 10:
A 13-cell oscillator with period 6,110,178:
Code: Select all
-- For 3D.lua. This script lets you create a Busy Boxes pattern by
-- entering cell coordinates in the format used by Miller and Fredkin in
-- "Circular Motion of Strings in Cellular Automata, and Other Surprises"
-- (https://arxiv.org/abs/1206.2060).
local g = golly()
local gp = require "gplus"
local coords = g.getstring(
"Enter the cell coordinates as\n"..
"(2,0,-1),(0,3,1),...,(-4,2,0)",
"", "Enter a Busy Boxes pattern")
if #coords > 0 then
NewPattern()
if not GetRule():find("^BusyBoxes") then
SetRule("BusyBoxes")
end
coords = coords:gsub(" ","") -- remove any spaces
coords = coords:gsub("\n","") -- remove any line breaks
for x,y,z in coords:gmatch("%((.-),(.-),(.-)%)") do
SetCell(tonumber(x), tonumber(y), tonumber(z))
end
MoveMode()
end
Anchored string showing wavelike behavior, from page 5
(rotated about X axis so it looks nicer in 3D.lua's default view):
Code: Select all
3D version=1 size=24 pos=2,2,11
x=21 y=21 z=1 rule=BusyBoxes
oo$oo$$bbo$$3bo$$4bo$6bo$8bo$10bo$12bo$14bo$16bo$$17bo$$18bo$$19boo
$19boo!
Code: Select all
3D version=1 size=24 pos=10,11,12
x=3 y=3 z=3 rule=BusyBoxesW
bo/$bbo$o/bbo!
Code: Select all
3D version=1 size=24 pos=11,11,7
x=5 y=4 z=4 rule=BusyBoxes
bbo$$3bo/3$4bo//$$o!
Code: Select all
3D version=1 size=24 pos=11,11,11
x=2 y=3 z=3 rule=BusyBoxes
oo/o$o/o$$o!
Code: Select all
3D version=1 size=24 pos=10,9,9 gen=8757816
x=5 y=7 z=6 rule=BusyBoxes
$$3bo//$obo$o$$3boo$3bo$3bo/o4$o3bo/3$o/3$3bo!
Re: Salt, a 3D reversible, universal CA
A nice feature of the Busy Boxes website is its ability to display trails. The following script lets you do the same thing in 3D.lua:
Here is a screenshot showing the script in action on the circular motion pattern:
Code: Select all
-- For 3D.lua. This script runs the current pattern and uses
-- selected cells to create translucent green trails, similar to
-- those at http://www.busyboxes.org.
-- Author: Andrew Trevorrow, July 2018.
local g = golly()
local op = require "oplus"
local gp = require "gplus"
local ov = g.overlay
local round = gp.round
local allcells = false -- trail all cells or just their average?
SetMessage("Hit escape to abort script\n"..
"Hit A to toggle average trail")
CancelSelection()
MoveMode()
-- allow dragging mouse to rotate grid
local mousedown = false -- mouse button is down?
local prevx, prevy -- previous mouse position
while true do
local event = op.process(g.getevent())
if #event == 0 then
-- might need to resize overlay
CheckWindowSize()
elseif event == "key a none" then
allcells = not allcells
CancelSelection()
elseif event:find("^key") then
-- handle arrow keys, I for initial view, etc
HandleKey(event)
elseif event:find("^oclick") then
local _, x, y, button, mods = gp.split(event)
x = tonumber(x)
y = tonumber(y)
if y > GetBarHeight() and button == "left" then
mousedown = true
prevx = x
prevy = y
end
elseif event:find("^mup") then
mousedown = false
elseif event:find("^ozoomout") then
ZoomOut()
elseif event:find("^ozoomin") then
ZoomIn()
end
local mousepos = ov("xy")
if mousedown and #mousepos > 0 then
local x, y = gp.split(mousepos)
x = tonumber(x)
y = tonumber(y)
if x ~= prevx or y ~= prevy then
-- mouse has moved so rotate the view
local deltax = x - prevx
local deltay = y - prevy
Rotate(round(-deltay/2.0), round(deltax/2.0), 0)
Update()
prevx = x
prevy = y
end
else
local livecells = GetCells()
if #livecells == 0 then
SetMessage("Pattern is empty.")
break
end
if allcells then
-- select all live cells without changing previous selection
for _, xyz in ipairs(livecells) do
SelectCell(table.unpack(xyz))
end
else
-- only select the average position of all live cells
local ax, ay, az = 0, 0, 0
for _, xyz in ipairs(livecells) do
local x, y, z = table.unpack(xyz)
ax = ax + x
ay = ay + y
az = az + z
end
local n = #livecells
SelectCell(round(ax/n), round(ay/n), round(az/n))
end
Step()
if GetGeneration() % GetStepSize() == 0 then
Update()
end
end
end