chemart / sr-loops

hub:
  repo_type: generator
  builtin: sr-loops
  tags:
  - banzhaf-yamamoto
chemistries:
- id: sr-loops
  name: Self-replicating loops in cellular automata
  intuition: 'Self-replication in a cellular automaton, and the clearest case of ''what is a molecule''
    being the observer''s choice. At the micro level a cell state is a molecule and a transition is a
    reaction; at the macro level a *loop* - an emergent closed pattern that copies itself - is the molecule,
    and reproduction, mutation and dissolution are the reactions. Langton''s loop replicates without universal
    construction; add structural dissolution and the colony reaches a steady state, and loops can then
    evolve toward smaller sizes.

    '
  aliases:
  - Langton loop
  - Byl loop
  - Chou-Reggia loop
  - SDSR loop
  - evoloop
  origin: von Neumann 1966; Langton 1984; Byl 1989; Reggia 1993; Sayama 1998-2004
  book: 10.4, 10.7.2; ecology 8.2.3
  refs:
  - '[495]'
  - '[705]'
  - '[744]'
  - '[745]'
  - '[738]'
  - '[739]'
  - '[779]'
  - '[453]'
  family: automata
  kind: generator
  constructive: true
  S:
    repr: 'Two readings (book 10.7.2), chosen with `mode`. (a) macro: an emergent loop pattern is a molecule.
      A loop is a connected group of at least min_loop_cells non-quiescent cells; two loops are the same
      species when they ever show the same configuration up to rotation. Species id = cell count at first
      registration plus a base-26 label (L086aaa); structure = that configuration, rows of state digits
      separated by "/". (b) micro: a cell state is a molecule and the quiescent state 0 is the absence
      of one (species s1..s8); state transitions are movement and reaction.

      '
    definition: implicit
  R:
    definition: implicit
    arity:
    - 1
    - 5
    scheme: 'macro: L -> 2 L (replication), L -> L + L'' (replication with variation, evoloop), L -> ∅
      (structural dissolution or death); micro: C + N + E + S + W -> C'' + N + E + S + W (one CA transition,
      the neighbours as catalysts, quiescent cells omitted)'
    notes: 'Reactions are the events observed in one run of the cellular automaton, each with its firing
      count. A replication is recorded when a new connected loop appears; its mother is the loop it separated
      from (or the nearest loop). A death is recorded when a loop disappears, which in the SDSR loop and
      the evoloop is Sayama''s structural dissolution.

      '
  A:
    reactor: lattice-2d
    dilution: 'bounded space: the lattice is finite (periodic or with a quiescent border), so loops compete
      for room; in the SDSR loop and the evoloop blocked loops dissolve, and the population settles at
      a steady state instead of freezing.

      '
    notes: 'Synchronous update of the whole lattice, von Neumann neighbourhood, rotationally symmetric
      (rotate4) transition tables, one ancestor loop at the centre by default.

      '
  params:
  - name: rule
    type: enum
    default: langton
    choices:
    - langton
    - byl
    - reggia-1
    - reggia-2
    - sdsr
    - evoloop
    role: structural
    meaning: 'published transition table: langton = Langton 1984 (8 states, 219 transitions, 86-cell loop);
      byl = Byl 1989 (6 states, 12-cell loop); reggia-1 and reggia-2 = the Chou-Reggia loops of Reggia
      et al. 1993 (8 states, 6 and 5 cells); sdsr = Sayama''s structurally dissolvable loop (9 states);
      evoloop = Sayama''s evolvable loop (9 states)'
  - name: mode
    type: enum
    default: macro
    choices:
    - macro
    - micro
    role: structural
    meaning: 'which reading of ''molecule'' to export: macro = emergent loops and their replication/dissolution
      events; micro = cell states, with every CA transition that fired as a reaction'
  - name: grid
    type: int
    default: 60
    min: 8
    max: 4000
    range: Sayama's evolution runs use 200x200 to 1000x1000; 60 holds two Langton loops
    role: spatial
    meaning: side of the square lattice
  - name: steps
    type: int
    default: 320
    min: 1
    max: 2000000
    range: one replication takes 151 steps (Langton, SDSR), 25 (Byl), 15 (Chou-Reggia), 363 (evoloop);
      the SDSR steady state needs a few thousand and evolution in the evoloop 10^4-10^7
    role: population
    meaning: synchronous updates of the lattice
  - name: boundary
    type: enum
    default: periodic
    choices:
    - periodic
    - quiescent
    role: spatial
    meaning: 'periodic: the lattice is a torus (Sayama''s ''periodic space''); quiescent: everything outside
      the lattice is background'
  - name: ancestors
    type: int
    default: 1
    min: 1
    max: 1000
    range: Sayama's competition runs start two ancestors at opposite ends of the space
    role: population
    meaning: how many copies of the ancestor to place; one is centred, several are placed at random non-overlapping
      positions (this is the only use of the seed)
  - name: ancestor_pattern
    type: str
    default: ''
    role: structural
    meaning: the seed loop as a Golly RLE string ('x = 4, y = 4, rule = ...' then the run-length-encoded
      rows, '.' = quiescent, A = state 1); empty means the published ancestor of the chosen rule
  - name: min_loop_cells
    type: int
    default: 12
    min: 1
    max: 100000
    range: 12 = Byl's loop; use 4 for the Chou-Reggia loops, 20 or more to ignore the debris of dissolving
      loops
    role: structural
    meaning: 'macro mode: the smallest connected group of non-quiescent cells that counts as a loop; smaller
      groups are debris and are ignored'
  - name: track_every
    type: int
    default: 1
    min: 1
    max: 100000
    role: population
    meaning: 'macro mode: observe the loops every this many steps (higher is faster but misses loops that
      live shorter than one interval)'
  provides:
  - topology
  - stoichiometry
  - catalysts
  - initial-state
  - space
  - sequence-structure-function
  fidelity: reconstructed
  sources:
  - Langton, C. G. (1984). Self-reproduction in cellular automata. Physica D 10(1-2):135-144. doi:10.1016/0167-2789(84)90256-2
    (book ref [495]). 8 states, von Neumann neighbourhood, 219 rotationally symmetric transitions, an
    86-cell loop that replicates in 151 steps.
  - Byl, J. (1989). Self-reproduction in small cellular automata. Physica D 34(1-2):295-299. doi:10.1016/0167-2789(89)90242-X
    (book ref not listed; the loop is cited in the book via [779]). 6 states, a 12-cell loop replicating
    in 25 steps.
  - Reggia, J. A., Armentrout, S. L., Chou, H.-H. & Peng, Y. (1993). Simple systems that exhibit self-directed
    replication. Science 259(5099):1282-1287. doi:10.1126/science.259.5099.1282 (book ref [705], the book's
    '8 states, 5 cells'). Two unsheathed loops of 6 and 5 cells replicating in 13 and 15 steps.
  - Sayama, H. (1998). Introduction of structural dissolution into Langton's self-reproducing loop. Artificial
    Life VI, 114-122, MIT Press. http://cseweb.ucsd.edu/~rik/alife6/papers/IN79.html ; Sayama, H. (1999).
    A new structurally dissolvable self-reproducing loop evolving in a simple cellular automata space.
    Artificial Life 5(4):343-365. doi:10.1162/106454699568818 (book ref [744]). The dissolving state 8
    and the evoloop.
  - Sayama, H. (1999). Toward the realization of an evolving ecosystem on cellular automata. AROB 4th
    '99, 254-257 (book ref [745]), and the author's pages https://bingweb.binghamton.edu/~sayama/SDSR/
    (SDSR and evoloop software, LoopS/EvoLoopS, Java simulator).
  - 'Salzberg, C., Antony, A. & Sayama, H. (2004). Complex genetic evolution of self-replicating loops.
    Artificial Life IX, 262-267, MIT Press (book ref [738]). https://bingweb.binghamton.edu/~sayama/papers/alife9-evoloop.pdf
    : gene sequences (G = 071 straight growth, T = 041 left turn, C = 0 filler), species = genotype +
    loop size, size-8 ancestor GGCCGGCGCGTTGCGC, 2n-2 C n-2 self-replicating species of size n (15 of
    size 4), birth detected by the umbilical cord dissolver (state 6) and death by the loss of the inner
    sheath (state 2), 1000x1000 periodic space, parabolic population growth.'
  - 'Transition tables: the @TABLE sections of Golly''s rule files Langtons-Loops.rule, Byl-Loop.rule,
    Chou-Reggia-1.rule, Chou-Reggia-2.rule, SDSR-Loop.rule and Evoloop.rule (https://github.com/AlephAlpha/golly/tree/master/Rules),
    which carry the tables of Sayama''s own loops.java (NECSI, ''Self-Replicating Loops & Ant'', E. Bachmutsky
    1999), together with the ancestors of Golly''s Patterns/Loops/*.rle. Wikipedia''s ''Langton''s loops''
    table (states, cells, replication period per variant) was used as a cross-check.'
  decisions:
  - 'kind stays generator: the implementation runs the cellular automaton and returns the observed event
    network of the loops (macro) or of the cell states (micro).'
  - 'Transition tables are not in the book and the original papers print them as figures; they are taken
    verbatim from Golly''s rule files, whose provenance is Sayama''s loops.java. Each table is verified
    by reproducing the published replication period of its ancestor (tests): Langton 151, Byl 25, Chou-Reggia
    15 (5-cell loop), evoloop 363, SDSR = Langton''s 151.'
  - 'Golly rule-table semantics: variables are bound per transition, every transition stands for its four
    rotations (rotate4), the first matching transition wins, and a neighbourhood no transition covers
    leaves the cell unchanged. The expansion used here reproduces the compiled @TREE section of all six
    rule files exactly (59049 entries each for the 9-state rules), so the automaton is the one Golly runs.'
  - Byl's table as distributed contains a line '212052' commented out with the note that it was inserted
    by mistake; it is not applied here, exactly as in Golly.
  - 'Langton''s period: from Golly''s ancestor pattern a complete rotated copy of it stands elsewhere
    on the lattice at step 147 and a second one at 151; after that each loop shows that configuration
    again every 147 steps (147, 294, 441, ... and 151, 298, 445, ...). The published period 151 is the
    step at which the newly born loop is an exact copy of the ancestor, which is what extras.analysis.ancestor_copy_steps
    and the replication records report; the four-step difference is the phase of the ancestor pattern
    as distributed, and the mother''s own recurrence (147) is reported separately as ancestor_recurrence.
    The same holds for the SDSR loop. For Byl (25, and every 25 steps after), the Chou-Reggia loops (13
    for the 6-cell loop, 15 for the 5-cell one) and the evoloop (363) the published period is the step
    at which the first complete copy appears.'
  - 'Species (macro): Salzberg, Antony & Sayama identify a species by the loop''s gene sequence (read
    counter-clockwise from the bonding location) plus its size, which only makes sense for the Langton
    family. Chemart instead identifies species observationally and for every rule: a species is registered
    by the configuration a loop has when it is born (plus the ancestor''s initial configuration), and
    any loop that shows a registered configuration, up to rotation, is that species. This reproduces the
    intended distinctions - a daughter that is an exact copy is the same species (L -> 2 L), a mutated
    evoloop offspring is a new one (L -> L + L'') - without assuming a sheath structure.'
  - Only birth configurations are registered. Registering every configuration a loop passes through was
    tried first and merges everything into one species in long evoloop runs, because dissolving loops
    pass through the configurations of smaller ones.
  - 'A loop born mid-construction is provisionally its own species and is merged with its mother''s (union-find,
    the older species wins) as soon as it shows a configuration registered for that species. extras.analysis.replications
    records both steps: for Langton the daughter separates at step 128 and is an exact copy of the ancestor
    at step 151. Reactions are aggregated after those merges, so a species that turns out to be its mother''s
    appears in a single L -> 2 L reaction.'
  - 'Loop detection: a loop is a connected group (8-connectivity) of at least min_loop_cells non-quiescent
    cells, followed from step to step by cell overlap. Sayama''s own detectors use rule-specific markers
    (the umbilical cord dissolver state 6 for birth, the inner sheath state 2 for death), which would
    not work for the Byl and Chou-Reggia loops; the connected-group criterion is used for all rules instead,
    with min_loop_cells to ignore the debris that dissolving loops leave behind.'
  - The mother of a new loop is the loop whose blob it separated from, or, when it appears detached, the
    nearest living loop. Loops that appear without any living loop in the lattice are recorded as ∅ ->
    L.
  - 'The chemistry is deterministic: the CA, the ancestor and its position are fixed. The seed is used
    only to place several ancestors (ancestors > 1) at random non-overlapping positions.'
  - 'Boundary: periodic (Sayama''s ''periodic space'') by default; ''quiescent'' treats everything outside
    the lattice as background. The unbounded plane of the original papers is not offered - bounded space
    is what makes the loops compete (book 10.7.2).'
  - 'Dropped v1 parameters: n_states, neighbourhood, grid and seed_loop (types matrix) and dissolution.
    The number of states and the neighbourhood are properties of the chosen rule, not free knobs; grid
    becomes the lattice side; seed_loop becomes ancestor_pattern (a Golly RLE string); dissolution is
    what distinguishes rule=sdsr and rule=evoloop from rule=langton.'
  - 'Not implemented: the Tempesti (1995), Perrier (1996) and Sexyloop (2007) variants, and von Neumann''s
    29-state automaton [453]; the evoloop gene sequence (G/T/C) reading of Salzberg et al.; the loops''
    interaction with ''hostile'' environments [739].'
  reference_impl: Sayama's LoopS / EvoLoopS and Java evoloop simulator, https://bingweb.binghamton.edu/~sayama/SDSR/
    ; Golly (https://golly.sourceforge.net), Rules/*.rule and Patterns/Loops/*.rle.
  phenomena:
  - 'self-replication without universal construction: Langton''s 86-cell loop makes an identical copy
    of itself every 151 steps, Byl''s 12-cell loop every 25, the Chou-Reggia 5-cell loop every 15, the
    evoloop every 363'
  - in bounded space the colony grows until the space is full; Langton's loops then freeze, while SDSR
    loops dissolve when they can no longer replicate and the population reaches a steady state with continuous
    turn-over
  - 'evoloop: variation on collision, and natural selection for smaller loops - a size-8 ancestor is replaced
    by the smallest self-replicating loops (interior 2x2, size 4)'
  - species clustering into islands, and changing 'concentrations' of loop species over time (book figure
    10.13)
  - robustness of dissolvable loops to hardware errors
  notes: 'The clearest case in the book where ''what is a molecule'' depends on the observer, so both
    readings are generated: `mode=macro` returns loops and their replication/dissolution events, `mode=micro`
    returns the cell states and the transitions that fired. The default run (Langton''s loop on a 60x60
    torus for 320 steps) is three replications of the published loop, the first of them an exact copy
    at step 151; the SDSR steady state and the evolution of the evoloop need thousands of steps and a
    larger lattice (see the tests).

    '