Building a computer in Conway's game of life

Building a computer in Conway's game of life(nicolasloizeau.com)

227 points by ctlachance 5 years ago | 66 comments

lqet 5 years ago |

I remember seeing that video 3 years ago and being blown away.

In case someone doesn't already know it, here is Conway's Game of Life simulated in Conway's Game of Life:

https://www.youtube.com/watch?v=xP5-iIeKXE8

selestify 5 years ago | |

Blog post about the OTCA metapixel: https://web.archive.org/web/20200831001939/http://www.amanda...

Previous discussion: https://news.ycombinator.com/item?id=24323011

CGamesPlay 5 years ago |

So, for "pure" tasks which take input and produce output only at the very end, the Hashlife algorithm [0] allows you to run arbitrarily many generations of life in constant time at the expense of a huge internal cache (memory usage). That is, with Hashlife you can trade memory for computational efficiency. That means that for a sufficiently difficult task like mining bitcoin, this computer could be simulated faster than any conventional computer could run at the expense of using more memory.

My question: does anybody know what the ratio of trade-off between time and space is for Hashlife? I haven't been able to find anything from my searches.

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

im3w1l 5 years ago | |

You could do the same without transforming to game of life. Iterate over all possible states the memory can be in, and emulate a cpu with that memory for N steps.

But if you have 640 kilobytes memory (ought to be enough for anyone), that means your cache will have 2^640000 entries.

When transforming to game of life every bit of memory becomes many cells in the grid, so the requirements for that would be even worse.

ohazi 5 years ago | |

Hashlife can theoretically "cache" a specific input and output, e.g. running an instruction on your simulated computer like "add r0, r1, r2" (when r0, r1, and r2 contain specific values that have already been used with this instruction, and assuming that any nearby internal state is also identical).

But this doesn't let you magically mine bitcoin in fast-forward, because in order to mine bitcoin, you need to insert random bytes into your block and keep changing them until you get lucky and find a hash that starts with a certain number of zeroes. This effectively guarantees that you aren't going to have cached computation snippets that are big enough to skip any meaningful amount of work.

At best, you might be able to fast-forward at the instruction level granularity, at which point you might as well be mining on your CPU.

CDSlice 5 years ago | |

I'm not so sure this is correct. [0] says that Hashlife has logarithmic complexity on average. In the worst case it is O(n) since it could have to look at every element to see a pattern if one even exists [1]. Therefore the worst case for any algorithm running in a Life turing machine using HashLife is the same as if it was running directly on the machine.

[0] https://fanf.livejournal.com/83709.html [1] https://softwareengineering.stackexchange.com/questions/2345...

CGamesPlay 5 years ago | | |

Hmm, the phrasing on that first link does not lead to its stated conclusion:

> Hashlife can take the same length of time to compute from generation N to generation 2N for any large enough N - it has logarithmic complexity.

If 2N takes as much time as N, then 4N takes as much time as N, and so 8N takes as much as N, and so... (for any large enough N). This seems to indicate--asymptotically--constant time, not logarithmic.

travisoneill1 5 years ago | |

Memory access is generally much slower than computation, so I don't think you could actually speed up mining in this manner.

saagarjha 5 years ago |

See Quest for Tetris, a full processor implemented in Conway's Game of Life: https://codegolf.stackexchange.com/a/142673

Arcorann 5 years ago | |

That question is still open for submissions, and this computer looks to be significantly smaller than the one submitted there. If someone were willing to expand the computer a bit (memory currently seems a bit small) and then port Tetris to it then I suspect they'd be able to beat the QFT processor.

scollet 5 years ago | |

Well that's just nifty

jcims 5 years ago |

It’s interesting watching the messy complexity resolve into patterns and order as you zoom out.

It’s reminiscent of what it feels like to dig deeply into a metabolic or reproductive process in a cell and be overcome with the sheer complexity of it, then look at the back of your hand and realize it’s all happening right there, now.

Basically it feels a bit like life.

Aerroon 5 years ago | |

The first time I heard of Conway's Game of Life I was blown away. It was an example of potentially incredible complexity that can be arranged to large scale patterns emerge. It was the first time I took the idea of the universe being simulated (or created) seriously. Even more fascinating for me is the idea that we can't analytically calculate the outcome. To find out what happens we have to simulate it.

Even if the real world has a creator (or is a simulation), my money would be on it being impossible for the creator to know what is going to happen. Life would be the simulation.

jcims 5 years ago | | |

If you haven't seen it before this might blow you away haha - https://www.youtube.com/watch?v=ZKE8qK9UCrU

All of this is happening in my body right now so i can type these letters: WTF

Schiphol 5 years ago | | |

>we can't analytically calculate the outcome. To find out what happens we have to simulate it.

