4 ms·

The Single Rotation rule: simple and rich reversible cellular automaton (2013)

112 points by bemmu 8y ago

fallingfrog 8y ago
This is really cool! It’s very interesting that the time reversible cellular automata also conserves mass. I feel like there must be a connection to Noether’s theorem here; in fact I’d wager that any time reversible cellular automata conserves mass..
- tgb 8y ago
  Not just any: consider the dumbest possible cellular automate with 1 cell that always switches between black and white. Trivially reversible but mass is not conserved. It's easy to see that mass must oscillate though (and cannot grow infinitely), if the system is finite and time-reversible (and if not finite, then mass of the system is ill-defined).
  - heavenlyblue 8y ago
    Here’s a counterexample (time-reversible and infinite): 1) start with a single cell 2) create a cell if bottom neighbour is a cell At every step our tower is growing Reversal: 1) delete a cell if a cell doesn’t have a top neighbour
    - jpfed 8y ago
      Can we say that a CA is reversible if, in order to deduce the previous state, you must know the initial conditions? With your CA, if you did not know that the current state ultimately descended from one cell, you would not know whether the previous state involved two towers separated by an empty cell.
    - SamReidHughes 8y ago
      That's not reversible -- there is no preceding state for the one-cell state.
      - syrrim 8y ago
        Given two dimensions: Destroy any cell with only a left neighbour. Create any cell with only a bottom neighbour. Start with a single cell: in the forward direction a vertical tower appears. In the reverse direction a horizontal row appears.
        SamReidHughes 8y ago
        The following picture has two predecessor states: _____ _____ __x__ _____ __x__ They are: _____ _____ __xx_ _____ __x__ and _____ _____ __xx_ _____ __xx_ Edit: Also, this has zero predecessors: _x xx
        Twisol 8y ago
        EDIT: I'm assuming that "neighbor" means a cell sharing an edge, but I realize that the Game of Life includes cells sharing a corner, so this probably isn't what you meant. Leaving it for... curiosity, I guess? > In the reverse direction a horizontal row appears. If you have a non-trivial row of live cells, then the cells immediately above that row will also become alive in the next (forward) instant. You end up with a row of N propagating upwards with a trail of rows of N-1. I think your 1-cell example is actually a Garden of Eden in this rule -- there is no state that would produce it. The 1-cell itself isn't a still life, since as you note, it generates a vertical tower. Going backwards, a cell could only exist in the N+1'th state if it has a left neighbor in the N'th state; the only possible candidate for a predecessor would be the 2-cell row. But if we step this forward, we end up with three cells: OO O
    - tgb 8y ago
      Sorry, not sure I understand. What is this a counterexample of?
      - SamReidHughes 8y ago
        A counterexample to your claim that mass cannot grow infinitely. It doesn't work though...
        tgb 8y ago
        That wasn't my claim though, since I was assuming finiteness of the system.
        SamReidHughes 8y ago
        So you mean finitely many cells, on or off. What's funny is we still don't have a counterexample of the broader notion, with finitely many cells turned on, in an infinite grid.
