Salt, a 3D reversible, universal CA

For discussion of other cellular automata.
Post Reply
edf
Posts: 5
Joined: March 29th, 2013, 9:42 am

Salt, a 3D reversible, universal CA

Post by edf » March 29th, 2013, 9:57 am

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

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Salt, a 3D reversible, universal CA

Post by Tropylium » March 29th, 2013, 6:01 pm

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.

edf
Posts: 5
Joined: March 29th, 2013, 9:42 am

Re: Salt, a 3D reversible, universal CA

Post by edf » March 30th, 2013, 9:31 am

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.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Tim Hutton » April 4th, 2013, 12:44 pm

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
Hello. Are you Ed Fredkin?

I've been meaning to play with Salt. Superficially it looks a little similar to CA models of connected particles, as explored here: Our software package Ready should be able to run the 2D and 3D versions. I will have a look.
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.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Tim Hutton » April 5th, 2013, 8:50 am

Here's the 2D Salt CA running in Ready. I implemented it as a 4-state CA with a radius-3 Moore neighborhood.

Image

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.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Tim Hutton » April 8th, 2013, 6:57 pm

Here's the 3D version:

Image
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.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Tim Hutton » April 8th, 2013, 7:41 pm

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.

hminsky
Posts: 3
Joined: October 31st, 2013, 2:51 pm

Re: Salt, a 3D reversible, universal CA

Post by hminsky » November 17th, 2013, 12:23 am

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

hminsky
Posts: 3
Joined: October 31st, 2013, 2:51 pm

Re: Salt, a 3D reversible, universal CA

Post by hminsky » November 18th, 2013, 5:28 pm

Image

Here's an animation of the length 7 circular glider with translation

Sphenocorona
Posts: 549
Joined: April 9th, 2013, 11:03 pm

Re: Salt, a 3D reversible, universal CA

Post by Sphenocorona » November 18th, 2013, 5:53 pm

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.

User avatar
Tim Hutton
Posts: 64
Joined: May 20th, 2010, 7:30 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Tim Hutton » November 18th, 2013, 6:49 pm

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.
Hi Sphenocorona,

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.

hminsky
Posts: 3
Joined: October 31st, 2013, 2:51 pm

Re: Salt, a 3D reversible, universal CA

Post by hminsky » November 19th, 2013, 2:08 pm

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

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » November 20th, 2013, 3:05 pm

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.

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » November 20th, 2013, 3:11 pm

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.
Tim Hutton has added the Busyboxes rule to his 'ready' program http://code.google.com/p/reaction-diffusion/

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)

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Andrew » December 3rd, 2013, 6:10 pm

danx0r wrote:The source code for the website is published here: https://github.com/danx0r/BusyBoxes
Hi Dan. I've had a few pleasant hours playing with BusyBoxes and the above code -- the Salt CA is truly fascinating!

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:
busyboxes.png
busyboxes.png (147.1 KiB) Viewed 17490 times
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
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » December 5th, 2013, 1:51 am

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!
The 3-shadow thing looks like a cool idea! I will try to review these changes and get them on the site ASAP.

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

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Andrew » December 5th, 2013, 3:47 am

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.
Ah, good point -- I didn't think about that. Probably best just to add 1 if an odd size is requested.

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?
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » December 5th, 2013, 6:55 pm

Andrew 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?
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=GJR0

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

User avatar
codeholic
Moderator
Posts: 1147
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Salt, a 3D reversible, universal CA

Post by codeholic » December 6th, 2013, 9:22 am

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

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » December 11th, 2013, 2:43 am

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.
'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:

http://busyboxes.org/?size=20&mode=wrap ... cXeHUHOHC0

a repeated 5x5 pattern with two additional cells...

danx0r
Posts: 6
Joined: October 16th, 2013, 2:13 am
Contact:

Re: Salt, a 3D reversible, universal CA

Post by danx0r » December 11th, 2013, 2:51 am


User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Andrew » June 12th, 2018, 9:24 pm

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:

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!
The above examples use the default "mirror" mode. The next example uses BusyBoxesW (the W specifies wrap mode):

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!
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).
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Andrew » June 13th, 2018, 10:27 pm

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:

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
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):

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!
A 6,6,6c/246 glider, from page 7:

Code: Select all

3D version=1 size=24 pos=10,11,12
x=3 y=3 z=3 rule=BusyBoxesW
bo/$bbo$o/bbo!
String orbiting around a cell, from page 10:

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!
A 6-cell oscillator with period 1200, from page 10:

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!
A 13-cell oscillator with period 6,110,178:

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!
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

User avatar
Andrew
Moderator
Posts: 919
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Salt, a 3D reversible, universal CA

Post by Andrew » June 14th, 2018, 8:28 pm

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:

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
Here is a screenshot showing the script in action on the circular motion pattern:
trails.png
trails.png (68.85 KiB) Viewed 11318 times
Use Glu to explore CA rules on non-periodic tilings: DominoLife and HatLife

Post Reply