Hacker News Reader

Comment by fallingfrog | Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com