The Single Rotation rule: simple and rich reversible cellular automaton (2013) | Hacker News Reader

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

dmishin.blogspot.com

112 pointsbemmu19 comments

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?

momentum maps pretty strangely to automata, since to move more slowly you need a more complicated spaceship

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/R...

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

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

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

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

Thanks, I'll check some of these out! Sounds like a very fun project.

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

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

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.

That's not reversible -- there is no preceding state for the one-cell state.

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.

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

The following picture has two predecessor states:

    _____
    _____
    __x__
    _____
    __x__

They are:

    _____
    _____
    __xx_
    _____
    __x__

and

    _____
    _____
    __xx_
    _____
    __xx_

Edit: Also, this has zero predecessors:

    _x
    xx

Sorry, not sure I understand. What is this a counterexample of?

A counterexample to your claim that mass cannot grow infinitely. It doesn't work though...

That wasn't my claim though, since I was assuming finiteness of the system.

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.

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

Reply on news.ycombinator.com