5 ms·

A Computer in the Game of Life (2020)

2 points by Hooke 5y ago

tobyhinloopen 5y ago
How are these huge “maps” of game of life simulated at these speeds anyway
- ColinWright 5y ago
  It uses "Golly": http://golly.sourceforge.net/ http://golly.sourceforge.net/
- Doxin 5y ago
  A quadtree, where every node is first looked up in a hash table before simulating it. Eventually the hash table has enough entries to where most changes aren't even simulated but just looked up. It's a pretty plain CPU/memory tradeoff, but it works surprisingly well for game of life.
  - tobyhinloopen 5y ago
    https://en.m.wikipedia.org/wiki/Hashlife https://en.m.wikipedia.org/wiki/Hashlife Nice
OneTimePetes 5y ago
This is how the ideal machine architecture should look like.. Massive parallelism, as in every cell is a core. Implicit transport- as in every core without instructions to handle data, forwards it to the next core. Packages can contain instructions for cores. A program is nothing but data flowing through the area, marshalled into streams by the embedded instructions within the data. If a core is not busy, it can switch "location" todo the task of a busy core, thus the computational substrate is as big as the traversing packages need it be. The location is virtual, the core assigned to a package is real. The output is nothing but little blackholes, swallowing the result from the universe. This is how our universes simulation architecture looks like.
- holoduke 5y ago
  A bit how shader units are implemented right
  - OneTimePetes 5y ago
    Yes.. and you can see the emergency of what one could call physics as properties of the data flow. You have a light cone, as in data, can not move faster then the processing speed from field to field. You can even remove parts of the universe temporary, as long as its out of reach of the other parts.
- pyinstallwoes 5y ago
  That's a bit what Dave is working on with https://movablefeastmachine.org/ https://movablefeastmachine.org/ no? See: https://www.cs.unm.edu/~ackley/#rh-is https://www.cs.unm.edu/~ackley/#rh-is
  - pyinstallwoes 5y ago
    Or also mov based architectures?
nathell 5y ago
Another computer implemented in Life (that isn’t covered by the article) is the OTCA-metapixel-based one in which Tetris was implemented: https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life https://codegolf.stackexchange.com/questions/11880/build-a-w...
cjg 5y ago
Game of Life has the hashlife algorithm that can provide exponential speed-ups but with increased memory usage. A computer in the Game of Life therefore implies there is an algorithm that can exponentially speed up arbitrary computation - again at the cost of memory overhead. Does this say anything towards P=NP or other complexity questions?
- Strilanc 5y ago
  Hashlife only gets exponential speedups when patterns repeat with exponentially large periods. The relevant parts of an algorithm solving an NP-complete problem aren't going to repeat in the right way to get the speedup.
jbotz 5y ago
Here's a thought experiment that may illuminate some of the deepest questions of metaphysics... First, any given configuration in Conway's Life (hence CL) can be said to exist regardless of whether it is being currently executed (or simulated) in on some external physical machine. That's why we say that we "discovered" rather than "invented" interesting configurations within CL. So the existence of anything within the CL universe independent of its simulation... "running" a particular configuration on our computer is just a way for us to visualize this existence. CL configurations exist in kind of Platonic parallel universe of pure math or information, and a software implementation of CL is a window into that Universe. Now let's assume for a moment that AGI is possible, i.e. that any turing machine can become a conscious mind (given the right software, enough processing power, and time). Then that means there are minds in the CL universe... they exist, regardless of whether we are simulating them or not. But since the CL configurations in which they exists are enormously complex, we may never actually simulate any of them. Yet they exist, and if we do "discover" one of them we could run it multiple times, always with the same result... that would be just like window into that mind's existence that, like a movie, we can play again and again, but the existence is independent of our running it. Now let's try to put ourselves for a moment into one of these minds... to it, its world is physical, it can be sensed and manipulated. It is "real" like our own world is real to us, but again, that reality is independent of the CL configuration ever being simulated. It is a mathematical reality that appears hypothetical to us, but it has physical form to the minds within, regardless of being simulated; our simulating any CL configuration only makes it observable for us, it has no bearing on its internal reality. So now we have a very useful distinction between the terms "existence" and "reality"... the former is universal, the later refers to the perspective of a mind. So, what does all this mean with respect to our own reality? Well, first of all it means that asking whether our own reality might be a simulation (as some philosophers and even physicists have done in recent years [1]) is really kind of irrelevant. Our existence is in some sense just as mathematical as CL (at least if the universe is in any sense deterministic), but that math doesn't need to be simulated or executed by any external machine for it to be real and physical to us. In other words, "it from bit" [2]. Secondly, it suggests that we may be able to find a mathematical way of determining whether or not we can ever truly know the fundamental nature of our reality... all we have to do is figure out if a CL mind can discover the rules of the cellular automaton in which it exists. Thirdly, it means that everything exists, every imaginable type of "universe" has existence [3], but only those which can give rise to minds have reality, because "realness" is a property of mind, not of universes. [1] https://www.scientificamerican.com/article/do-we-live-in-a-simulation-chances-are-about-50-50/ https://www.scientificamerican.com/article/do-we-live-in-a-s... [2] See John Wheeler's 1989 paper with this title [3] I.e. there is a "level 4" multiverse according to Max Tegmark's hierarchy of multiverses; https://space.mit.edu/home/tegmark/multiverse.pdf https://space.mit.edu/home/tegmark/multiverse.pdf