- yesenadam 8y ago
  There are a load of papers on the subject, I read a lot a couple of years ago. Some leading names: Fredkin, Margolus & Toffoli, Gerard Vichniac, Jarkko Kari, Tetsuya Hattori, Morita & Ueno, Shinji Takasue, mostly 70s and since. I made movies that looked like sunlight reflecting on ripples in a river (I mean, looked exactly) using 2D CA based on a couple of Rudy Rucker papers, based on (I believe) the original (1D) CA paper, analyzing non-linear effects on waves, modelled as a row of particles, neighbours joined with springs, sliding up and down frictionless rods. I used this super-simple formula to approximate the wave equation: a cell's height (each cell stores a number representing height of the water) = half the sum of the 4 neighbours from the previous generation, minus the cell's height in the gen before that. i.e. C_t=(Nsum_{t-1})/2-C_{t-2}. (Note that adding C_{t-2} to both sides produces a time-symmetric equation.) Amazing that it produced totally realistic-looking water! (I added a feature to show sunlight reflection if the 3D angle of the plane between each adjacent 4 points was in a particular small angle range) Different conserved quantities in CAs indeed correspond to different conserved quantities in the physics. (I don't remember the details enough now to say more.)
  - fallingfrog 8y ago
    Thanks, I'll check some of these out! Sounds like a very fun project.
sgentle 8y ago
Fascinating. I notice some arguments that sound a bit like CA applications of Noether's theorem (symmetries correspond to conservation laws). For example, "as a consequence of the time-reversibility, no pattern can completely disappear", and "collision of a lightest spaceship with a static life always produces another lightest spaceship and the same static life". Could these be formulated as time-energy and position-momentum relationships?
- jes5199 8y ago
  momentum maps pretty strangely to automata, since to move more slowly you need a more complicated spaceship
  - goldenkey 8y ago
    Thats actually the principle behind doubly special relativity and the Feynman checkerboard. If all fundamental particles move at C, then movement at less than C for a "macroscopic object" would have to be facilitated by internal bouncing. You can actually get special relativity from a couple principles: 1) All fundamental particles move at C. C usually equals 1 cell per tick. 2) Energy = amount of change per unit time. Change defined as particle movement or particle interaction. 3) Complimentarity - A particle cannot interact and move at the same time. 4) Mass = amount of internal bouncing 5) Speed of an object = (internal change due to energy / total change due to energy) Heres a CA I made based off of these concepts: https://github.com/churchofthought/ScatterLife/blob/master/README.md https://github.com/churchofthought/ScatterLife/blob/master/R...
darepublic 8y ago
Why not make the gif a graceful fallback instead of showing modern browsers both svg + low quality gif
mikhailfranco 8y ago
Fascinating. The rule reminds me of this iconoclastic tour de force from the great David Hestenes, which takes intrinsic angular momentum seriously, i.e. electrons really are spinning or spiralling: The Zitterbewegung Interpretation of Quantum Mechanics http://geocalc.clas.asu.edu/pdf/ZBW_I_QM.pdf http://geocalc.clas.asu.edu/pdf/ZBW_I_QM.pdf "The idea that the electron spin and magnetic moment are generated by a localized circulatory motion of the electron has been proposed independently by many physicists. Schroedinger’s zitterbewegung (zbw) model for such motion is especially noteworthy, because it is grounded in an analysis of solutions to the Dirac equation. Surely, if the zbw is a real physical phenomena, then it tells us something fundamental about the nature of the electron..."

112 points by bemmu 8y ago

This is really cool! It’s very interesting that the time reversible cellular automata also conserves mass. I feel like there must be a connection to Noether’s theorem here; in fact I’d wager that any time reversible cellular automata conserves mass..

tgb 8y ago
Not just any: consider the dumbest possible cellular automate with 1 cell that always switches between black and white. Trivially reversible but mass is not conserved. It's easy to see that mass must oscillate though (and cannot grow infinitely), if the system is finite and time-reversible (and if not finite, then mass of the system is ill-defined).
- heavenlyblue 8y ago
  Here’s a counterexample (time-reversible and infinite): 1) start with a single cell 2) create a cell if bottom neighbour is a cell At every step our tower is growing Reversal: 1) delete a cell if a cell doesn’t have a top neighbour
  - jpfed 8y ago
    Can we say that a CA is reversible if, in order to deduce the previous state, you must know the initial conditions? With your CA, if you did not know that the current state ultimately descended from one cell, you would not know whether the previous state involved two towers separated by an empty cell.
  - SamReidHughes 8y ago
    That's not reversible -- there is no preceding state for the one-cell state.
    - syrrim 8y ago
      Given two dimensions: Destroy any cell with only a left neighbour. Create any cell with only a bottom neighbour. Start with a single cell: in the forward direction a vertical tower appears. In the reverse direction a horizontal row appears.
      - SamReidHughes 8y ago
        The following picture has two predecessor states: _____ _____ __x__ _____ __x__ They are: _____ _____ __xx_ _____ __x__ and _____ _____ __xx_ _____ __xx_ Edit: Also, this has zero predecessors: _x xx
      - Twisol 8y ago
        EDIT: I'm assuming that "neighbor" means a cell sharing an edge, but I realize that the Game of Life includes cells sharing a corner, so this probably isn't what you meant. Leaving it for... curiosity, I guess? > In the reverse direction a horizontal row appears. If you have a non-trivial row of live cells, then the cells immediately above that row will also become alive in the next (forward) instant. You end up with a row of N propagating upwards with a trail of rows of N-1. I think your 1-cell example is actually a Garden of Eden in this rule -- there is no state that would produce it. The 1-cell itself isn't a still life, since as you note, it generates a vertical tower. Going backwards, a cell could only exist in the N+1'th state if it has a left neighbor in the N'th state; the only possible candidate for a predecessor would be the 2-cell row. But if we step this forward, we end up with three cells: OO O
  - tgb 8y ago
    Sorry, not sure I understand. What is this a counterexample of?
    - SamReidHughes 8y ago
      A counterexample to your claim that mass cannot grow infinitely. It doesn't work though...
      - tgb 8y ago
        That wasn't my claim though, since I was assuming finiteness of the system.
        SamReidHughes 8y ago
        So you mean finitely many cells, on or off. What's funny is we still don't have a counterexample of the broader notion, with finitely many cells turned on, in an infinite grid.
