6 Metabiology
(ns meme-constructor.computing.post-i4-metabiology
(:require [scicloj.kindly.v4.kind :as kind]
[benjamin-schwerdtner.metabiology.mutation :as mutation]
[meme-constructor.synthesis.metabiology :as mb]
[random-seed.core :refer [random *rng*]]
[meme-constructor.figures :as fig]))Post I.4 of Part I, “A Constructor Theory of Computing and Design”.
Chaitin made the mutation a program, so that the distance between two organisms is the length of the shortest program that turns one into the other. On Push3 this kind of variation shortens the search for regular targets, but only when the criterion rewards the intermediate forms: the advantage belongs to variation and criterion together. And it shows that counting conserved sites overestimates regular design, 213 bits against the 117 that selection actually supplied.
The organism is a Push program read as an abstract constructor (post I.1, Definition I.1.6).
6.1 1. What Chaitin proved
Chaitin (2009) studied a single mutating program on a random walk of increasing fitness, where fitness is a busy-beaver problem: the larger the integer a program names, the fitter it is. Chaitin (2012b) then made mutations algorithmic: “an arbitrary algorithm that transforms … the original organism into the mutated organism”, where an \(n\)-bit mutation has probability \(2^{-n}\) (§4.4). Proving Darwin (Chaitin 2012a) is the non-technical account. Time counts mutations tried. Theorems 2 and 3 are stated for a variant \(BB'(N) = BB(N + O(\log N))\).
The proofs need a halting oracle, which compares organisms and applies mutations that may never halt (§4.6), and an uncomputable fitness built on lower bounds of the halting probability \(\Omega\) (§6). Theorem 2 counts mutations only, so knowing which mutation to try is free. And the bound on evolution is an upper bound: whether evolution is slower than design is Chaitin’s Open Problem 6.
- evolution is at most roughly quadratically slower than a free designer
- and exponentially faster than exhaustive search
- that design beats evolution
- the bound on evolution is an upper bound (Open Problem 6)
- a halting oracle
- an uncomputable fitness
- the designer's choice of mutation is free
He also notes that in this model “all structure in the programs can be hidden” (§9): the design sits in the fitness and a fixed prefix, not in the evolved organism. In the terms of Part I, Chaitin’s model is an adaptive synthesis task (C5) with one organism and a fixed criterion.
6.2 2. Algorithmic variation (C6)
Definition I.4.1 (Algorithmic variation). Fix a universal prefix-free machine \(U\). A mutation is a program \(M\) with \(U(M, K) = K'\). The variation constructor \(V\) draws \(M\) with probability \(2^{-|M|}\) and turns \(K\) into \(M(K)\). The probability of a transition and the mutation distance are
\[\begin{aligned} P_V(K' \mid K) &= \sum_{M:\ M(K) = K'} 2^{-|M|}, \\ d_V(K, K') &= -\log_2 P_V(K' \mid K). \end{aligned}\]
This is Chaitin’s definition (2012b, §4.4–4.5). What we add is the role: \(V\) is a constructor whose output is a variant.
Four standard results, in our terms:
Proposition I.4.2 (Mutation distance is conditional complexity; imported). \(d_V(K, K') = H(K' \mid K) + O(1)\), where \(H(K' \mid K)\) is the length of the shortest self-delimiting program that turns \(K\) into \(K'\) (Chaitin 2012b, eq. (1), citing Chaitin 1975).
So the distance between organisms is the length of the shortest description of the change, not the number of positions that differ. Doubling a genome changes every position after the old end, and it is one short program.
Proposition I.4.3 (Coding theorem; imported). Starting from nothing, \(P_V(K) = 2^{-H(K) + O(1)}\) (Levin 1974; Li & Vitányi 2019).
Proposition I.4.4 (What selection must supply; sketch). A generate-and-test process that draws from \(V\) needs on average
\[\frac{1}{P_V(K)} = 2^{H(K) + O(1)}\]
draws to hit \(K\). The elimination constructor, which discards variants, must supply about \(H(K)\) bits to single \(K\) out, not the raw length.
Sketch. A geometric waiting time with success probability \(P_V(K)\) has that mean. Insert Proposition I.4.3. \(\square\)
Regular designs (symmetry, repetition, reused modules) are cheap under \(V\). A point variator pays the full length. The information bound (S1′) of post I.5 generalises this to any \(V\) and many rounds.
Proposition I.4.5 (Invariance; imported). For every computable variation constructor \(W\) there is a constant \(c_W\) with \(P_V(K' \mid K) \ge 2^{-c_W}\, P_W(K' \mid K)\) for all \(K, K'\) (Solomonoff 1964; Li & Vitányi 2019).
This says a universal variator is never much worse than any other, up to \(2^{c_W}\). In practice \(c_W\) is large: in Section 4 the repository’s algorithmic variator on its own solved random targets in 1 of 20 runs, and it became competitive only mixed with point steps, a mix we chose after seeing that failure (Observation I.4.11).
Two consequences are ours.
Proposition I.4.6 (Occam without smuggling). \(P_V\) in Definition I.4.1 depends on \(K\) and \(K'\) only, not on any task. So a preference for short descriptions does not violate the unspecific-variation condition (A1′) of post I.5.
Proof. Definition I.4.1 mentions no task. \(\square\)
Proposition I.4.7 (Closed variators have holes). If \(V\) is not universal, some \(K'\) can have \(P_V(K' \mid K) = 0\). Then the alternatives condition (D2) of post I.5 fails for \(K'\) relative to \(V\), and no amount of selection yields \(K'\).
Proof by example. The point variator of Section 4 inserts only digits, so every program containing an instruction has probability 0. \(\square\)
6.2.1 2.1 Push3 and a first number
Push programs are not self-delimiting, so weights \(2^{-k}\) over programs of size \(k\) do not sum to 1. The Push3 repository therefore draws a size \(k\) with weight \(2^{-k/3}\) and then a program of that size uniformly (docs/metabiology.md). The exponential fall in description length survives. The exact measure does not, so every proposition above holds for the machine only up to constants and this encoding. \(H\) is not computable, so the experiments measure upper bounds.
How far apart are the two pictures of distance? We draw 4,000 mutations of (3 7 3 7) with seed 1 and count doublings.
(def doubled '(3 7 3 7 3 7 3 7))(def doubling
(binding [*rng* (random 1)]
(let [n 4000
kids (mapv (fn [_] (:child (mb/algorithmic-variation '(3 7 3 7)))) (range n))
hits (count (filter #(= doubled %) kids))
unchanged (count (filter #(= '(3 7 3 7) %) kids))]
{:draws n
:doublings hits
:unchanged unchanged
:bits-algorithmic (- (mb/log2 (/ hits (double n))))
;; one point path: four insertions at the end of a genome of length 4..7,
;; each with probability 1/(3 (n+1) 10)
:bits-one-point-path (reduce + (map #(mb/log2 (* 3 (inc %) 10)) (range 4 8)))})))doubling{:draws 4000,
:doublings 189,
:unchanged 2026,
:bits-algorithmic 4.403541860441015,
:bits-one-point-path 30.341807900100196}Observation I.4.8 (seed 1). About 5 % of the repository’s mutations turn (3 7 3 7) into its doubling, about 4 bits. For a point variator the same change is four accepted steps, and one path of four insertions has probability \(2^{-30}\). About half of the algorithmic draws return the parent unchanged.
- about 5 % of draws
- about 4 bits
- four accepted steps
- one path has probability 2⁻³⁰
6.3 3. The Chaitin reproduction (X1)
The Chaitin reproduction (X1) re-runs the Push3 repository’s comparison of the three regimes (evolution/compare-regimes) with small budgets: 4,000 trials, seeds 1–3, organisms that start from (), run for at most 200 steps and name numbers of at most 10,000 bits. Trials are evaluations, the compute actually spent. Accepted counts accepted mutations, Chaitin’s unit, in which the designer’s choice is free. Our designer inspects a pool of 32 mutations per step and pays for all 32.
(def x1 (mb/x1-comparison {:seeds [1 2 3] :trials 4000}))(kind/table (:medians x1))| regime | runs | median-bits | median-trials | median-accepted | saturated |
|---|---|---|---|---|---|
| exhaustive-search | 1 | 4 | 4000 | 4000 | 0 |
| cumulative-evolution | 3 | 10000 | 3981 | 12 | 2 |
| intelligent-design | 3 | 156 | 4000 | 7 | 0 |
(kind/table
(for [{:keys [regime bits trials accepted]} (:cost x1)]
{:regime regime :target-bits bits
:reached (str (:reached trials) "/" (:of trials))
:median-trials (:median trials)
:median-accepted (:median accepted)}))| regime | target-bits | reached | median-trials | median-accepted |
|---|---|---|---|---|
| exhaustive-search | 4 | 1/1 | 246 | 246 |
| exhaustive-search | 16 | 0/1 | ||
| exhaustive-search | 64 | 0/1 | ||
| exhaustive-search | 256 | 0/1 | ||
| exhaustive-search | 1024 | 0/1 | ||
| cumulative-evolution | 4 | 3/3 | 860 | 2 |
| cumulative-evolution | 16 | 2/3 | 2106.5 | 5.5 |
| cumulative-evolution | 64 | 2/3 | 2213.0 | 8.0 |
| cumulative-evolution | 256 | 2/3 | 2633.0 | 9.0 |
| cumulative-evolution | 1024 | 2/3 | 2824.5 | 12.5 |
| intelligent-design | 4 | 3/3 | 864 | 2 |
| intelligent-design | 16 | 2/3 | 2128.0 | 5.5 |
| intelligent-design | 64 | 2/3 | 2256.0 | 7.5 |
| intelligent-design | 256 | 1/3 | 3840 | 10 |
| intelligent-design | 1024 | 0/3 |
Observation I.4.9 (seeds 1–3, 4,000 trials). Exhaustive search reaches 4 bits after 246 programs and never improves. Cumulative evolution saturates the 10,000-bit substrate in 2 of 3 runs, with a median of 12 accepted mutations. The designer reaches 256 bits in 1 run of 3 and 1,024 bits in none. The repository’s published 8-seed run shows the same pattern.
Evolution beats exhaustive search, as Chaitin proved: exhaustive search pays \(2^H\) for each record, evolution conditions each draw on the parent and pays \(H(K' \mid K)\). Design does not beat evolution once the designer pays for its choice. That contradicts nothing Chaitin proved, since he never proved a separation. It says that his design regime is a free oracle, and a free oracle already contains a design.
On program synthesis the regimes collapse. On 31 problems of the General Program Synthesis Benchmark Suite (Helmuth & Spector 2015), with 3 seeds and 20,000 trials each, cumulative evolution and design return the same score in 91 of 93 runs. We cite that run and do not repeat it (commit 830b0d1 in clj-push3-play). The reason given there: in the busy-beaver landscape every improvement is a small algorithmic step from the last one, while on the benchmark “an improvement is usually structural, add a conditional or wrap a loop”, and a single hill climber cannot hold the worse forms on the way.
6.4 4. The point-versus-algorithmic experiment (X2)
The point-versus-algorithmic experiment (X2) asks whether search time scales with the raw length of a target or with its description length. Our prediction: under point mutation with raw length, under algorithmic variation with description length, with a gap that grows with the regularity of the target. The refutation condition: no difference for regular targets.
Set-up. The target is \(L\) digits: a random block of \(p\) digits, repeated to length \(L\). With \(p = L\) it is random. The organism is a Push program of (possibly nested) digit literals, and its output is the INTEGER stack, so the organism language cannot compress: any compression must come from the variator. Every run starts from (), keeps a variant only if it is strictly fitter, and stops at the target or after 20,000 trials. The score is matches minus mismatches over the longer of target and output. Three variators:
The description length is taken as \(p \log_2 10 + \log_2 L\) bits, the block plus the length, against a raw length of \(L \log_2 10\) bits. The grid is \(L \in \{8, 16, 32, 64\}\) and \(p \in \{1, 2, 4, L\}\), seeds 1–5, each seed with a fresh target. The four-minute sweep was precomputed by mb/precompute-x2! into results/postI4/x2-sweep.edn. The post re-runs four cells live as a check.
(def x2 (mb/load-edn mb/x2-path))(kind/table
(vec (for [v [:point :mixed] p [1 16]]
(let [live (mb/x2-run {:variation v :period p :length 16
:seeds [1 2 3 4 5] :trials 20000})
stored (first (filter #(and (= v (:variation %)) (= 16 (:length %))
(= p (:period %)))
(:rows x2)))]
{:variation v :L 16 :period p
:matches-stored? (= (mapv :solved-at (:per-seed live))
(mapv :solved-at (:per-seed stored)))}))))| variation | L | period | matches-stored? |
|---|---|---|---|
| point | 16 | 1 | true |
| point | 16 | 16 | true |
| mixed | 16 | 1 | true |
| mixed | 16 | 16 | true |
(def colours {1 "#1f77b4" 2 "#2ca02c" 4 "#ff7f0e" :random "#7f7f7f"})(defn cost-vs-length [rows title]
(kind/plotly
{:data (vec (for [v [:point :mixed]
c [1 2 4 :random]
:let [rs (sort-by :length (filter #(and (= v (:variation %))
(= c (mb/regularity-class %)))
rows))]]
{:type "scatter" :mode "lines+markers"
:name (str (name v) ", period " (if (= c :random) "L (random)" c))
:x (mapv :length rs) :y (mapv :median-trials rs)
:line {:color (colours c) :dash (if (= v :point) "dash" "solid")}}))
:layout {:title {:text title}
:xaxis {:title {:text "raw length L (digits)"} :type "log"}
:yaxis {:title {:text "median trials to construct target"} :type "log"}
:legend {:orientation "h" :y -0.3}
:margin {:t 50 :r 20}}}))Medians count an unsolved run as the full 20,000 trials, so a median that includes failures is a lower bound.
(cost-vs-length (:rows x2) "Search time against raw length (dashed: point, solid: mixed)")(kind/table
(for [s (mb/slopes (filter #(#{:point :mixed} (:variation %)) (:rows x2)))]
(-> s (update :slope #(/ (Math/round (* 100 %)) 100.0))
(update :medians pr-str))))| variation | regularity | medians | slope | censored? |
|---|---|---|---|---|
| mixed | 1 | [[8 101] [16 153] [32 267] [64 474]] | 0.75 | false |
| mixed | 2 | [[8 127] [16 168] [32 145] [64 661]] | 0.69 | false |
| mixed | 4 | [[8 349] [16 1072] [32 4279] [64 10847]] | 1.69 | false |
| mixed | random | [[8 1051] [16 2478] [32 10729] [64 20000]] | 1.49 | true |
| point | 1 | [[8 246] [16 420] [32 885] [64 1982]] | 1.01 | false |
| point | 2 | [[8 545] [16 3471] [32 14412] [64 20000]] | 1.76 | true |
| point | 4 | [[8 913] [16 4795] [32 16987] [64 20000]] | 1.52 | true |
| point | random | [[8 1204] [16 4441] [32 15381] [64 20000]] | 1.4 | true |
Observation I.4.10 (seeds 1–5, 20,000 trials). The slope of log cost against log \(L\) summarises each line. Under point variation, cost grows at least linearly in \(L\) at every regularity: slope 1.0 for the constant target and 1.4 to 1.8 for the others, where \(L = 64\) is censored. Under mixed variation the constant target and period 2 grow sublinearly, with slopes 0.75 and 0.69. At \(L = 64\) point variation needs 4 times as many trials as mixed for the constant target, and at least 30 times as many for period 2. For period 4 and random targets mixed variation also grows faster than linearly, and on random targets the two are within a factor of 2 at every length.
So the prediction fits the most regular targets and fails at period 4 within this budget. “Cost follows description length” is too strong: period 4 adds about 7 bits of description over period 2, yet it moves the mixed variator from sublinear to superlinear growth. The period-4 cells are bimodal, and we have not traced why.
Observation I.4.11 (same runs). The repository’s algorithmic variator alone solves the constant target in 3 to 5 of 5 runs and random targets in 1 of 20. It cannot make a local repair cheaply: half its draws return the parent unchanged, and a specific one-digit change needs a long mutator.
(kind/table
(for [r (:rows x2) :when (= :algorithmic (:variation r))]
{:L (:length r) :period (if (:random? r) "random" (:period r))
:solved (str (:solved r) "/" (:runs r))}))| L | period | solved |
|---|---|---|
| 8 | 1 | 5/5 |
| 8 | 2 | 3/5 |
| 8 | 4 | 0/5 |
| 8 | random | 1/5 |
| 16 | 1 | 3/5 |
| 16 | 2 | 2/5 |
| 16 | 4 | 0/5 |
| 16 | random | 0/5 |
| 32 | 1 | 4/5 |
| 32 | 2 | 2/5 |
| 32 | 4 | 0/5 |
| 32 | random | 0/5 |
| 64 | 1 | 3/5 |
| 64 | 2 | 2/5 |
| 64 | 4 | 0/5 |
| 64 | random | 0/5 |
Observation I.4.12 (the first score we tried). Our first score was matches minus the length difference. Under it, appending a wrong digit to a short output scores +1, so length is rewarded for its own sake, and junk digits are accepted early and then duplicated with the rest.
(cost-vs-length (:length-rewarding-rows x2)
"First score (length-rewarding): no separation")Under this score point variation beats mixed variation in 15 of 16 cells, neither is sensitive to regularity, and the refutation condition is met. We changed the score after seeing this result, and we report both because the difference is the finding.
- a wrong digit on a short output scores +1
- point beats mixed in 15 of 16 cells
6.5 5. The advantage belongs to variation and criterion together
The two negative results say the same thing. On the benchmark suite the regimes collapsed because the improving forms were not one small step apart. Under the length-rewarding score the algorithmic variator lost because the score did not reward the partial forms it could build cheaply. Algorithmic variation shortens a path only when the elimination constructor rewards the intermediate forms along it. That is the cumulative-selection proposition (S2) of post I.5: the variants must be connected under the step relation of \(V\) and ordered by the criterion. Chaitin’s \(N^2\) is a property of his landscape, where the oracle guarantees such a connection, not of the regime.
6.5.1 5.1 The per-site measure overestimates regular design
Post 7 measures design site by site, after Kimura (1968, 1983): a site’s substitution rate \(k\) against the neutral rate \(\mu\). The measure counts every constrained site. Under algorithmic variation a repeated or duplicated module is one short step, worth about \(H(\text{module})\) bits of selection. So the per-site count overstates the information in a regular design and misses the step that made it. Each accepted step of a lineage carries \(-\log_2 p\) bits of the variation that produced it, and the sum is the selection information the lineage consumed.
(kind/table
(for [r (:rows x2) :when (#{:point :mixed} (:variation r))]
{:variation (:variation r) :L (:length r)
:period (if (:random? r) "random" (:period r))
:raw-bits (Math/round (double (:median-raw-bits r)))
:description-bits (Math/round (double (:median-periodic-bits r)))
:median-lineage-bits (some-> (mb/median-lineage-bits r) double Math/round)}))| variation | L | period | raw-bits | description-bits | median-lineage-bits |
|---|---|---|---|---|---|
| point | 8 | 1 | 27 | 6 | 53 |
| point | 8 | 2 | 27 | 10 | 53 |
| point | 8 | 4 | 27 | 16 | 53 |
| point | 8 | random | 27 | 30 | 53 |
| point | 16 | 1 | 53 | 7 | 121 |
| point | 16 | 2 | 53 | 11 | 121 |
| point | 16 | 4 | 53 | 17 | 121 |
| point | 16 | random | 53 | 57 | 121 |
| point | 32 | 1 | 106 | 8 | 273 |
| point | 32 | 2 | 106 | 12 | 273 |
| point | 32 | 4 | 106 | 18 | 273 |
| point | 32 | random | 106 | 111 | 273 |
| point | 64 | 1 | 213 | 9 | 608 |
| point | 64 | 2 | 213 | 13 | 608 |
| point | 64 | 4 | 213 | 19 | |
| point | 64 | random | 213 | 219 | |
| mixed | 8 | 1 | 27 | 6 | 28 |
| mixed | 8 | 2 | 27 | 10 | 17 |
| mixed | 8 | 4 | 27 | 16 | 30 |
| mixed | 8 | random | 27 | 30 | 56 |
| mixed | 16 | 1 | 53 | 7 | 38 |
| mixed | 16 | 2 | 53 | 11 | 23 |
| mixed | 16 | 4 | 53 | 17 | 99 |
| mixed | 16 | random | 53 | 57 | 131 |
| mixed | 32 | 1 | 106 | 8 | 64 |
| mixed | 32 | 2 | 106 | 12 | 36 |
| mixed | 32 | 4 | 106 | 18 | 195 |
| mixed | 32 | random | 106 | 111 | 290 |
| mixed | 64 | 1 | 213 | 9 | 117 |
| mixed | 64 | 2 | 213 | 13 | 117 |
| mixed | 64 | 4 | 213 | 19 | 403 |
| mixed | 64 | random | 213 | 219 | 681 |
Observation I.4.13 (same runs). A point lineage consumes the same bits whatever the regularity: 53, 121, 273 and 608 for \(L\) = 8 to 64, two to three times the raw length. A mixed lineage consumes 28 to 117 bits for the constant target and 17 to 117 for period 2. On random targets the two cost about the same. A per-site measure credits the constant target of length 64 with 64 constrained sites, about 213 bits, while selection under the mixed variator supplied a median of 117.
This is a limit of the measure, not of the definition of design.
6.6 Summary
- Chaitin proved \(2^N\) for exhaustive search, linear time for a free designer and roughly \(N^2\) for cumulative evolution, all with a halting oracle. He did not prove that design beats evolution.
- Algorithmic variation (C6) measures the distance between organisms as \(H(K' \mid K)\). Selection must then supply about \(H(K)\) bits.
- The Chaitin reproduction (X1) reproduces evolution beating exhaustive search. Design does not beat evolution once the designer pays for its choice.
- In the point-versus-algorithmic experiment (X2) the mixed variator grows sublinearly for the most regular targets. The mix was chosen after the algorithmic variator alone failed, and under a length-rewarding score the separation disappears.
- The advantage belongs to variation and criterion together: algorithmic steps help only where the criterion rewards the forms between them.
- Counting conserved sites overestimates regular design: 213 bits against 117 supplied.
6.7 Open problems
- Which score is the right environment? The result depends on it, and we only know that it matters.
- Period 4. Why the period-4 cells are bimodal is not traced. A likely cause is a wrong block that was duplicated and must then be repaired digit by digit.
- A compressing organism language. If organisms could use
:integer_dupor loops, point variation could exploit regularity through the language. That case is untested. - Budgets. At \(L = 64\) several cells hit the budget, five seeds per cell are few, and the Chaitin reproduction (X1) ran 4,000 trials where takeoff can come as late as 15,000.
6.8 References
- Chaitin, G. J. (1975). A theory of program size formally identical to information theory. Journal of the ACM 22, 329–340. (verified: bibliographic data, as listed in Chaitin 2012b)
- Chaitin, G. J. (2009). Evolution of mutating software. Bulletin of the EATCS 97, 157–164. (verified: bibliographic data. Its content is taken from the summary in Chaitin 2012b, §2)
- Chaitin, G. J. (2012a). Proving Darwin: Making Biology Mathematical. Pantheon. (verified: bibliographic data only)
- Chaitin, G. J. (2012b). Life as evolving software. In H. Zenil (ed.), A Computable Universe, World Scientific, ch. 15. doi:10.1142/9789814374309_0015. Preprint of 24 February 2012. §2, §4.4–4.6, §5–7 (Theorems 1–3), Open Problem 6, §9. (verified: theorem statements, the \(BB'\) variant, the \(O(N^2 (\log N)^{1+\epsilon})\) estimate and Open Problem 6 re-read in the preprint, viXra:1202.0076)
- Helmuth, T. & Spector, L. (2015). General program synthesis benchmark suite. Proc. GECCO 2015, 1039–1046. (verified: bibliographic data)
- Kimura, M. (1968). Evolutionary rate at the molecular level. Nature 217, 624–626. Kimura, M. (1983). The Neutral Theory of Molecular Evolution. Cambridge University Press. (not re-checked)
- Levin, L. A. (1974). Laws of information conservation (non-growth) and aspects of the foundation of probability theory. Problems of Information Transmission 10(3), 206–210. (verified: bibliographic data. The coding theorem as attributed in secondary sources)
- Li, M. & Vitányi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications, 4th ed. Springer. (verified: bibliographic data)
- Solomonoff, R. J. (1964). A formal theory of inductive inference, parts I and II. Information and Control 7(1), 1–22, and 7(2), 224–254. (verified: bibliographic data)
- Schwerdtner, B. benjamin-schwerdtner-clj-push3,
docs/metabiology.mdatd65ee67, and clj-push3-play, commit830b0d1. (verified: read locally)
source: book2/notebooks/meme_constructor/computing/post_i4_metabiology.clj