Hacker News Reader

Comment by tgb | Hacker News Reader

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

View on HN

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.

The following picture has two predecessor states:

    _____
    _____
    __x__
    _____
    __x__

They are:

    _____
    _____
    __xx_
    _____
    __x__

and

    _____
    _____
    __xx_
    _____
    __xx_

Edit: Also, this has zero predecessors:

    _x
    xx

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

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