Schrödinger's Game of Life
Abstract
John Conway's Game of Life cellular automaton meets Schrödinger's Cat: cells may be Alive, or Dead, or PossiblyAlivePossiblyDead.
Description
Recall that in the Game of Life, cells may be Alive (which we will depict
as #
) or Dead (which we will depict as .
).
A cell that is Alive remains Alive if 2 or 3 of its neighbours are Alive; otherwise it becomes Dead.
A cell that is Dead becomes Alive if exactly 2 of its neighbours are Alive, otherwise it remains Dead.
("Neighbours" in this sense means a Moore neighbourhood: the 8 surrounding cells, both cardinals and diagonals.)
To this, we add a third cell type, PossiblyAlivePossiblyDead. (For
brevity, we will also call this type Cat.) We will depict it as ?
.
If a cell is Cat we must consider both possibilities; what would its next state be if it was Alive, and what would its next state be if it was Dead? If the answer to both of these questions is the same, then that is the outcome for that cell on the next state; but cells which have different outcomes under those two conditions themselves become Cat.
In fact, this is just a sort of nondeterministicification operation applied to the base cellular automaton, and such an operation could probably be applied to any cellular automaton.
We could certainly implement this in a bruteforce, checkallthepossibilities fashion. But observe that in a CA with only two states, adding nondeterminism like this is not any different from simply adding a third state, and figuring out the rules for the new set of states. It should be entirely possible to derive a sort of "closed form" of the nondeterministic behaviour, in terms of deterministic rules — not unlike the powerset construction which turns an NFA into a DFA — and that is what we shall attempt here.
I think it goes like this: instead of considering only the number of Alive neighbours, we must now consider two counts: the minimum number of Alive neighbours, and the maximum number of Alive neighbours. (Call these minalive and maxalive for brevity.)
 Each neighbouring
#
cell counts as minalive 1 and maxalive 1.  Each neighbouring
.
cell counts as minalive 0 and maxalive 0.  Each neighbouring
?
cell counts as minalive 0 and maxalive 1.
And for each cell, we simply sum these up to achieve these two counts.
As an example, the middle cell in the following diagram has minalive 1 and maxalive 6:
???
?x?
#..
Now, using these two counts, the new rules are:

A cell which is Alive:
 remains Alive if its minalive is 2 or 3 and its maxalive is 2 or 3.
 becomes Dead if its minalive is 4 or greater, or its maxalive is 1 or fewer.
 otherwise becomes Cat.

A cell which is Dead:
 becomes Alive if its minalive is 3 and its maxalive is 3.
 remains Dead if its minalive is 4 or greater, or its maxalive is 2 or fewer.
 otherwise becomes Cat.

A cell which is Cat:
 becomes Alive if its minalive is 3 and its maxalive is 3.
 becomes Dead if its minalive is 4 or greater, or its maxalive is 1 or fewer.
 otherwise remains Cat.
Now that we have stated the new rules, we see they are not particularly
difficult to implement, so, that is just what we have done. However,
this matter of there being two counts for each cell is a bit more than
ALPACA can express, so the automaton has simply been implemented
from scratch in Python, in the file script/slife
in this repository.
(Note: there is also an implementation in Javascript, which can be used directly in your web browser, here: Schrödinger's Game of Life installation at Cat's Eye Technologies).
There is certainly some way to state the rules such that ALPACA could accept them. However, I have not worked it out, and I believe there is a good chance that such an "even more closed form" would only serve to overcomplicate the description. I shall leave the deriving of it as an exercise for the interested reader.
Anyway, now that we have an implementation, we can confirm that it meets our expectations by giving it a few example configurations to test it.
Examples
> Tests for functionality "Evolve Schroedinger's Life for 5 steps"
When a playfield consists solely of .
and #
cells, this cellular automaton
has precisely the same behaviour as John Conway's Game of Life. For example,
here is a glider:
 ............
 ............
 ............
 .....##.....
 ....#.#.....
 ......#.....
 ............
 ............