I've read Wolfram claim this, but as a conjecture, iirc. Is there a formal proof that in order to predict life patterns we essentially need to run the cellular automaton?

blintz 5 years ago |

Amazing how if you just stare at the logic gates you can kinda figure out what they mean. Makes you think maybe our meatware and the computers we use aren't as far apart as they seem.

dspillett 5 years ago |

Wow. I'm pretty sure I fully understand every concept involved, but I doubt I could put it all together.

Oddly beautiful seeing it run too. And the gliders flowing around put me in mind a bit of the ants that run Pratchett's Hex.

taneq 5 years ago | |

Just like building a real computer, you don't have to hold all of the concepts in your mind at once, just start with basic building blocks and work your way up the ladder of abstraction to parentheses or space invaders or whatever floats your boat. :)

dspillett 5 years ago | | |

That can fall down a little when it comes to debugging. You end up having to break everything back down to component parts more than if you could keep larger parts in your head at once.

I probably could do it, understanding all the parts implies that. Eventually. Just not in a reasonable amount of time, and perhaps not as neatly.

goldenkey 5 years ago |

I wonder what the most elegant Turing-complete universe is.

I believe it to be a system based on collision-based computing [1].

My hunch is this: Matter and Energy have a duality that is analogous to code and data. Einstein likened the speed of light to the speed of information. Wolfram/Toffoli/Fredkin or well, any other Cellular Automata specialist, studied the rate of propagation in CA, Lyapunov exponents. [2]

Now it seems to me, that if we can create a digital system which provides for code <-> data duality analogous to Mass–energy equivalence [3], then we should be able to get stable structures that hold data, and stable processes that process data. I have tried for many years on and off with various CAs. Many of the CAs have been unconventional, like cells containing arrays of particles, particles being objects rather than simple numbers or enum types. And CAs based on reals or complex numbers or associated vector fields.

---------------------------

Experiments

https://github.com/churchofthought/ScatterLife (CUDA)

https://github.com/churchofthought/HexagonalComplexAutomata (WebGL 2.0)

https://github.com/churchofthought/Grautamaton (WebGL 2.0)

---------------------------

Example of a Complex-valued Cellular Automata based on Sandpile dynamics

Big Bang (video): https://photos.app.goo.gl/K7fovThbvatpmGQy5

End result (image): https://photos.app.goo.gl/n5amaqn8ZLVocn1Z6

---------------------------

[1] https://link.springer.com/referenceworkentry/10.1007%2F978-3...

[2] https://www.math.ucdavis.edu/~gravner/papers/AUTOMATA2014_15...

[3] https://en.wikipedia.org/wiki/Mass%E2%80%93energy_equivalenc...

Topolomancer 5 years ago |

This reminds me of 'Permutation City', one of my favourite sci-fi novels. Cellular automata play a pivotal role in this book, which, despite some small misgivings, has largely aged rather well.

beachy 5 years ago |

I have always wondered if intelligence could emerge from a game of life, given a massive board and sufficient random seeds.

thotsBgone 5 years ago | |

Given the fact that we can build a computer in the game of life, this breaks down to a simpler question: can we have intelligence in a computer? If so, it can also occur in the game of life.

Strilanc 5 years ago | |

It would be difficult. In particular, unlike in our world, it's very difficult to create anything like a stable membrane or barrier in the game of life. And patterns are extremely susceptible to falling apart if perturbed. So you would generally expect a game-of-life-based entity touching anything to die as a result.

FartyMcFarter 5 years ago | | |

Since the game of life is Turing complete, it can simulate any computer. If a computer can eventually simulate the world (including humans), so can the game of life.

This doesn't mean the patterns would visually look like cells and membranes though...

rantwasp 5 years ago | |

yes.

without any spoilers there are literally tens of books out there that explore this very same idea. (some of them hard scifi)

fblifeadvice645 5 years ago | | |

you could at least give some names :)

andrelaszlo 5 years ago |

Haha I posted this a few months ago: 4 points. HN is so random sometimes :D

brazzy 5 years ago | |

You get that on any platform where upvotes or likes increase visibility. Content quality provides at most a potential for popularity.

brundolf 5 years ago |

But can it run Doom?

FartyMcFarter 5 years ago | |

Yes. I don't expect anyone can simulate that at real-time speed though (unless they take a lot of shortcuts, e.g. simulating at a higher level, which becomes a bit pointless).

dllthomas 5 years ago | | |

https://en.wikipedia.org/wiki/Hashlife speeds things up a lot, although my uninformed guess is still not enough.

ctlachance 5 years ago | |

I suppose any Turing complete language could. You could run DOOM in PowerPoint if you were masochistic enough.

hedora 5 years ago | | |

There’s a Doom clone for excel:

https://m.youtube.com/watch?v=6jyOJsJlLhI