5 ms·

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

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

teraflop 3y ago
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.
- TomSwirly 3y ago
  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.
  - teraflop 3y ago
    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 https://en.wikipedia.org/wiki/Hashlife
    - ShamelessC 3y ago
      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.
      - Kranar 3y ago
        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.
      - samatman 3y ago
        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.
        ShamelessC 3y ago
        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.
    - Aurelius108 3y ago
      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.
    - karmakaze 3y ago
      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.
nolist_policy 3y ago
More intuitive if you zoom out: https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
epiccoleman 3y ago
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/ https://blog.oimo.io/2023/04/10/life-universe-en/
spacebacon 3y ago
It feels like cheating due to the first generation grid already being a complex pattern of spaceships, pulsars, breeders and replicators I think.

teraflop 3y ago

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.

TomSwirly 3y ago
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.
- teraflop 3y ago
  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 https://en.wikipedia.org/wiki/Hashlife
  - ShamelessC 3y ago
    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.
    - Kranar 3y ago
      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.
    - samatman 3y ago
      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.
      - ShamelessC 3y ago
        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.
  - Aurelius108 3y ago
    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.
  - karmakaze 3y ago
    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.

nolist_policy 3y ago

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

epiccoleman 3y ago

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/ https://blog.oimo.io/2023/04/10/life-universe-en/

spacebacon 3y ago

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