hub: repo_type: generator builtin: automata-reaction tags: - banzhaf-yamamoto chemistries: - id: automata-reaction name: Automata reaction (32-bit binary string chemistry) intuition: 'The cheapest constructive chemistry that still does something interesting. Molecules are 32-bit words, and a collision treats the first word as a finite automaton that consumes the second and emits a third: s1 + s2 -> s1 + s2 + A_s1(s2). Both reactants survive, so every string is both machine and tape. About a third of random strings turn out to be passive replicators, products tend to resemble their parents, and none of it is designed in - it falls out of 32 bits and one rule. ' aliases: - Dittrich-Banzhaf automata chemistry - constructive binary string system origin: Dittrich & Banzhaf, 1998 book: 10.6.1 refs: - '[233]' - doi:10.1162/106454698568521 family: automata kind: generator constructive: true S: repr: 32-bit words; species id w<8 hex digits>, structure the 32-character bitstring (most significant bit first) definition: implicit R: definition: implicit arity: 2 scheme: s1 + s2 -> s1 + s2 + s3 with s3 = A_s1(s2); elastic if the filter rejects s3 (paper eq. 3) notes: 's1 is folded into a program of eight 4-bit instructions (least significant nibble first; SETP takes the next nibble as a 4-bit pattern) run by a register machine: the operator register holds s1 (read only), the IO register starts as s2 and holds s3 at the end. Five control registers (direction, move mode, last ALU operation, copy mode, pattern). No loops or jumps: the program halts after the eighth nibble or at STOP, and a MOV with a pattern moves at most 32 steps. Operator and operand are ordered: s1 + s2 and s2 + s1 generally differ. ' A: reactor: - well-stirred-multiset dilution: each inserted product replaces a random molecule; M constant (paper's reactor algorithm) notes: M collisions make one generation; the paper runs M = 100 to 10^6 for up to 7000 generations params: - name: method type: enum default: soup choices: - soup - closure role: structural meaning: 'soup: the paper''s reactor algorithm, observed reactions with firing counts; closure: every reaction reachable from the distinct seed words (Chemart addition, e.g. to check that a published organization is closed)' - name: mechanism type: enum default: automata choices: - automata - and role: structural meaning: 'automata: the automata reaction (paper 3.2); and: the paper''s reference reaction s3 = s1 AND s2 (paper 3.1, fig. 2)' - name: code_table type: enum default: 1 choices: - 1 - 2 range: paper figs. 3-4 use table 1, figs. 5-10 (evolution) use table 2 role: structural meaning: 'instruction table (paper fig. 1, right): table 1 maps 1010 to NOT, table 2 maps it to EQ; the other 15 codes are identical' - name: forbid_exact_replication type: bool default: false range: 'paper section 5.4 (evolution): true' role: selection meaning: 'filter f1 of paper eq. 3: a collision whose product equals one of its reactants is elastic, so exact replication is disabled' - name: M type: int default: 1000 min: 2 max: 1000000 range: 'paper: 100 (fig. 3), 10^4 (figs. 2, 4), 10^5 (figs. 5-6), 10^6 (fig. 7)' role: population meaning: 'soup size: number of random 32-bit words in the initial soup (ignored when words is given)' - name: generations type: int default: 10 min: 0 max: 100000 range: 'paper: 10 (fig. 2), 140 (fig. 3), 280 (fig. 4), 1000 and 7000 (figs. 5-6)' role: population meaning: 'soup only: run length in generations of M collisions each, elastic collisions included' - name: words type: list default: [] range: e.g. the fig. 3 organization [7240a7ef, 7240a7ea, 7240a7eb, 7240a7ee] role: structural meaning: explicit initial multiset (soup) or seed set (closure) of 32-bit words as hex strings or integers; overrides the random draw of M words - name: max_species type: int default: 200 min: 1 role: structural meaning: 'closure only: species budget; the closure of random words is usually cut off by it (status truncated)' provides: - topology - stoichiometry - catalysts - rate-constants - flow - initial-state - sequence-structure-function fidelity: reconstructed sources: - 'Dittrich, P. & Banzhaf, W. (1998). Self-evolution in a constructive binary string system. Artificial Life 4(2):203-220. Preprint (draft April 20, 1998): reactor algorithm (sec. 2), eqs. 1-3, automata reaction (sec. 3.2, fig. 1, tables 1-2), figs. 2-10, appendix (registers and instructions). https://users.fmi.uni-jena.de/~dittrich/p/DB97alife.ps' - 'Dittrich, P. (1997). autoreac-1.0, ANSI C source code of the automata reaction (paper ref. [8], named there as the precise formal specification): autoReac.c runN, instructionTable01/02. https://users.fmi.uni-jena.de/~dittrich/software/autoreac-1.0.tar' decisions: - The book gives only the idea (10.6.1). The machine is a line-by-line port of autoReac.c, which the paper's appendix names as the formal specification; compiled with 32-bit words it and the port agree on 2015 random pairs for each code table, and both reproduce paper table 2, the fig. 3, 4 and 10 reaction tables and the fig. 9 block (tests). - 'Where the paper''s appendix and the C source disagree the source wins: TMM cycles both -> operator pointer only -> IO pointer only -> both (autoReac.c movMode++), whereas the appendix prints both -> IO pointer -> operator pointer.' - 'C details the paper does not spell out, kept as in autoReac.c: pointers are realised by rotating the registers, and the IO register is rotated back at the end (correctResult); pointers start at bit 0 (least significant) and ''left'' moves to higher bits; instructions are read from the least significant nibble; a SETP in the last nibble gets pattern 0000; a logic instruction sets the last-ALU register, runs, and then makes one pointer step, which with copy mode on applies that ALU operation once more before moving (so EXOR/NOT/EQ cancel on that bit); CPON keeps the last ALU operation (initially ID); a MOV with a pattern checks the operator register, or the IO register in IO-pointer-only mode, after each of at most 32 steps.' - 'autoReac.c also contains code tables 3 and 4, a binding-preference option and a no-correction switch; the paper uses none of them (only tables 1 and 2), so they are not exposed. The v1 params word_len and opcode_width are dropped: the machine is defined only for 32-bit words and 4-bit instructions.' - 'The v1 topology param (2d-grid) and the ''space'' capability are dropped: the spatial variant is Banzhaf, Dittrich & Eller (1999, Physica D 125:85-104), not [233], and lattice-2d is removed from A.reactor.' - 'Reactor: chemart.soup.soup with dilution constant runs generations x M collisions. The paper replaces a random one of the M molecules by s3; soup removes a random one of the M + 1 molecules after insertion, so s3 itself is removed with probability 1/(M + 1). soup also draws two distinct molecules, while the paper does not say whether s1 and s2 may be the same molecule. Both differences are O(1/M).' - 'Rates: paper eq. 1 (catalytic network equation) with eq. 2 (k = 1 if s1 + s2 => s3 exists and passes the filter, 0 otherwise). Each network reaction is a multiset {a, b} -> {a, b, s3}; its mass-action k counts the ordered pairs (a, b), (b, a) that produce s3 (1 or 2; 1 when a = b). outflow constant-total is the dilution term of eq. 1.' - 'Observed network: species are all initial words and all products; initial_state is the random soup; extras.final_state the final one (most frequent first); extras.analysis records the paper''s macroscopic measures per generation: diversity Div = distinct types / M (from generation 0), productivity (inserted products / M) and total innovativity (never-seen products / M). The paper''s DDC is not computed.' - mechanism and is the paper's reference reaction (3.1), included for fig. 2; code_table does not apply to it. method closure (chemart.expand.expand over ordered pairs) is a Chemart addition. - Paper 3.2 says about 30% of random strings are passive and about 0.004% active self-replicators, without saying how many operands were tried. With the (C-verified) machine, 38% of random strings copy one random operand, 20-25% copy each of three, and about 0.005% (54-58 per 10^6) return themselves for eight operands; the test only checks the passive fraction is of that order. - 'Paper erratum: the fig. 4 program listing prints the binary code of CPON as 0100 (that is TDIR); the string 1e1ca260 has nibble 0110 there, and the listed mnemonics are what the machine runs.' reference_impl: 'autoreac-1.0 (Dittrich 1997, ANSI C): https://users.fmi.uni-jena.de/~dittrich/software/autoreac-1.0.tar' phenomena: - 'many random strings are passive replicators (s1 + s2 => s2; paper 3.2: about 30%, measured here 20-38% depending on how many operands are checked) and very few are active self-replicators (s1 + s2 => s1; paper: about 0.004%, measured here about 0.005%)' - products resemble their parents; variation happens mostly at the right edge of the operand (paper table 2) - 'AND reaction: extinction, the soup is taken over by 00000000 (paper fig. 2, M = 10^4)' - 'M = 100: diversity and innovativity drop until a closed self-maintaining organization of a few strings dominates, then drift (fig. 3: 7240a7ef, 7240a7ea, 7240a7eb, 7240a7ee)' - 'M = 10^4: an explorative phase of high diversity and innovativity ends (about generation 40) when active replicators appear and take over (fig. 4)' - 'M = 10^5-10^6 with code table 2 and exact replication forbidden: self-evolution without mutation operator or fitness function, punctuated quasi-stable organizations of closely coupled similar strings (figs. 5-9)' - 'spontaneous emergence of cross-over: 1e64a24e + 00000000 => 0000024e (fig. 10)' - syntactic and semantic closure of emergent organizations (confirming Fontana); lazy -> eager replicator transitions (book 10.6.1) notes: 'The best cost/benefit constructive chemistry in the book: 32-bit words, no loops, a bounded number of steps per reaction, large populations, and it reproduces the qualitative results of AlChemy at a fraction of the compute. The observed network of a short soup run is a sample of a 2^32-species chemistry; paper-scale runs (M = 10^6) need a vectorised or compiled machine. '