= ............................................................
= ............................................................
= ..............................#...........##..........##....
= .....##..........###..........##.........#.#...........##...
= ......##...........#.........#.#...........#..........#.....
= .....#............#.........................................
= ............................................................
= ............................................................
But now we turn our attention to the newcomer, Cat. The first thing to note is that in cases where, in Conway's Life, the result is the same regardless of whether the cell is Dead or Alive, the result will continue to be the same when the cell is Cat.
One such example is a lone cell, with no neighbours. Whether it be Dead or Alive, on the next turn, it will always be Dead.
 .....
 .....
 ..?..
 .....
 .....
= .........................
= .........................
= .........................
= .........................
= .........................
Another such example is the "selfhealing block": if a 2x2 block is missing a corner, or if that corner is present, the next configuration will always be a full 2x2 block.
 ......
 ......
 ..##..
 ..#?..
 ......
 ......
= ..............................
= ..............................
= ..##....##....##....##....##..
= ..##....##....##....##....##..
= ..............................
= ..............................
This extends to a fuse that ends in a block: it survives having a Cat at the end:
 .........
 ..##.....
 ..#.#....
 .....#...
 ......#..
 .......?.
 .........
= .............................................
= ..##.......##.......##.......##.......##.....
= ..#.#......#.#......#.?......#?.......##.....
= .....#........?..............................
= ......?......................................
= .............................................
= .............................................
Within this realm of predictability, some forms composed entirely of Cats behave remarkably similar to the same Alive forms. For example, the 2x2 block is stable:
 ......
 ......
 ..??..
 ..??..
 ......
 ......
= ..............................
= ..............................
= ..??....??....??....??....??..
= ..??....??....??....??....??..
= ..............................
= ..............................
And the blinker behaves conventionally:
 .......
 .......
 ...?...
 ...?...
 ...?...
 .......
 .......
= ...................................
= ...................................
= ..........?.............?..........
= ..???.....?.....???.....?.....???..
= ..........?.............?..........
= ...................................
= ...................................
In general, though, nondeterminism is nondeterminism. Adding ?
s to a
form adds uncertainty, and there are relatively few avenues in Life by which
uncertainty is reined in, as in the above examples. Thus, uncertainty tends
to propagate throughout the form, and, indeed, beyond.
Here is what happens if we try something which we are only mostly sure is a glider.
 ............
 ............
 ............
 .....##.....
 ....#.?.....
 ......#.....
 ............
 ............
= ............................................................
= ......................................................?.....
= ..............................?..........???.........???....
= .....#?..........???.........???.........???........?????...
= ......#?.........???.........???........?????.......?????...
= .....?............?..........???.........???........?????...
= ..........................................?..........???....
= ............................................................
In fact, this is not very different from a form which we are completely unsure if it's a glider:
 ............
 ............
 ............
 .....??.....
 ....?.?.....
 ......?.....
 ............
 ............
