chemart / automata-reaction

View on GitHub

Automata reaction (32-bit binary string chemistry) — 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…

chemistry official · built in automata fidelity: reconstructed constructive #banzhaf-yamamoto

How it works

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.

S: 32-bit words; species id w<8 hex digits>, structure the 32-character bitstring (most significant bit first) · implicit
R: s1 + s2 -> s1 + s2 + s3 with s3 = A_s1(s2); elastic if the filter rejects s3 (paper eq. 3) · arity 2
A: well-stirred-multiset · each inserted product replaces a random molecule; M constant (paper's reactor algorithm)

Parameters

name	default	meaning
method enum · structural	"soup"	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) soup \| closure
mechanism enum · structural	"automata"	automata: the automata reaction (paper 3.2); and: the paper's reference reaction s3 = s1 AND s2 (paper 3.1, fig. 2) automata \| and
code_table enum · structural	1	instruction table (paper fig. 1, right): table 1 maps 1010 to NOT, table 2 maps it to EQ; the other 15 codes are identical 1 \| 2; paper figs. 3-4 use table 1, figs. 5-10 (evolution) use table 2
forbid_exact_replication bool · selection	false	filter f1 of paper eq. 3: a collision whose product equals one of its reactants is elastic, so exact replication is disabled paper section 5.4 (evolution): true
M int · population	1000	soup size: number of random 32-bit words in the initial soup (ignored when words is given) [2, 1e+06]; paper: 100 (fig. 3), 10^4 (figs. 2, 4), 10^5 (figs. 5-6), 10^6 (fig. 7)
generations int · population	10	soup only: run length in generations of M collisions each, elastic collisions included [0, 100000]; paper: 10 (fig. 2), 140 (fig. 3), 280 (fig. 4), 1000 and 7000 (figs. 5-6)
words list · structural	[]	explicit initial multiset (soup) or seed set (closure) of 32-bit words as hex strings or integers; overrides the random draw of M words e.g. the fig. 3 organization [7240a7ef, 7240a7ea, 7240a7eb, 7240a7ee]
max_species int · structural	200	closure only: species budget; the closure of random words is usually cut off by it (status truncated) [1, ∞]

Automata reaction (32-bit binary string chemistry)

One of the artificial chemistries of Banzhaf & Yamamoto, Artificial Chemistries (MIT Press, 2015), §10.6.1; first proposed by Dittrich & Banzhaf, 1998.

Its generator ships with the chemart library, so loading it runs no code from the hub and needs no trust_remote_code.

import chemart

net = chemart.generate_network("chemart/automata-reaction", seed=0)   # same as "automata-reaction"
print(net.summary())

What to look for

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)

Implementation 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.

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

Banzhaf & Yamamoto, Artificial Chemistries (2015), §10.6.1

Preview at default parameters

4818 species · 9872 reactions · status observed · seed 1

