10 ms·
A Lisp Interpreter Implemented in Conway's Game of Life
- algon33 5y agoHow come the GoL runtimes are only ~300 times longer than the VarLife runtimes? Is it because the metapixels can be more efficiently simulated than running the game of life rules? Or because of sparsity of cells or some-such thing? This is seriously cool BTW.
- contravariant 5y agoYou can simulate the metapixels singificantly faster using Hashlife by caching the results for previously seen patterns. There's a pretty interesting dr dobbs article describing the core idea [1]. [1]: https://www.drdobbs.com/windows/an-algorithm-for-compressing-space-and-t/184406478 https://www.drdobbs.com/windows/an-algorithm-for-compressing...
- spicybright 5y agoI still can't get over how much interest the game of life maintains since it's invention. It might just be my favorite "field" of CS at this point. It's such a satisfying intersection of maths, coding, "biology", and "biological engineering".
- pfarrell 5y agoTotally. It's amazing how much complexity arises from something so simple. Just like in the game itself :). We lost someone special when we lost John Conway.
- jonsen 5y agoWe've still got Stephen Wolfram.
- kitd 5y agoYou could add "existential philosophy" to the list too.
- Aperocky 5y agoI like to think of this as the power of simplicity. A transistor is a simple piece of electronic, when combined in billions, it supports the incredible information transformation we see today.
- mirekrusin 5y agoThis is great thought. How many transistors make computer interesting has some parallels with how many neutrons create consciousness.
- wanderingstan 5y agoI suspect you mean neurons, but yes, a given amount of neutrons are also apparently needed for consciousness!
- mirekrusin 5y agoYes neurons for some reason my phone doesn’t like it and autocorrects, missed it.
- jodrellblank 5y agoOne that Conway didn't like much, saying (roughly) that it had all been explored and proved and other work of his was more interesting - https://www.youtube.com/watch?v=E8kUJL04ELA https://www.youtube.com/watch?v=E8kUJL04ELA in this Numberphile interview with him.
- idiotsecant 5y agoThis reminds me a lot of the aging rockstar who hates the billboard top 10 hit that he always gets asked to play.
- smoldesu 5y agoIf you're Thom Yorke, you use that hatred to drive you to build your magnum opus. Though admittedly, I don't know how one could iterate on Game of Life. It's simplicity is part of what makes it so great.
- djtriptych 5y agoWell kinda. The Bends was next after Pablo Honey, which contained "Creep", the song Radiohead famously learned to hate. The "magnum opus" is typically said to be OK Computer, their 3rd album, 2 after Pablo. While it was certainly a departure, the band generally said they wanted a total artistic change in direction. Interesting though is the song "Iron Lung" on The Bends, which is a song about "Creep" where they refer to it as, among other things, a "total waste of time".
- a4isms 5y agoYes, and both have my sympathy. Sometimes, a musician revisits their earlier work and finds new things to explore. Joni Mitchell and Ryuchi Sakamoto come to mind. But other times, a musician feels that although their earlier work may be new and exciting to you, they are finding other things more engaging today and tire of answering questions about the old work with the same rote, trite answers. Over and over again. For someone constantly seeking fresh ground to cover, this attitude is an asset. p.s. In this discussion about comedy, Louis CK talks about a tip he got from George Carlin, namely to throw the old material out after a year and start over again, forcing yourself to find new things to say about the Universe. In the same discussion, Jerry Seinfeld explains that some of his material is ten years old, and he is still finding ways to sharpen and refine it. There is clearly no one right way about this. https://www.youtube.com/watch?v=OKY6BGcx37k https://www.youtube.com/watch?v=OKY6BGcx37k
- agumonkey 5y agosome people in biology labs also made a game of life out of dna tiles (google nicolas schabanel / damien woods)
- jimmyed 5y agoHas anyone done Conways game of life in Conways game of life?
- Ivoah 5y agoYes: https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
- contravariant 5y agoIn this case they're running lisp running in VarLife running in the game of life. This Varlife is simulated using the OTCA metapixel, which was designed to run the game of life inside the game of life, though it is more general and can therefore also be used to simulate VarLife.
- bglusman 5y agoYup. https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
- yoru-sulfur 5y agoYup https://youtube.com/watch?v=xP5-iIeKXE8 https://youtube.com/watch?v=xP5-iIeKXE8
- lambic 5y agoIt's cellular automata all the way down.
- nisa 5y agoNot so exciting but still pretty cool: Conways Game of Life in a few lines of otus lisp* https://github.com/yuriy-chumak/ol/blob/master/samples/Convey's%20Life/life.lisp https://github.com/yuriy-chumak/ol/blob/master/samples/Conve... * otus lisp is a descendant of owl lisp (https://www.youtube.com/watch?v=utOVF0U7Zd8 https://www.youtube.com/watch?v=utOVF0U7Zd8) with a nice ffi - http://yuriy-chumak.github.io/ol/ http://yuriy-chumak.github.io/ol/
- netizen-936824 5y agoI wonder when someone will code GoL inside GoL
- piannucci 5y agoLook up the OTCA metapixel.
- filoeleven 5y agoThis video doesn’t go into any detail, but is perhaps the best illustration of the concept. https://youtu.be/xP5-iIeKXE8 https://youtu.be/xP5-iIeKXE8 Edit: yes I am late to the party.
- yesenadam 5y agoA while ago... https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
- retrac 5y agoGiven there is a Lisp implementation of GoL and a GoL implementation of Lisp, it's already done!
- ColinWright 5y agoIt's already done: https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8
- 5y ago
- layer8 5y agoNext: Street Fighter II in Game of Life.
- Kim_Bruning 5y agoI knew GoL was turing complete so theoretically this should be possible. I just couldn't even imagine imagining wanting to try. So this is rather impressive.
- Waterluvian 5y agoI’ve got to imagine there’s some sort of GoL compiler that takes more writable code and compiles it to a board state, given we know about a whole set of machines that do specific things (gates and whatnot)
- jacquesm 5y agoThere is a rather roundabout route to compiling software to game of life cells that is pretty interesting. It is of course completely impractical but the idea that it could be done is intriguing.
- OscarCunningham 5y agohttps://www.conwaylife.com/wiki/APGsembly https://www.conwaylife.com/wiki/APGsembly
- retrac 5y agoNot too different in concept to automated IC layout from Verilog or VHDL.
- colejohnson66 5y agoThen you’ll be pleased to know that some crazy people worked to build an entire computer architecture using metapixels just to play Tetris: https://codegolf.stackexchange.com/a/142673 https://codegolf.stackexchange.com/a/142673
- onemoresoop 5y agoNext target is a bacteria based lisp.
- vzaliva 5y agoNow we need to find Life implementation in List and bootstrap it from there.
- Aperocky 5y agoShameless plug: Have some fun over possible setups of cellular-automata (which conway's game of life is a subset of): http://aperocky.com/cellular-automata/ http://aperocky.com/cellular-automata/
- galaxyLogic 5y agoWhat is special about Game Of Life? Why does it seem to be the most "interesting" cellular automaton?
- ColinWright 5y agoIt's simple, small, clean, and Turing Complete. Most others show "interesting behaviour" (for some definition thereof) but are not Turing Complete (though some are). I've not found a CA that's Turing Complete and as small and easy to understand (which is not to say there isn't one).
- spicybright 5y agoI think it's just inertia. It's the most popular and well researched one at this point. There's definitely tons of other less researched rules that are as interesting.
- gumby 5y agoLove this. Next step: host Emacs on life.
- BoxOfRain 5y agoStep after that, bitcoin but it's on DNA strands and new coins are generated every time the host cell reproduces. The maximum number of coins is reached when the biosphere is reduced to an amorphous grey goo.
- jstx1 5y agoCan anyone explain in an accessible way how we go from a changing pattern on a 2d grid to "add these 2 numbers" or "if x do y"?
- elitepleb 5y agoHere's a nice writeup for that https://nicholas.carlini.com/writing/2020/digital-logic-game-of-life.html https://nicholas.carlini.com/writing/2020/digital-logic-game...
- OscarCunningham 5y agoThe long answer: https://conwaylife.com/book/ https://conwaylife.com/book/
- davesque 5y agoOne interesting thing about this is that it serves as a kind of simplified demonstration of the kind of computation that must be occurring or could occur with actual cellular biology. DNA really seems somewhat like a tape in a Turing machine (although technically a read-only one). But the entire system does compute a result which is an organism.
- AprilArcus 5y agoYou might be interested to learn that DNA is not actually read-only. Besides viruses like HIV and transposable elements which permanently splice themselves in to the host's DNA, antibodies gain specificity through irreversible self-editing of the lymphocyte's genome via a similar (and perhaps, evolutionarily related) mechanism. https://en.wikipedia.org/wiki/V(D)J_recombination https://en.wikipedia.org/wiki/V(D)J_recombination
- davesque 5y agoFascinating. Thanks so much for this! Natural biology really is miraculous (to use a loaded term).
- WJW 5y agoBiology uses only global variables. All processes can write to all others. We wouldn't do this in software because the human mind can't handle it (leading to bugs), but evolution has no such constraint.
- roflc0ptic 5y agoAs a metaphor that really doesn’t work. Biology is incredibly hype about modularization and separation of concerns. The human body rather goes out of its way to prevent arbitrary changes, both exogenous and endogenous
- kevin_thibedeau 5y agoThere's also epigenetics controlling gene activation, some of which is inheritable based on a parent's environmental exposures.
- galaxyLogic 5y agoIs there any hardware designed to just run cellular automata? I wonder if it could actually be a very efficient form of calculation, because cells are almost bits, but seem to possess more power than bits. For instance this Lisp in GoL. Could it run faster than lisps on "bit processors" if it ran on special purpose hardware? So instead of 64-bit processors we might have "64-cell processors" ?
- nynx 5y agoYou could totally design a chip that runs some cellular automata or another, but there's not much point aside from it being cool.
- m12k 5y agoDo modern graphics cards have optimizations for applying a kernel to a texture? If so, that should work well with cellular automata too
- eesmith 5y agoGoL implementations for big systems don't evaluate the cellular automata step-by-step. They implement HashLife - https://en.wikipedia.org/wiki/Hashlife https://en.wikipedia.org/wiki/Hashlife . The first example on that page shows position 6.3+ octillion for a Turing machine, computed in under 30 seconds. If the special purpose hardware ran at 1 THz, it would take about 4 quadrillion seconds to get to the same point, which is a bit over 200 million years.
- galaxyLogic 5y agoSpecial-purpose hardware for cellular automata would not evaluate it "step-by-step" either, but in parallel. Every cell could evaluate its next state independently of others. We could think of some kind of version of RAM where each 'cell' would implement this behavior. Perhaps similar optimizations like HashLife could be developed for such special purpose hardware as well.
- rezmason 5y ago
- davesque 5y agoThis makes me wonder. If cells were occasionally activated in random positions, what sorts of modifications to the architecture would be necessary to make the system robust and still able to carry out its computations with a reasonable probability of success? Would that even be possible? In other words, what kinds of modifications to this system would make it more like a natural biological system that has to cope with noise and interference from its environment?
- Mathnerd314 5y agoCells activating in random positions seems like a high bar. How robust are you to a rock suddenly appearing inside your body? (e.g. inside your heart?) A lower bar might be being robust to individual spaceships/gliders coming in from outside. But even there a collection of gliders is probably going to break through.
- davesque 5y agoYep, restricting things to coming from the outside might be more of a realistic challenge. I think I had a more academic version of the question in mind. Seems like we already have tech that is designed to handle a certain degree of pure randomness. For example, we have error-checked RAM.
- drdeca 5y agoI think it would be cool to have a structure with a line where, no matter where vertically (within a large range of vertical positions) a single glider crossed the line to the right , and no matter which of the 4(?) phases the glider has, signals would be sent somewhere indicating generally where the glider crossed, and the structure eventually returning to how it was (other than the signals it sent out) . Is such a structure possible? If so, how short can its recovery time be? How good can the resolution of how specifically it detects the locations of the gliders be? We know that GoL is Turing complete, and if the field is initialized with random noise, then for any fixed finite pattern, as the board size goes to infinity, the probability that that pattern appears somewhere in the noise approaches 1. (of course, I'm talking about enormous board sizes, possibly with many many more cells than there are protons in the visible universe, not talking about anything resembling practicality.) If intelligence and agency is computable (which, it seems like it should be), "any fixed finite pattern" would include structures which, for some amount of time, before they are destroyed by surrounding noise, would simulate an intelligent agent. If there are structures which, when surrounded by stuff initialized with noise, has a high probability of being able to withstand this noise, and then proceed to clear out the noise in order to e.g. make copy of itself, or just to grow, then we would expect the fraction of an infinite board containing such patterns (or things derived from them) to grow over time. But, whether such structures can exist in GoL, in part depends, I think, on whether any large structures can withstand noise (or, having a high chance of withstanding it). (I am defining "structures" in a way where a structure is allowed to include as part of it a large empty region (of any fixed size) on its periphery. This should assist in withstanding the noise, because it limits what things the core part of the structure could be faced with, to things which can travel a distance)
- waspentalive 5y agoNow all we need is Conway's Game of Life written in this lisp.