Hacker News Reader

Comment by teraflop | Hacker News Reader

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

View on HN

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.

Reply on news.ycombinator.com