chemart / mcs-bl

hub:
  repo_type: generator
  builtin: mcs-bl
  tags:
  - banzhaf-yamamoto
chemistries:
- id: mcs-bl
  name: Molecular Classifier System (MCS.bl)
  intuition: 'Every molecule can be the enzyme or the substrate. Strings over a small alphabet of data
    and control symbols act on each other by pattern matching: one string''s units match a region of another
    and rewrite it, with both reactants surviving. Among all 4096 strings of length four exactly one is
    a self-replicase that copies any string - and, tellingly, it enjoys no selective advantage over non-enzymatic
    strings, which is the model''s point about how hard it is to get selection started.

    '
  aliases:
  - MCS.b
  - Molecular Classifier System - broadcast language
  origin: Decraene, Mitchell & McMullin, 2006-2011; based on Holland's Broadcast Language (1975) and classifier
    systems
  book: 11.1.1
  refs:
  - '[221]'
  - '[222]'
  - '[224]'
  - '[225]'
  - '[452]'
  - '[570]'
  - '[395]'
  - '[396]'
  - doi:10.1142/S0219525911002913
  family: bio-inspired
  kind: generator
  constructive: true
  S:
    repr: 'Broadcast devices: strings over {0, 1, *, :, #, $, %, ''} (thesis glyphs diamond, reversed
      triangle, triangle, prime for # $ % ''). Species id m_<one letter per symbol: 0 1, * S, : C, # H,
      $ D, % P, '' Q>, structure the raw string. A device holds zero or more broadcast units ''*condition:action''
      (null device: none).

      '
    definition: implicit
  R:
    definition: implicit
    arity: 2
    scheme: enzyme + substrate -> enzyme + substrate + product (both reactants catalytic); elastic if
      no unit of the enzyme matches the substrate
    notes: 'Units: from each unquoted * to the next; the first unquoted : separates condition from action,
      a second : and what follows are ignored; both parts non-empty. The condition must match the whole
      substrate: 0, 1 and quoted symbols are literals; # one symbol (any non-empty suffix when last);
      $ a non-empty prefix (first) or suffix (last), ignored elsewhere; % one symbol, only the leftmost
      counts. The action writes 0, 1 and quoted symbols (one quote removed), replaces $ and % by what
      they matched (transposition) and ignores unquoted #, and $ or % absent from the condition. Order
      matters (enzyme vs substrate). If several units match, one is picked at random. Realisable operations
      (book table 11.1): no reaction, activation, inhibition, universal replication, self-replication,
      concatenation, cleavage.

      '
  A:
    reactor:
    - well-stirred-multiset
    - compartments
    dilution: 'single reactor: grows to n_max, then each product displaces a random molecule other than
      the reactants (catalytic network equation with dilution flow, thesis eq. 5.1); cell model: cells
      divide at a criterion and a random other cell is removed'
    notes: 'Multilevel selection (book fig. 11.2; ACS 2011 2.3): cells run independent reactors; a cell
      that meets the division criterion (full, or n_target copies of a target species) gives half its
      molecules, drawn at random, to an offspring and a random other cell is removed, keeping the number
      of cells fixed. Book fig. 11.3: 31 cells, capacity 10^6, division at 200 copies of s1, p_s = 1e-5,
      cells racing in wall-clock time on separate CPUs.

      '
  params:
  - name: method
    type: enum
    default: closure
    choices:
    - closure
    - soup
    role: structural
    meaning: 'closure: every reaction among the strings reachable from the seeds (status complete or truncated);
      soup: the thesis'' single-reactor model (4.2.1) for `steps` collisions with mutation, returning
      the reactions that fired with counts (status observed)'
  - name: strings
    type: list
    default:
    - '*$0:$1'
    - '*$0:$0'
    - '*$1:$0'
    - '*$1:$1'
    range: 'book table 11.2 cell types: c1 [*$0:$1, *$0:$0, *$#:$0, *$#:$1], c2 [*$0:$1, *$0:$0, *$#:$%0,
      *$#:$%1], c3 [*$0:$1, *$0:$0, *$%:$0, *$%:$1]; universal replicase [*$:$]; thesis table 5.2 replicases
      *$1:$1 .. *$0101:$0101'
    role: structural
    meaning: 'seed broadcast devices over {0,1,*,:,#,$,%,''} (thesis glyphs are accepted and translated).
      Default: cell type c0 of book table 11.2 (thesis table 7.1)'
  - name: self_replication
    type: bool
    default: false
    range: true in thesis ch. 5-6 and book table 11.1; false in the table 11.2 experiment (thesis 7.2,
      ACS 2011, CEC 2009)
    role: selection
    meaning: allow reactions whose product is identical to both enzyme and substrate (s + s -> 2s + s);
      false makes them elastic
  - name: max_length
    type: int
    default: 500
    min: 4
    max: 1000000
    range: 'thesis: BDL_max = 500 (ch. 6-7), 10^6 (5.5)'
    role: structural
    meaning: 'BDL_max: a reaction whose product is longer is not permitted (elastic); bounds the elongation
      catastrophe'
  - name: max_species
    type: int
    default: 200
    min: 1
    max: 100000
    role: structural
    meaning: 'closure only: species budget; elongating chemistries are cut off by it (status truncated)'
  - name: initial_copies
    type: int
    default: 10
    min: 1
    max: 1000000
    range: 'thesis 7.2: 10 of each seed species; 5.3: 100 copies of the replicase'
    role: population
    meaning: copies of each seed string (initial_state; initial soup)
  - name: n_random
    type: int
    default: 0
    min: 0
    max: 1000000
    range: 'thesis 5.2: 100 random molecules; 5.3: 900'
    role: population
    meaning: extra seed strings drawn uniformly from the alphabet (each with initial_copies copies)
  - name: random_length
    type: int
    default: 10
    min: 1
    max: 1000000
    range: 'thesis 5.2-5.3: 10'
    role: population
    meaning: length of the random seed strings
  - name: n_max
    type: int
    default: 1000
    min: 3
    max: 100000000
    range: 'thesis 5.2-5.3: 1000; cells in 7.2: 10^6'
    role: population
    meaning: 'soup only: reactor capacity; below it products are added, at it each product displaces a
      random molecule other than the reactants'
  - name: steps
    type: int
    default: 10000
    min: 0
    max: 1000000000
    range: 'thesis 5.2: 5x10^6 collisions per run; 7.2: over 4x10^7 per cell per hour'
    role: population
    meaning: 'soup only: number of collisions (elastic ones included)'
  - name: p_s
    type: float
    default: 1.0e-05
    min: 0.0
    max: 1.0
    range: 'book fig. 11.3 / ACS 2011: 1e-5; thesis 5.2: 1e-3; D.1: 5e-5'
    role: stochastic
    meaning: 'soup only: per-symbol mutation probability of each product; a mutation is a flip to another
      symbol, an insertion of a random symbol after it, or a deletion, with equal probability'
  provides:
  - topology
  - stoichiometry
  - catalysts
  - rate-constants
  - flow
  - initial-state
  - sequence-structure-function
  fidelity: reconstructed
  sources:
  - 'Decraene, J. (2009). Autocatalytic Closure and the Evolution of Cellular Information Processing Networks.
    PhD thesis, Dublin City University: MCS reactor and mutation (4.2), broadcast language syntax and
    semantics with examples r1-r20 and table 4.2 (4.3), self-replicases (tables 5.1-5.2, eqs. 5.1-5.6),
    elongation catastrophe (5.5), cell model (6.4.2), table 7.1-7.2 experiment (7.2), appendices B and
    D.2. https://doras.dcu.ie/14810/1/jd-thesis-09-08-09.pdf'
  - 'Decraene, J. & McMullin, B. (2011). The evolution of complexity in self-maintaining cellular information
    processing networks. Advances in Complex Systems 14(1):55-75 (book ref [221]); preprint: alphabet
    and table 2 (operations), mutation (2.2), multilevel model (2.3, fig. 2), table 3 (= book table 11.2),
    table 4. http://doras.dcu.ie/16292/1/decraene-ACS-09.pdf'
  - 'Decraene, J., Mitchell, G. G. & McMullin, B. (2009). Crosstalk and the cooperation of collectively
    autocatalytic reaction networks. IEEE CEC 2009, 2249-2256 (book ref [225]): table I, random choice
    among satisfied units, reactor algorithm (fig. 5). http://doras.dcu.ie/4609/1/decraene-cec-09.pdf'
  - 'Decraene, J., Mitchell, G. G. & McMullin, B. (2008). Unexpected evolutionary dynamics in a string
    based artificial chemistry. ALife XI, 158-165 (book ref [224]): reactor, BDL_max rule, elongation
    catastrophe. http://doras.dcu.ie/4589/1/decraene-alife-final-08.pdf'
  - 'Decraene, J. (2006). The Holland Broadcast Language. Technical report ALL-06-01, DCU: specification
    and C++ source (BUnit.cpp: setRegexForm, setCompactForm, getSymbolValueFromSignal, reactWith). http://doras.dcu.ie/4590/1/decraene-ALL-06-01.pdf'
  decisions:
  - 'Symbols: the book''s extracted text prints the alphabet as {3, $, %, } and table 11.2 uses 3; comparing
    with thesis table 7.2 (glyphs), book 3/# is the diamond (single wildcard, any suffix when last), $
    the reversed triangle (prefix/suffix wildcard that transposes), % the triangle (single wildcard that
    transposes) and the lost fourth symbol the quote. The book''s table 11.1 also lost the quotes of the
    activation (*$1:''*$) and inhibition (*''*0$:0$) enzymes.'
  - 'Matching semantics come from the thesis prose and examples plus the C++ source of the authors'' earlier
    BL implementation (ALL-06-01); the MCS.bl C++ package (esignet.net/dokumente/upload/WP13...) is not
    archived. From the source: $ matches one or more symbols (regex .+), so it never matches an empty
    string; a symbol is quoted iff the preceding symbol is a quote; unquoted quotes are dropped; the $
    value is positional (the other condition symbols take one character each); $ in the middle of a condition
    is ignored, and with $ at both ends the last is ignored; only the first % counts. The source''s length
    arithmetic counts quote characters in the condition (a bug for quoted symbols after a leading $);
    here the matched string is computed from the pattern symbols.'
  - '# as the last condition symbol matches any non-empty suffix (thesis r13-r15); after a leading $ it
    can only take one symbol, since $ absorbs the rest (this is the thesis'' statement that # and % act
    the same in *$#:$0 and *$%:$0, and gives c1-c3 nine reactions each).'
  - 'Book table 11.1 / thesis table 4.2 / CEC table I / ACS table 2 activation row is inconsistent: *$1:''*$
    on 0:1 gives *0: (not an active device) by the same rule the cleavage and concatenation rows use (*$1:$
    on *0:1 gives *0:, so $ excludes the matched 1). The intended activation is reproduced by *$:''*$
    on 0:1 -> *0:1 (tested).'
  - 'Several units: CEC 2009 (II-A) picks one satisfied unit at random. The closure lists every possible
    product; a reaction''s rate weight is the fraction of the enzyme''s satisfied units that give it.'
  - 'Elastic collisions: no unit matches; the product is empty; the product is longer than max_length
    (ALife 2008: such reactions ''were simply not permitted''; truncation was a later, abandoned variant);
    or, with self_replication false, the product equals both reactants.'
  - 'Rates: thesis eq. 5.1-5.2 (catalytic network equation, alpha = 1 per ordered enzyme-substrate pair
    that yields the product) with dilution flow = outflow constant-total. Each multiset reaction {a, b}
    -> {a, b, p} gets mass-action k = sum over the orders (a, b), (b, a) of the fraction of satisfied
    units giving p (1 or 2 for single-unit enzymes; one order when a = b). Soup reactions made by a mutation
    have no structural k and get rate None.'
  - 'Soup: two distinct molecules drawn at random, the first the enzyme (thesis 4.2.1, 5.3); below n_max
    the product is added, at n_max it replaces a random molecule other than the two reactants (thesis;
    ALife 2008 does not exclude them). Mutation (thesis 4.2.2) is applied to the product once per symbol
    with probability p_s, sampled as a binomial number of distinct positions; self-replication is filtered
    before mutation and length after. The thesis'' spontaneous mutation (a fraction r_mut of the population
    every x timesteps, x not given) is not modelled; the table 11.2 experiment used r_mut = 0.'
  - 'Multilevel cell selection is not part of one network and is not modelled: v1 params n_cells, cell_capacity
    and division_target are dropped (they size a population of reactors, not the chemistry); the model
    is described in A.notes. Division variants: thesis 6.4.2 divides when a cell is full and overwrites
    a random target cell; thesis 7.2 / ACS 2011 divide at n_target copies of s_T and remove a random other
    cell.'
  - 'Book prose erratum (11.1.1): ''c1 consists of s1, s2, s3, s4, whereas c2 consists of s1, s2, s5,
    s6'' is shifted by one; table 11.2 (and thesis table 7.2) give c0 = {s1..s4}, c1 = {s1, s2, s5, s6}.
    The book''s ''one molecule (rather than the full number) was selected as cell division threshold''
    means one target species. The reaction counts 6 (c0) and 9 (c1) are from thesis 7.2.3 and ACS 2011
    (three additional reactions).'
  - 'Thesis errata found while testing: appendix D.2 lists s4 + s2 -> s4 for s4 = *$0:$0, s2 = *$1:$0;
    the rule gives s2 (replication of the substrate), and the other 15 entries of that table agree; D.2
    prints the species without the leading * (s1 = $0:$1) and s3 as $1:$ for *$1:$1. Section 5.5 prints
    s_R4 = *$0101:*$0101 with an unquoted * in the action, which would leave no unit; table 5.2 and the
    fig. 5.4 caption give *$0101:$0101, whose reactions reproduce 5.5 exactly (tested). Section 5.2 (and
    ALife 2008) count ''4^8 (65,536)'' molecules of length 4; with 8 symbols there are 8^4 = 4,096, of
    which only *$:$ self-replicates (tested).'
  - 'Open doubt: of the 15 spontaneous self-replicases of thesis table 5.1 (ALife 2008 table 2), 9 self-replicate
    under the published semantics (tested), but 6 have $$ in the action (e.g. *$*$:$%$%%), which by thesis
    example r17 doubles the substrate instead; the thesis nevertheless calls all 14 non-*$0:$0 entries
    equivalent to *$:$. The MCS.bl source that would settle this is not available.'
  reference_impl: BL C++ source in technical report ALL-06-01 (Decraene 2006); the MCS.bl C++ package
    cited at http://esignet.net/dokumente/upload/WP13 is not archived
  phenomena:
  - 'universal replicase *$:$ copies any string; it has no selective advantage over non-enzymatic strings
    (thesis eqs. 5.3-5.6: zero expected growth under dilution)'
  - of the 8^4 = 4,096 strings of length 4 only *$:$ is a self-replicase (thesis 5.2, which misprints
    the count as 4^8 = 65,536)
  - 'elongation catastrophe: the mutant *$0101:$00101 of *$0101:$0101 makes ever longer strings *$0101:$0...0101
    (thesis 5.5, ALife 2008)'
  - succession of dominant cell types c0 -> c1 -> c2 -> c3 under selection for s1 (book table 11.2); c1-c3
    are phenotypically equivalent and have 9 reactions against 6 in c0, all closed
  - selection pressure can be aimed at a chosen molecular species by changing the division criterion
  - hand-designed collectively autocatalytic sets *$0:$1 + *$1:$0 close into c0 (thesis appendix D.2)
  notes: 'A reflexive string-rewriting chemistry: every molecule can be both enzyme and substrate. Chemart
    provides the molecular level (closure or single reactor); the cell level of the book''s figures (31
    concurrent cells racing in wall-clock time) is not a reaction network.

    '