yesenadam 8y ago
There are a load of papers on the subject, I read a lot a couple of years ago. Some leading names: Fredkin, Margolus & Toffoli, Gerard Vichniac, Jarkko Kari, Tetsuya Hattori, Morita & Ueno, Shinji Takasue, mostly 70s and since. I made movies that looked like sunlight reflecting on ripples in a river (I mean, looked exactly) using 2D CA based on a couple of Rudy Rucker papers, based on (I believe) the original (1D) CA paper, analyzing non-linear effects on waves, modelled as a row of particles, neighbours joined with springs, sliding up and down frictionless rods. I used this super-simple formula to approximate the wave equation: a cell's height (each cell stores a number representing height of the water) = half the sum of the 4 neighbours from the previous generation, minus the cell's height in the gen before that. i.e. C_t=(Nsum_{t-1})/2-C_{t-2}. (Note that adding C_{t-2} to both sides produces a time-symmetric equation.) Amazing that it produced totally realistic-looking water! (I added a feature to show sunlight reflection if the 3D angle of the plane between each adjacent 4 points was in a particular small angle range) Different conserved quantities in CAs indeed correspond to different conserved quantities in the physics. (I don't remember the details enough now to say more.)
- fallingfrog 8y ago
  Thanks, I'll check some of these out! Sounds like a very fun project.

sgentle 8y ago

Fascinating. I notice some arguments that sound a bit like CA applications of Noether's theorem (symmetries correspond to conservation laws). For example, "as a consequence of the time-reversibility, no pattern can completely disappear", and "collision of a lightest spaceship with a static life always produces another lightest spaceship and the same static life". Could these be formulated as time-energy and position-momentum relationships?

jes5199 8y ago
momentum maps pretty strangely to automata, since to move more slowly you need a more complicated spaceship
- goldenkey 8y ago
  Thats actually the principle behind doubly special relativity and the Feynman checkerboard. If all fundamental particles move at C, then movement at less than C for a "macroscopic object" would have to be facilitated by internal bouncing. You can actually get special relativity from a couple principles: 1) All fundamental particles move at C. C usually equals 1 cell per tick. 2) Energy = amount of change per unit time. Change defined as particle movement or particle interaction. 3) Complimentarity - A particle cannot interact and move at the same time. 4) Mass = amount of internal bouncing 5) Speed of an object = (internal change due to energy / total change due to energy) Heres a CA I made based off of these concepts: https://github.com/churchofthought/ScatterLife/blob/master/README.md https://github.com/churchofthought/ScatterLife/blob/master/R...

darepublic 8y ago

Why not make the gif a graceful fallback instead of showing modern browsers both svg + low quality gif

mikhailfranco 8y ago

Fascinating. The rule reminds me of this iconoclastic tour de force from the great David Hestenes, which takes intrinsic angular momentum seriously, i.e. electrons really are spinning or spiralling: The Zitterbewegung Interpretation of Quantum Mechanics http://geocalc.clas.asu.edu/pdf/ZBW_I_QM.pdf http://geocalc.clas.asu.edu/pdf/ZBW_I_QM.pdf "The idea that the electron spin and magnetic moment are generated by a localized circulatory motion of the electron has been proposed independently by many physicists. Schroedinger’s zitterbewegung (zbw) model for such motion is especially noteworthy, because it is grounded in an analysis of solutions to the Dirac equation. Surely, if the zbw is a real physical phenomena, then it tells us something fundamental about the nature of the electron..."