[HN Gopher] Lace: A New Kind of Cellular Automata Where Links Ma...
___________________________________________________________________
Lace: A New Kind of Cellular Automata Where Links Matter
Author : airesearcher
Score : 108 points
Date : 2025-10-16 13:33 UTC (9 hours ago)
(HTM) web link (www.novaspivack.com)
(TXT) w3m dump (www.novaspivack.com)
| airesearcher wrote:
| LACE - Link Automata Computing Engine
|
| (written in python, with optional taichi GPU-powered mode for
| large-scale simulations)
|
| LACE is a new kind of cellular automata where rules operate on
| cell states and their links to other cells.
|
| Check out the Gallery in
| https://www.novaspivack.com/science/introducing-lace-a-new-k...
| to see the familiar Game of Life rule, but with links.
|
| * Quick Examples **
|
| Game of Life, with links: https://videopress.com/v/lTZ8e4hD
|
| Amazing Dragons (LACE rules): https://videopress.com/v/lQ5Bghsj
|
| ** MANY more examples in the Gallery (in the blog post cited
| above)
|
| Rules can use topological properties of cells and neighborhoods,
| such as number of connections, neighbor degree, and other
| metrics.
|
| The added topological dimension enables rules that can have more
| interesting behavior than traditional "cells-only" CA rules,
| opening up a fascinating new computational world of new species
| of stable patterns - oscillators - gliders, puffers, and more.
|
| For details on how these rules work, get the repo and open
| various rules in the rule editor, where all their parameters are
| explained. There are many new classes of rules to experiment
| with.
|
| ** You can get the repo and learn more at:
| https://github.com/novaspivack/lace
| analog8374 wrote:
| That's pretty darn cool.
|
| How might you increase the overall order and decrease the chaos?
| airesearcher wrote:
| Good question... and I explored this a lot in the rules - some
| of the parameters are extremely sensitive... so it takes a lot
| of trial and error...
| airesearcher wrote:
| Realm of Lace Rules The signature "Realm of Lace" family of
| rules uses:
|
| Birth conditions: Based on sum of neighbor degrees Survival
| conditions: Based on sum of neighbor degrees Death conditions:
| Specific degree counts that cause node death Eligibility: Nodes
| must meet conditions to form connections
| dvt wrote:
| This is really cool, I wish they explained what the rules were;
| for example, the "Amazing Dragons" seems to self-organize very
| neatly, but I'm not really sure why it has that behavior.
| airesearcher wrote:
| Yeah thanks for the feedback - explaining the rules would
| require a longer write-up so I opted for the late binding
| path... in the repo there is a rule editor, and it explains the
| parameters of every rule in the GUI. It's a lot easier since
| there are many different kinds of rules and many parameters to
| explore.
| airesearcher wrote:
| Birth conditions: Based on sum of neighbor degrees
|
| Survival conditions: Based on sum of neighbor degrees
|
| Death conditions: Specific degree counts that cause node death
|
| Eligibility: Nodes must meet conditions to form connections
| user____name wrote:
| Did you end up simulating the mouse brain after the LSD trip?
| airesearcher wrote:
| hahaha ... I actually wondered if someone dosed me... but no
| that was not possible in that situation at that time (and it
| would have had to be an elephant dose to last a week). Yes, I
| did try to simulate a mouse brain... but on a Mac 128 that was
| rather intractable at the time (actually it still is...)
| golol wrote:
| This is pretty cool. I have several points to make. 1. We all
| know that Cellular automata or more generally any dynamical
| system of sufficient complexity (and maybe not too much
| complexity) will be Turing complete, will have complicated
| "uncomputable" behavior, will have perhaps pattern formation, or
| gliders, solitons etc. So what is a valuable addition to this
| these computational investigations? I think when studying
| emergent computational behavior we really care about dynamics
| complexity / rules complexity. It's not impressive to get
| complicated dynamics out of a complicated system but the
| simplicity of game of life made it really impressive. I think in
| that regard LACE is pretty nice: the rule still feels very
| simple/natural and you can get much more structured/complex
| behavior with fewer cells.
|
| 2. Nevertheless in the end this blog shows mostly pretty pictures
| of computational, complex, emergent, chaotic behavior, which
| we've all seen before. And the key features that make the
| difference go something I would call _physics_ -like are still
| missing. And I guess that would be complex _stable_ patterns that
| can have complex _stable_ interactions. Who knows maybe there are
| 10^16-celled patterns that have this but we don 't know.
|
| 3. If I were you I would cut the whole preamble. It will make
| people take you less seriously than they should. You don't want
| to look like a crank.
| sushisource wrote:
| +1 to this copy being a little bit over-the-top. This is neat,
| but, as you pointed out at the end of the day this is still
| computationally equivalent to normal 2d cellular automata. I
| suspect (not taking the time to prove this) that it's equal in
| a fairly obvious way, which is that you could just replace
| "links" with 8*<num link states> additional sub-states per
| cell. The only real difference is just in how it's visualized.
|
| So, neat, but not exactly mindblowing.
| airesearcher wrote:
| In theory, if using a computationally universal CA, you can
| simulate any other CA with it. However it might require a lot
| of sub-steps to do so.
|
| No claim is being made that this is a new kind of
| computation.
| Isamu wrote:
| The observation that other CA can be equivalent is a weak
| critique at best, this CA may be a nice compact way of
| describing types of CA that have interesting properties. It
| is not terribly interesting that it may be subsumed by some
| other CA. It may be some interesting unstudied subset.
|
| For instance the Game of Life is a subset of 2-d binary
| state CA, the rule only takes the totals of neighboring
| cells, and so is a subset of those CAs with rules that care
| about specific patterns of neighbors.
| airesearcher wrote:
| The question is really whether this class of rule is a
| subset of 2D binary state CA, or whether it is a superset
| in fact.
| airesearcher wrote:
| Good feedback -
|
| These rules use very different principles than traditional
| cell-based rules - for example neighbor degree, number of
| connections, and eligibility criteria based on connectivity. So
| the cells are not becoming alive or dead based on the states of
| their neighbors, but rather on the topology of their
| neighborhoods.
|
| The details are beyond the scope of a short write up, but are
| easy to explore in the rule-editor in the GUI of the code.
|
| And preamble pruned of the historical anecdote behind this.
| TophWells wrote:
| So what actually is it? None of the rules in the videos look
| particularly striking compared to other Life-like cellular
| automata and 2d cellular automata in general. As you say, their
| behaviour includes oscillators, spaceships, patterns that grow
| endlessly... all things that are well-known from other cellular
| automata. So the videos didn't really show off why they're
| interesting.
|
| I don't mind the rambling about "planets, galaxies, galaxy
| clusters, superclusters... and beyond ...." but some technical
| detail would be nice too!
| airesearcher wrote:
| These rules use very different principles than traditional
| cell-based rules - for example neighbor degree, number of
| connections, and eligibility criteria based on connectivity.
|
| So in short, the cells are not becoming alive or dead based on
| the states of their neighbors, but rather on the topology of
| their neighborhoods.
|
| The details are beyond the scope of a short write up, but are
| easy to explore in the rule-editor in the GUI of the code.
|
| Here is an example of a rule that is markedly different from a
| typical "life-like" rule: https://videopress.com/v/lQ5Bghsj
|
| The level of structure and self-organization is striking, to me
| at least.
|
| Also in all the rules - the links are visible and can have
| binary or real-valued states as well as the cells. So this
| enables pretty rich topology which rules can utilize.
| TophWells wrote:
| Could you try explaining it in a comment? Not the general
| principle, but just the rules for one particular automaton.
| Whichever one is your favourite. Or Amazing Dragons, if you
| don't have a favourite.
|
| The amazing part of cellular automata is the emergence of
| complicated behaviour from simple rules. Life's rules can be
| written in three sentences, maybe less.
|
| Forgive my quibbling, but I don't understand what this is
| doing that other projects in this space haven't done before.
| Adding states and transition rules to edges is new to me...
|
| I did try running your project, but I had to tweak it to get
| it to work with the instructions in the repo. I seem to be
| missing a few packages -- mpmath, sympy, typing_extensions.
| Can you add those to the requirements.txt file?
| TophWells wrote:
| Let's see if I understood this right. For the Betweenness
| Amazing Dragons rule:
|
| * Compute the "betweenness" of each living cell, which is 1
| divided by its degree. Cells which are not connected to
| anything have infinite/undefined betweenness, but it
| doesn't matter.
|
| * Then, for each cell, sum up the betweenness of its
| connected neighbours.
|
| * If the total betweenness of a dead cell is in the range
| [(1.3, 3.6)], it is born and becomes alive at the next
| generation.
|
| * If the total betweenness of a living cell is in the range
| [(0.9, 2.6)], it survives and remains alive to the next
| generation.
|
| * Exception: any cell with 0, 1, 7 or 8 neighbours (in
| total, ignoring betweenness) dies anyway after the rules
| above were applied.
|
| ... That's not quite right, there's some references to
| "eligibility" that I can't make sense of. What else am I
| missing?
| airesearcher wrote:
| I've added a bit more explanation
|
| https://github.com/novaspivack/lace/blob/master/Rule_Expl
| ana...
|
| https://github.com/novaspivack/lace/blob/master/Betweenne
| ss_...
|
| These cover only one metric and one rule, but give some
| more info
|
| Here is a more detailed explanation: https://github.com/n
| ovaspivack/lace/blob/master/Realm_of_Lac...
| bee_rider wrote:
| Game of life on a sphere could be nice. I never really liked how
| the gliders would just go off into nowhere.
|
| Although I guess if we play with this too much there is a risk of
| inventing something like... Bloch's Game of Life or something.
| TophWells wrote:
| The Game of Life implementation in this post is based on a
| torus. Watch the gliders when they go off the edge of the
| screen: they return from the other side!
| wbolt wrote:
| Actually most of CA simulations are done on torus which is
| referred to as periodic boundary conditions in the
| literature. Alternatively you can also have null (or fixed)
| boundaries or reflective ones. If the initial configuration
| has compact support (finite number of non-null states) and
| the CA keeps null-neighborhoods as null in the next step, you
| can simulate infinite grids... but not many people bother to
| do it. Many many papers use finite grids on torus.
| nh23423fefe wrote:
| probably torus. could you actually discretize the sphere
| properly? isnt this like tessellating a soccer ball?
| wat10000 wrote:
| You can get the topology of a sphere with holes at the poles
| by wrapping left/right but not up/down, like the Civilization
| games. Or you can do it with no holes by having left/right
| wrap, and top/bottom do a different wrap where you come back
| from the same direction but halfway around horizontally.
| (Imagine the path crossing over the poles projected onto a
| Mercator map.)
| abdullahkhalids wrote:
| Have they proven their computational model is inequivalent to
| cellular automata? It is possible that the link rules could be
| translated into cell rules in regular cellular automata.
|
| That said a different representation can always reveal new
| phenomena about an old model.
| crdrost wrote:
| I mean even phrasing what you're trying to do there, would be a
| big difficult task.
|
| Consider e.g. that Game of Life has had folks build universal
| Turing machines for it, and those machines can be programmed to
| run a Lace automaton.
| binary132 wrote:
| Maybe I'm missing something, but it seems to me like these links
| are just visualizing the adjacencies which govern existing
| cellular automata.
| airesearcher wrote:
| Yes you are missing something. The first examples do that, but
| later examples do something different - they are using the
| neighborhood topology instead of traditional cell states, to
| generate the behavior.
| airesearcher wrote:
| https://github.com/novaspivack/lace/blob/master/Rule_Explana.
| ..
|
| https://github.com/novaspivack/lace/blob/master/Betweenness_.
| ..
| clearleaf wrote:
| If we had a grid of cells where each cell was a number from
| 0-8, representing the number of neighbours, would that be
| equivalent to what these "links" are? I'm still finding it
| hard to understand.
| airesearcher wrote:
| links are first-class entities. Some rules have cell
| states AND links. Some rules treat cell states as
| topological metrics of neighborhoods or neighbors. See
| the detailed .md cited above for more details.
| wbolt wrote:
| This is interesting and may reveal additional properties
| of certain class of CAs.
|
| Yet, as some comments already stated what you do is
| basically study a subclass of multi-state 2D CAs where
| specific states from the finite state set have a specific
| meaning associated.
|
| In general a CA is defined as a dynamical system governed
| by a local rule operating on the neighborhood
| configuration and yielding a new state. State set is
| typically finite. But the actual structure of the states
| can be anything you like. A valid state can be a tuple of
| a form (visible state, number of neighbors, sum of
| neighbors degrees, ...). As the maximum neighborhood size
| is finite and the visible cell states are finite - there
| is a finite number of such tuples which constitute the
| state set on which a CA can operate.
|
| Summing up - you are studying CAs in which your multi-
| state setup has some implied meaning. Still cool and
| interesting.
| airesearcher wrote:
| Here is a bit more information on how this class of rule works -
| should help with some of the questions about that in the thread:
| https://github.com/novaspivack/lace/blob/master/Realm_of_Lac...
| OutOfHere wrote:
| Can you make a deep CA such that layer 1 evolves the rules itself
| that apply to layer 2? Visualize the outputs of layer 1 and 2 in
| tandem then. Following this, apply this update logic to n layers.
| There are some papers on this that exist that can LLM can help
| find.
| my_throwaway23 wrote:
| Looks like it would be fun to play around with, but... The file
| "LACE/lace_app.py" is 37202 lines long. Why?
| airesearcher wrote:
| Because I was too lazy to refactor it into a ton of modules...
| my_throwaway23 wrote:
| Fair enough, especially considering it looks like a passion
| project. That said, I think you'd have a greater reach if
| you'd modularize, allowing a better overview of the project.
| I'd love to take a deep dive, but truth be told, that big of
| anything is a little daunting.
| airesearcher wrote:
| Actually it's a pretty hard thing to implement - the main
| challenge was to make it performant in python... I had to
| jump through flaming hoops!
| Perenti wrote:
| How is this different from a CA with dynamic neighbourhoods?
| Other than the visualisation of course. It appears at first read
| to be isomorphic to what's shown, unless I'm overlooking
| something (quite possible I am). CA with neighbourhoods dependent
| on cell states and/or agents were what made later versions of
| SimCity etc work.
|
| I was working on GACA with dynamic neighbourhoods in 1997.
___________________________________________________________________
(page generated 2025-10-16 23:00 UTC)