8 ms·
Building a computer in Conway's game of life
- last_frontier 6y agoCool and all that, but isn't this... practically and intellectually useless? Surely, you can build a computer using pebbles on the sea shore by aligning them in the specific order. How is that surprising?
- enoreyes 6y agoPerhaps this specific exercise does not necessarily generate any utility in and of itself, but the concept is certainly quite interesting. Many would argue a bunch of pebbles on the sea shore couldn't possibly be alive, yet many still hope we can bring life to a machine of silicon. Clearly there must be some difference between the two, unless there isn't. Relevant XKCD: https://xkcd.com/505/ https://xkcd.com/505/
- TobalJackson 6y agoHave you ever thought about what life is about for other people? Do you only think about eating, drinking, sleeping and exercise? I would counter your question by asking, isn't your comment here practically and intellectually useless?
- wombatmobile 6y ago> Do you only think about eating, drinking, sleeping and exercise? We need more than that. We need breathing, pissing, shitting, fighting, and sex.
- mensetmanusman 6y agoIt might be useful: We do not know how ‘soup of chemistry’ does information processing. (e.g. biology) The more it looks like soup, the more we might be able to intuit how to tackle things that are unbounded in complexity. E.g. how do millions of cells coordinate growth to make a new organ/repair and then stop, what are the chemical initial conditions that generate this complex orchestra, what tells it to stop, can we speak that language if we knew it?
- j4nt4b 6y agoAn obvious example would be intellectual cross-pollination. This project is likely to get a lot of exposure in the Game of Life community as well as the Computer Science community, increasing the chances that members of either community feel compelled to cross over and contribute in an area that may have previously seemed uninteresting/unpromising/unknown.
- monadgonad 6y agoWhile that's true for posts like this in general, in this specific case those communities are the same. Conway's Game of Life is a computer science curio.
- dang 6y agoThe interestingly useless and uselessly interesting are not only welcome here, they're at the apex of the tradition that HN (at its best) helps to continue. A post like this never needs an answer to "why"! https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- soared 6y agoYou can’t build a computer with pebbles though? OP is using basic Conway laws to build on logic gates.
- zamadatix 6y agoWhat's to stop you from making logic gates out of patterns of pebbles on a beach exactly?
- testermelon 6y agoBecause the pebbles stay there when nothing knock it off. And when something knock it off we can't reliably know where it will go?
- zamadatix 6y agoThere is nothing to knock of a starting condition for the GOL until you put energy into it. There is no reason, for instance, you couldn't have a little robot moving the pebbles according to GOL rules. If you say the robot is the thing doing the computation the such is the case of the computer running this GOL simulation. If you say it's not pebbles then imagine a mechanical computer built out of them. Provide some kinetic energy and rocks begin to compute just as the silicon in your computer begins to compute when you put electrical energy into it.
- scollet 6y agohttps://xkcd.com/505/ https://xkcd.com/505/ For any passerbys
- xaedes 6y agoWithout anyone performing the necessary pattern transformations to make it "work" this will be very static and boring... With computer in GOL you have GOL which will do the pattern transformations.
- 6y ago
- tasty_freeze 6y agoThey knew it was a low-quality question and so created a new account in order to post that comment. And despite knowing it was a crap comment, cared enough to make the effort to create the new account. I don't get some motivates some people.
- dspillett 6y agoThe joy of snark. Some get off on it quite easily.
- blintz 6y agoAmazing 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.
- lqet 6y agoI 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 https://www.youtube.com/watch?v=xP5-iIeKXE8
- selestify 6y agoBlog post about the OTCA metapixel: https://web.archive.org/web/20200831001939/http://www.amandaghassaei.com/blog/2020/05/01/the-recursive-universe/ https://web.archive.org/web/20200831001939/http://www.amanda... Previous discussion: https://news.ycombinator.com/item?id=24323011 https://news.ycombinator.com/item?id=24323011
- goldenkey 6y agoI 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 https://github.com/churchofthought/ScatterLife (CUDA) https://github.com/churchofthought/HexagonalComplexAutomata https://github.com/churchofthought/HexagonalComplexAutomata (WebGL 2.0) https://github.com/churchofthought/Grautamaton 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 https://photos.app.goo.gl/K7fovThbvatpmGQy5 End result (image): https://photos.app.goo.gl/n5amaqn8ZLVocn1Z6 https://photos.app.goo.gl/n5amaqn8ZLVocn1Z6 --------------------------- [1] https://link.springer.com/referenceworkentry/10.1007%2F978-3-540-92910-9_58 https://link.springer.com/referenceworkentry/10.1007%2F978-3... [2] https://www.math.ucdavis.edu/~gravner/papers/AUTOMATA2014_1509.pdf https://www.math.ucdavis.edu/~gravner/papers/AUTOMATA2014_15... [3] https://en.wikipedia.org/wiki/Mass%E2%80%93energy_equivalence https://en.wikipedia.org/wiki/Mass%E2%80%93energy_equivalenc...
- brundolf 6y agoBut can it run Doom?
- FartyMcFarter 6y agoYes. 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 6y agohttps://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife speeds things up a lot, although my uninformed guess is still not enough.
- ctlachance 6y agoI suppose any Turing complete language could. You could run DOOM in PowerPoint if you were masochistic enough.
- hedora 6y agoThere’s a Doom clone for excel: https://m.youtube.com/watch?v=6jyOJsJlLhI https://m.youtube.com/watch?v=6jyOJsJlLhI
- jcims 6y agoIt’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 6y agoThe 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 6y agoIf you haven't seen it before this might blow you away haha - https://www.youtube.com/watch?v=ZKE8qK9UCrU https://www.youtube.com/watch?v=ZKE8qK9UCrU All of this is happening in my body right now so i can type these letters: WTF
- Aerroon 6y agoI would've loved videos like this when I was studying Biology! This kind of explanation with the video is amazingly clear. It reminds me a lot of how the signal is generated in eyes through the build up of charge after light hits the retina.
- rantwasp 6y agomy favorite is https://youtu.be/LQmTKxI4Wn4 https://youtu.be/LQmTKxI4Wn4 once you look at microbiology you cannot unsee that it looks just like a massive, complicated stochasticaly-driven computer
- abraae 6y agoI have always wondered if intelligence could emerge from a game of life, given a massive board and sufficient random seeds.
- thotsBgone 6y agoGiven 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.
- rantwasp 6y agoyes. without any spoilers there are literally tens of books out there that explore this very same idea. (some of them hard scifi)
- fblifeadvice645 6y agoyou could at least give some names :)
- Strilanc 6y agoIt 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.
- 6y ago
- saagarjha 6y agoSee Quest for Tetris, a full processor implemented in Conway's Game of Life: https://codegolf.stackexchange.com/a/142673 https://codegolf.stackexchange.com/a/142673
- scollet 6y agoWell that's just nifty
- Arcorann 6y agoThat 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.
- CGamesPlay 6y agoSo, 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 https://en.wikipedia.org/wiki/Hashlife
- CDSlice 6y agoI'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 https://fanf.livejournal.com/83709.html [1] https://softwareengineering.stackexchange.com/questions/234548/what-are-the-consequences-of-hash-life-running-in-olog-n https://softwareengineering.stackexchange.com/questions/2345...
- CGamesPlay 6y agoHmm, 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 6y agoMemory access is generally much slower than computation, so I don't think you could actually speed up mining in this manner.
- 6y ago
- andrelaszlo 6y agoHaha I posted this a few months ago: 4 points. HN is so random sometimes :D
- brazzy 6y agoYou get that on any platform where upvotes or likes increase visibility. Content quality provides at most a potential for popularity.
- dspillett 6y agoWow. 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 6y agoJust 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 6y agoThat 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.
- Topolomancer 6y agoThis 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.