2 points by Hooke 5y ago

tobyhinloopen 5y ago

How are these huge “maps” of game of life simulated at these speeds anyway

ColinWright 5y ago
It uses "Golly": http://golly.sourceforge.net/ http://golly.sourceforge.net/
Doxin 5y ago
A quadtree, where every node is first looked up in a hash table before simulating it. Eventually the hash table has enough entries to where most changes aren't even simulated but just looked up. It's a pretty plain CPU/memory tradeoff, but it works surprisingly well for game of life.
- tobyhinloopen 5y ago
  https://en.m.wikipedia.org/wiki/Hashlife https://en.m.wikipedia.org/wiki/Hashlife Nice

OneTimePetes 5y ago

This is how the ideal machine architecture should look like.. Massive parallelism, as in every cell is a core. Implicit transport- as in every core without instructions to handle data, forwards it to the next core. Packages can contain instructions for cores. A program is nothing but data flowing through the area, marshalled into streams by the embedded instructions within the data. If a core is not busy, it can switch "location" todo the task of a busy core, thus the computational substrate is as big as the traversing packages need it be. The location is virtual, the core assigned to a package is real. The output is nothing but little blackholes, swallowing the result from the universe. This is how our universes simulation architecture looks like.

holoduke 5y ago
A bit how shader units are implemented right
- OneTimePetes 5y ago
  Yes.. and you can see the emergency of what one could call physics as properties of the data flow. You have a light cone, as in data, can not move faster then the processing speed from field to field. You can even remove parts of the universe temporary, as long as its out of reach of the other parts.
pyinstallwoes 5y ago
That's a bit what Dave is working on with https://movablefeastmachine.org/ https://movablefeastmachine.org/ no? See: https://www.cs.unm.edu/~ackley/#rh-is https://www.cs.unm.edu/~ackley/#rh-is
- pyinstallwoes 5y ago
  Or also mov based architectures?

nathell 5y ago

Another computer implemented in Life (that isn’t covered by the article) is the OTCA-metapixel-based one in which Tetris was implemented: https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life https://codegolf.stackexchange.com/questions/11880/build-a-w...

cjg 5y ago

Game of Life has the hashlife algorithm that can provide exponential speed-ups but with increased memory usage. A computer in the Game of Life therefore implies there is an algorithm that can exponentially speed up arbitrary computation - again at the cost of memory overhead. Does this say anything towards P=NP or other complexity questions?

Strilanc 5y ago
Hashlife only gets exponential speedups when patterns repeat with exponentially large periods. The relevant parts of an algorithm solving an NP-complete problem aren't going to repeat in the right way to get the speedup.

jbotz 5y ago

Here's a thought experiment that may illuminate some of the deepest questions of metaphysics... First, any given configuration in Conway's Life (hence CL) can be said to exist regardless of whether it is being currently executed (or simulated) in on some external physical machine. That's why we say that we "discovered" rather than "invented" interesting configurations within CL. So the existence of anything within the CL universe independent of its simulation... "running" a particular configuration on our computer is just a way for us to visualize this existence. CL configurations exist in kind of Platonic parallel universe of pure math or information, and a software implementation of CL is a window into that Universe. Now let's assume for a moment that AGI is possible, i.e. that any turing machine can become a conscious mind (given the right software, enough processing power, and time). Then that means there are minds in the CL universe... they exist, regardless of whether we are simulating them or not. But since the CL configurations in which they exists are enormously complex, we may never actually simulate any of them. Yet they exist, and if we do "discover" one of them we could run it multiple times, always with the same result... that would be just like window into that mind's existence that, like a movie, we can play again and again, but the existence is independent of our running it. Now let's try to put ourselves for a moment into one of these minds... to it, its world is physical, it can be sensed and manipulated. It is "real" like our own world is real to us, but again, that reality is independent of the CL configuration ever being simulated. It is a mathematical reality that appears hypothetical to us, but it has physical form to the minds within, regardless of being simulated; our simulating any CL configuration only makes it observable for us, it has no bearing on its internal reality. So now we have a very useful distinction between the terms "existence" and "reality"... the former is universal, the later refers to the perspective of a mind. So, what does all this mean with respect to our own reality? Well, first of all it means that asking whether our own reality might be a simulation (as some philosophers and even physicists have done in recent years [1]) is really kind of irrelevant. Our existence is in some sense just as mathematical as CL (at least if the universe is in any sense deterministic), but that math doesn't need to be simulated or executed by any external machine for it to be real and physical to us. In other words, "it from bit" [2]. Secondly, it suggests that we may be able to find a mathematical way of determining whether or not we can ever truly know the fundamental nature of our reality... all we have to do is figure out if a CL mind can discover the rules of the cellular automaton in which it exists. Thirdly, it means that everything exists, every imaginable type of "universe" has existence [3], but only those which can give rise to minds have reality, because "realness" is a property of mind, not of universes. [1] https://www.scientificamerican.com/article/do-we-live-in-a-simulation-chances-are-about-50-50/ https://www.scientificamerican.com/article/do-we-live-in-a-s... [2] See John Wheeler's 1989 paper with this title [3] I.e. there is a "level 4" multiverse according to Max Tegmark's hierarchy of multiverses; https://space.mit.edu/home/tegmark/multiverse.pdf https://space.mit.edu/home/tegmark/multiverse.pdf