= ............................................................
= ......................................................?.....
= ..............................?..........???........????....
= .....??..........???........????........????.......??????...
= .....???........????........????.......??????......??????...
= .....?...........??.........????........????.......??????...
= .........................................??.........????....
= ............................................................
Obviously, if either of these were to continue to run for more generations, the entire space would continue to be filled up with Cats, unboundedly.
One way to think about this is that our probablyaglider actually represents two forms (one of which is a glider, the other isn't,) and our 5Cat couldbeaglider actually represents 2^5 = 32 different forms in nondeterministic superposition. In both cases, the Cats that exist after n generations constitute a sort of "convex hull", or upperbound approximation, of where the "influence" of all these original forms could possibly reach.
Discussion
Er, and that's it, really. I expect there are a few other forms which are stable even though they're made of Cats (an infinite barber pole probably is.) But the mathematics of it stop here, and if that's all you're interested in, you can stop reading. The rest of this document is purely opinion and blather.
This cellular automaton is an original idea — I came up with it myself, independently (the note "Design and implement a cellular automaton with a nondeterministic state" has been sitting in my ideas file since at least 2009, possibly 2007,) but I do not claim it is novel — in fact, I would be surprised if it hasn't been looked into before. I would not be surprised if it was mentioned in an academic paper I haven't read, possibly in an unpublished internal report (the kind that universities sometimes collect), possibly before I was even born. (I am mainly just making a distinction between "original" and "novel" here because sometimes people confuse the two.)
Obviously, I'm taking a few liberties with the title. Erwin Schrödinger did not invent this Game of Life. But that's not how it's supposed to be read. As an homage to Schrödinger, it would be even better if it was an automaton that incorporated the wave function somehow. I don't have any good ideas on how to go about that, though, and the mathematics of it would be a bit beyond me. (If you have any similar ideas though, I strongly encourage you to try them out!)
Two points of trivia:
One, I understand that there's a historicalorthographic theory that the shape
of the glyph ?
comes from a depiction of a cat's rear end, with its tail in
the air. If this is true, it's not inappropriate for our use of it to depict
Cat here, then.
Two, a stalemate in TicTacToe (a.k.a Noughts and Crosses) is sometimes called a Cat's Game. Being neither a Win nor a Loss, it also seems appropriate here.
Now, to regard those two things as anything but coincidences would be stretching things. However, we may well ask why Schrödinger chose a cat for his thought experiment in the first place, when a rabbit would have done just as well. Or a dog. Or a slime mold. Or... but wait, I'm getting ahead of myself.
I was going to write a whole long screed about Schrödinger's Cat here, but that sort of thing gets tiresome. So maybe I'll just leave you with a bit of terrible doggerel I wrote back in the mid90's:
We've all heard of Schrödinger's Cat,
That famous thought 'sperimentation.
But you don't suppose it's possible that
The cat made an observation?
Oh, I do apologize. And I can't bear closing on such a sour note. So, here's
Schrödinger's Cat: Extended Dance Mix
Carrying a live cat and a quantum boobytrap, you walk into a room, in which is a fellow experimenter and a table containing two open, empty boxes.
You give the items to your colleague, step out of the room, and close the door.
A minute later you open it again and walk back in. The boxes are closed and there is no sign of the cat or the deathtrap.
You check the environment carefully to ensure there are no hidden compartments and that your colleague has not eaten the cat.
You open one of the boxes.
What are the possible outcomes?
Which of these outcomes involve the collapsing of a quantum superposition, and which do not?
Why does the Copenhagen Interpretation tell us that predicting some of these outcomes is mere oddsmaking, while other outcomes involve such exotic concepts as being both dead and alive at the same time?
Is the wave function not just another mathematical model, like the parabola of Newtonian physics or the curved spacetime of Einsteinian relativity?
Why should we try to make our notions of ontology and epistomology bend over backwards for the sake of a mathematical model?
In conclusion, it's a safe bet that Dr. Quantum is bunko.
Happy "We need to talk"!
Chris Pressey, Cat's Eye Technologies
February 7, 2015
Reading, England, UK
Commit History
@master
git clone https://git.catseye.tc/SchroedingersGameofLife/
 This information is in the examplePrograms.jsonp.js, so use it. Chris Pressey 4 months ago
 Load all example programs at startup instead of XHR'ing each one. Chris Pressey 4 months ago
 Run tests w/Python 2, or 3, or both, depending on what's available. Chris Pressey 2 years ago
 Mercurial is no longer supported in this repo. Chris Pressey 2 years ago
 Make script run under both Python 2 and Python 3. Clean it up. Chris Pressey 2 years ago
 Refactor test suite. Chris Pressey 2 years ago
 Added tag 1.0 for changeset 2e82f581b128 Chris Pressey 8 years ago
 Add link to online installation in Javascript. Chris Pressey 8 years ago
 Add UNLICENSE. Chris Pressey 8 years ago
 Another minor edit. Chris Pressey 8 years ago