wb7362806 + w13410911 -> wb7362806 + w13410911 + w13410910  [mass-action k=1.0]  (x1)
w54694c3a + w8b89e43c -> w54694c3a + w8b89e43c + w8b89e43f  [mass-action k=1.0]  (x1)
w262802e1 + w8b169674 -> w262802e1 + 2 w8b169674  [mass-action k=1.0]  (x1)
w3700032a + w89d94737 -> w3700032a + w89d94737 + w89d9473b  [mass-action k=1.0]  (x1)
wedb4ccb2 + w3407a349 -> wedb4ccb2 + w3407a349 + w3407a34b  [mass-action k=1.0]  (x1)
w27d6c977 + w0e4da006 -> w27d6c977 + w0e4da006 + w0e4da005  [mass-action k=1.0]  (x1)
we9eff343 + w4295bf0f -> we9eff343 + w4295bf0f + w7295bf0f  [mass-action k=1.0]  (x1)
wc9f97bcf + wf8c7532f -> wc9f97bcf + wf8c7532f + wf8c75369  [mass-action k=1.0]  (x1)
w5083baa0 + w7f9b0c15 -> w5083baa0 + w7f9b0c15 + w7f9b0c16  [mass-action k=1.0]  (x1)
w95642a61 + w727d8aec -> w95642a61 + w727d8aec + w727d8aee  [mass-action k=1.0]  (x1)
wbaed2d8e + wc0c817b6 -> wbaed2d8e + 2 wc0c817b6  [mass-action k=1.0]  (x1)
w21b01d68 + w2192dee4 -> w21b01d68 + 2 w2192dee4  [mass-action k=1.0]  (x1)
wedb4ccb2 + w9aea3b44 -> wedb4ccb2 + w9aea3b44 + w9aea3b46  [mass-action k=1.0]  (x1)
w274d592c + wf8352013 -> w274d592c + 2 wf8352013  [mass-action k=1.0]  (x1)
w804ff7c1 + w8fff5958 -> w804ff7c1 + w8fff5958 + w8fff5940  [mass-action k=1.0]  (x1)
wfa17bfdb + w7295bf0f -> wfa17bfdb + w7295bf0f + w7295bf0e  [mass-action k=1.0]  (x1)
w4f7fb38b + w80969775 -> w4f7fb38b + w80969775 + w80969774  [mass-action k=1.0]  (x1)
w59b29703 + w48292531 -> w59b29703 + 2 w48292531  [mass-action k=1.0]  (x1)
w938c33cc + w8a1379f7 -> w938c33cc + w8a1379f7 + w8a1379f3  [mass-action k=1.0]  (x1)
w9a1119fa + wace37e3c -> w9a1119fa + wace37e3c + wace37ebd  [mass-action k=1.0]  (x1)
w46e25789 + w8582ab9f -> w46e25789 + 2 w8582ab9f  [mass-action k=1.0]  (x1)
wce41e6a5 + w73e2d50a -> wce41e6a5 + w73e2d50a + w73e2d504  [mass-action k=1.0]  (x1)
wc6d4b45f + wff8cd21c -> wc6d4b45f + wff8cd21c + wff8cd21e  [mass-action k=1.0]  (x1)
wcece408f + w5a2ec7c3 -> wcece408f + 2 w5a2ec7c3  [mass-action k=1.0]  (x1)
w63dbed03 + w41f876a5 -> w63dbed03 + 2 w41f876a5  [mass-action k=1.0]  (x1)
wb3cd234e + w624ed59f -> wb3cd234e + w624ed59f + w624ed59c  [mass-action k=1.0]  (x1)
w65432f84 + w6022e452 -> w65432f84 + 2 w6022e452  [mass-action k=1.0]  (x1)
wc344a2e2 + w87be4f3e -> wc344a2e2 + 2 w87be4f3e  [mass-action k=1.0]  (x1)
w3fcd72a9 + w7dca6599 -> w3fcd72a9 + w7dca6599 + w7dca659b  [mass-action k=1.0]  (x1)
w2076ee6c + wb55019e3 -> w2076ee6c + wb55019e3 + wb55019ed  [mass-action k=1.0]  (x1)
w32857488 + w760cd325 -> w32857488 + 2 w760cd325  [mass-action k=1.0]  (x1)
wec36f2dc + w13bed2ac -> wec36f2dc + w13bed2ac + w13bed2ae  [mass-action k=1.0]  (x1)
w4bf4d778 + w41ff629c -> w4bf4d778 + 2 w41ff629c  [mass-action k=1.0]  (x1)
wfb1ef876 + wd29e890e -> wfb1ef876 + 2 wd29e890e  [mass-action k=1.0]  (x1)
wafe95718 + w3b6a95da -> wafe95718 + 2 w3b6a95da  [mass-action k=1.0]  (x1)
w6009a231 + w11d79acc -> w6009a231 + 2 w11d79acc  [mass-action k=1.0]  (x1)
wca87c122 + w167e658b -> wca87c122 + 2 w167e658b  [mass-action k=1.0]  (x1)
w95c0591a + w21b01d68 -> w95c0591a + w21b01d68 + w21b01d79  [mass-action k=1.0]  (x1)
w05650503 + wdfe18980 -> w05650503 + 2 wdfe18980  [mass-action k=1.0]  (x1)
w2a1d25f1 + wea9b3542 -> w2a1d25f1 + wea9b3542 + wea9a3540  [mass-action k=1.0]  (x1)
… 9832 more

Generated by the uploader with chemart push; the hub never runs uploaded code.