Item — HN Reader

I’m assuming this is only achieved by “cheating” in some way? That is, I don’t see how giant pixels can come and go, at a zoomed in level, without breaking the rules of Conway’s game of life?

Still cool, but more curious to understand how this works, and if it’s actually able to pull it off “legitimately”.

4 comments

Yes, this is legitimate, and there's no cheating.

If you zoom in sufficiently, you can see that the "giant pixels" are really streams of spaceships, arranged in carefully positioned rows and columns that annihilate each other along the pixel's diagonal. These streams can be turned on or off to form the "display" component of each pixel, which is controlled by other parts of the pattern that do the actual computation.

As you zoom in or out, the simulation speed changes. A pixel seems to undergo a discrete state change when zoomed out, but when you zoom in and slow down, you can see how that change is actually executed by many underlying computational steps.

Other links in this thread go into more detail about how it works. The cleverest part is that the simulation is done in (more or less) "constant time" per frame, no matter how deeply you zoom or how fast you accelerate time.

That is a good summary, but of course, there is "cheating" to do the infinite amounts of work required in a finite time!

The board appears as if there exist at any time infinite levels of cellular automata going all the way down running things. In fact, they only compute one level deep and then short-circuit to using the "hardcoded" rules of Conway's life, and simply pop up the higher or lower levels on demand.

That's a fair point, but I don't consider that "cheating" any more than Hashlife [1] (which it's based on) is cheating. It's an ingenious trick that guarantees that what's displayed is exactly the same pattern as if all of the infinitely-many higher and lower levels had been simulated, in finite time. The rules of the cellular automaton are never broken, only elided.

In a metaphorical way, it reminds me of the "tying the knot" trick in pure functional languages like Haskell, to turn an infinite computation into a finite data structure.

[1]: https://en.wikipedia.org/wiki/Hashlife

Agreed, I think the key here is that the Game of Life is structured enough that many computational steps can be elided in this way. If it was more chaotic, this couldn't happen. The realization that GoL can be used to run one GoL cell in isolation is the brilliance here I think. Once you can decompose one single cell into GoL, you can also compose GoL into one cell and save computational cycles. Then suddenly it can be GoL all the way down.

A digression for anyone interested in Hashlife: I want to recommend Gosper's original paper [1] over the various other explanations of it. It is brief (6 pages), lucid, and was the paper that finally made me understand how hashlife works.

[1] https://www.lri.fr/~filliatr/m1/gol/gosper-84.pdf

Welllll, there seems to at least be some mathematical cheating in that this is representing a non-well-founded set. (Declare each pixel to be the set of subpixels at the next level down defining it, this forms an infinite descending chain).

I don't know the "tying the knot" trick, but I imagine it to be something like a proof by induction of self-simularity being exploited to share computation at different zoom levels.

I might be missing something, but I don't think you even need Hashlife for this. The pattern is regular enough that you could just flat out store a static (x, y, t, state) map of a single cell and apply it fractally in order to compute the state of any part of the map at any time in constant time. You don't even need to simulate it at all.

You may not consider it as cheating, but that's a reasonable interpretation barring pedantry and is likely what the parent comment was referring to.

It's no more cheating than the fact that 1 = 1/2 + 1/4 + 1/8 + 1/16 + ...

Despite the fact that you can never actually add up an infinite number of terms one by one, you can however, compute what the limit of the sum will be in a finite amount of time. The same principle applies to this simulation, in which it is computing the limit of the process.

Eliding intermediate strings of a term rewriting system when you can prove the answer without them isn't cheating in any sense of the term.

My point was that while it’s not cheating, you can easily infer “what they meant”, and as such don’t need to defend it’s lack of cheating.

There's a seriously incredible article on the guy's site where he explains how it works! It's very much worth a read, really cool stuff.

https://blog.oimo.io/2023/04/10/life-universe-en/

More intuitive if you zoom out: https://www.youtube.com/watch?v=xP5-iIeKXE8

It feels like cheating due to the first generation grid already being a complex pattern of spaceships, pulsars, breeders and replicators I think.