[HN Gopher] A Lisp Interpreter Implemented in Conway's Game of Life
___________________________________________________________________
A Lisp Interpreter Implemented in Conway's Game of Life
Author : ruidlopes
Score : 193 points
Date : 2021-12-23 13:30 UTC (9 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| spicybright wrote:
| I 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".
| kitd wrote:
| You could add "existential philosophy" to the list too.
| pfarrell wrote:
| Totally. 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 wrote:
| We've still got Stephen Wolfram.
| agumonkey wrote:
| some people in biology labs also made a game of life out of dna
| tiles (google nicolas schabanel / damien woods)
| Aperocky wrote:
| I 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 wrote:
| This is great thought. How many transistors make computer
| interesting has some parallels with how many neutrons create
| consciousness.
| wanderingstan wrote:
| I suspect you mean _neurons_ , but yes, a given amount of
| neutrons are also apparently needed for consciousness!
| jodrellblank wrote:
| One 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 in
| this Numberphile interview with him.
| idiotsecant wrote:
| This reminds me a lot of the aging rockstar who hates the
| billboard top 10 hit that he always gets asked to play.
| smoldesu wrote:
| If 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.
| a4isms wrote:
| Yes, 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
| isx726552 wrote:
| Like Jani Lane saying "I could shoot myself in the @#%*ing
| head" for writing "Cherry Pie" in the 80s:
|
| https://youtu.be/dNNa8wbKGb4
|
| I imagine there are a lot of people in this industry who
| feel that way about some their creations...
| jimmyed wrote:
| Has anyone done Conways game of life in Conways game of life?
| bglusman wrote:
| Yup. https://www.youtube.com/watch?v=xP5-iIeKXE8
| Ivoah wrote:
| Yes: https://www.youtube.com/watch?v=xP5-iIeKXE8
| contravariant wrote:
| In 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.
| yoru-sulfur wrote:
| Yup
|
| https://youtube.com/watch?v=xP5-iIeKXE8
| lambic wrote:
| It's cellular automata all the way down.
| davesque wrote:
| This 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 wrote:
| Cells 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.
| WJW wrote:
| Fascinating question. I suppose it depends on the size of the
| rock? Anything big "enough" would cause real problems, but a
| single molecule of rock would probably not matter too much.
| Presumably cosmic rays are triggering single neuron molecules
| all the time, but because there is a lot of redundancy this
| does not propagate into real activity.
| davesque wrote:
| Yep, 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 wrote:
| I 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)
| nisa wrote:
| Not 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/Conve...
|
| * otus lisp is a descendant of owl lisp
| (https://www.youtube.com/watch?v=utOVF0U7Zd8) with a nice ffi -
| http://yuriy-chumak.github.io/ol/
| netizen-936824 wrote:
| I wonder when someone will code GoL inside GoL
| yesenadam wrote:
| A while ago...
|
| https://www.youtube.com/watch?v=xP5-iIeKXE8
| ColinWright wrote:
| It's already done:
|
| https://www.youtube.com/watch?v=xP5-iIeKXE8
| retrac wrote:
| Given there is a Lisp implementation of GoL and a GoL
| implementation of Lisp, it's already done!
| piannucci wrote:
| Look up the OTCA metapixel.
| filoeleven wrote:
| This video doesn't go into any detail, but is perhaps the
| best illustration of the concept.
|
| https://youtu.be/xP5-iIeKXE8
|
| Edit: yes I am late to the party.
| layer8 wrote:
| Next: Street Fighter II in Game of Life.
| galaxyLogic wrote:
| Is 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 wrote:
| You could totally design a chip that runs some cellular
| automata or another, but there's not much point aside from it
| being cool.
| m12k wrote:
| Do modern graphics cards have optimizations for applying a
| kernel to a texture? If so, that should work well with cellular
| automata too
| eesmith wrote:
| GoL implementations for big systems don't evaluate the cellular
| automata step-by-step. They implement 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.
| gumby wrote:
| Love this. Next step: host Emacs on life.
| BoxOfRain wrote:
| Step 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.
| Kim_Bruning wrote:
| I 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 wrote:
| I'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 wrote:
| There 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 wrote:
| https://www.conwaylife.com/wiki/APGsembly
| retrac wrote:
| Not too different in concept to automated IC layout from
| Verilog or VHDL.
| colejohnson66 wrote:
| Then 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
| vzaliva wrote:
| Now we need to find Life implementation in List and bootstrap it
| from there.
| algon33 wrote:
| How 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 wrote:
| You 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...
| davesque wrote:
| One 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 wrote:
| You 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
| davesque wrote:
| Fascinating. Thanks so much for this! Natural biology really
| is miraculous (to use a loaded term).
| WJW wrote:
| Biology 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.
| onemoresoop wrote:
| Next target is a bacteria based lisp.
| retbull wrote:
| As long as I can install DOOM on it IDK about the platform.
| jstx1 wrote:
| Can 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 wrote:
| Here's a nice writeup for that
| https://nicholas.carlini.com/writing/2020/digital-logic-game...
| OscarCunningham wrote:
| The long answer: https://conwaylife.com/book/
| Aperocky wrote:
| Shameless 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/
| galaxyLogic wrote:
| What is special about Game Of Life? Why does it seem to be the
| most "interesting" cellular automaton?
___________________________________________________________________
(page generated 2021-12-23 23:00 UTC)