AlChemy — Lambda Calculus Chemistry

Topic: AlChemy — lambda calculus as unbounded artificial chemistry

Origin

Walter Fontana & Leo Buss (1994, "The Arrival of the Fittest: Toward a Theory of Biological Organization") introduced AlChemy (Algorithmic Chemistry) as a constructive artificial chemistry based on lambda calculus. The goal was to address the "existence problem of population genetics" — not survival of the fittest (Darwin), but arrival of the fittest (what structures exist to be selected?).

Core Mechanism

Lambda calculus expressions serve as "molecules." The three key properties:

  1. Vast combinatorial space: Infinite possible objects from a finite set of building blocks (variables, abstraction, application)
  2. Constructive interactions: Collisions between expressions produce new expressions (A + B → A + B + C, where C = (A)B normalized)
  3. Structure determines interaction: The outcome is completely determined by the internal structure of the expressions involved

The simulation: initialize with N random expressions → pick two at random (mass action) → apply one to the other → beta-reduce to normal form → add result → remove random expression → repeat. Non-terminating reductions are "elastic collisions" (pragmatic reduction with step limit).

Organizational Hierarchy

Fontana & Buss identified three levels:

L0 Organizations (Trivial Fixed Point)

  • Dominated by copy/identity functions (λx.x)
  • System converges to 1 species
  • The trivial attractor — copying is easy in lambda calculus

L1 Organizations (Autocatalytic Sets)

  • Multiple distinct expressions that collectively reproduce each other
  • No member copies itself directly, but each can be produced by interactions of others
  • Robust to perturbation (adding random expressions doesn't destroy them)
  • Multiple distinct L1 organizations exist — each with its own internal logic
  • Require syntactic filters to prevent L0 takeover (originally), though Mathis et al. 2024 found L0 simulations can produce L1-like organizations without filters

L2 Organizations (Composites)

  • Composites of two or more L1 organizations plus "glue" expressions
  • Glue = expressions produced by composing functions from different L1s
  • THE KEY FINDING: L2 is RARE. When two L1 organizations are combined, three outcomes:
    1. Dominance: One organization dominates, the other disappears (most common)
    2. Mutual Destruction: Both destroyed, novel organization emerges
    3. Coexistence: Both survive together with glue (RARE)

Mathis et al. 2024 Reanalysis ("Return to AlChemy")

Key findings from revisiting AlChemy after 30 years (arXiv:2408.12137):

  1. Complex organizations emerge more frequently than expected — L0 simulations without filters can produce L1-like organizations with 10s-100s of unique expressions
  2. Organizations are robust — needed 90%+ replacement with identity function to collapse non-trivial organizations
  3. L2 composition fails — "stable organizations cannot be easily combined into higher order entities" (from abstract)
  4. Sensitivity to initial conditions — the random expression generator matters enormously. Original (probabilistic grammar) produces diverse organizations; permutation generator (uniform binary trees) collapses to trivial fixed point
  5. Formal connection to CRNs — constructive proof that typed lambda calculus can simulate any chemical reaction network

Criticisms

  1. Not real chemistry — Lambda calculus is Turing complete, but chemistry has constraints (conservation laws, thermodynamics, spatial structure) that AlChemy ignores. The 2024 paper addresses this with the CRN simulation proof, but the dynamics of AlChemy are not chemically realistic.

  2. The Halting Problem — Non-terminating reductions are handled pragmatically (step limit). This is not a principled solution — the set of "elastic" reactions depends on the arbitrary step limit. Real chemistry doesn't have this problem.

  3. L2 failure = composition failure — The most significant criticism from our perspective: AlChemy produces stable single-scale organizations (L1) but cannot compose them (L2 is rare). This is the SAME multi-scale composition problem we identified in Echo (Smith & Bedau 1997) and our sim04. Unbounded space does not solve it.

  4. Standardization artifact — Free variables must be bound (standardization), and the method of binding affects dynamics. The original method (prepending λx to head) creates long argument chains; alternative methods produce different results. This is an implementation artifact, not a fundamental property.

  5. No selection mechanism — AlChemy has no explicit fitness or selection. Organizations emerge and persist through mass-action dynamics alone. Whether they are "evolvable" (selectable) is an open question that Mathis et al. 2024 note as a future direction.

Empirical Evidence

  • Original (1994): Fontana & Buss reported L1 and L2 organizations with qualitative analysis

  • Mathis et al. 2024: Systematic reanalysis with 1000 simulations. L0 simulations produce complex organizations in ~some fraction (not all converge to trivial fixed point). L2 coexistence is rare across tested pairs.

  • Our sim05 (corrected 2026-07-27): 4 independent L1 runs, 6 L2 composition tests. 2/6 coexistence, 3 dominance, 1 mutual destruction. Each L1 run explored 112-162 unique species (unbounded space confirmed — no finite exhaustion like sim04's 510).

    The previously reported figures — 0/6 coexistence, 3 dominance, 3 mutual destruction, 246-930 species per run — were artifacts of three defects found in code review, each biasing against coexistence: species identity was not alpha-invariant (so λv1.v1 and λv2.v2 counted as different species, inflating counts and deflating every set intersection); outcomes were classified on Jaccard similarity, whose ceiling fell below the coexistence threshold for two of the six pairs; and the mixed population was seeded almost entirely from organization A, giving it a ~9:1 abundance advantage under mass action, which is why every pair returned dominance-by-A. With equal starting abundance, coexistence appears in 2/6 pairs and the result is stable across survival thresholds 0.45-0.70. See ../simulations/REVIEW.md §2 and ../simulations/sim05_lambda_chemistry/README.md.

    This weakens, but does not overturn, the "composition is rare" reading: coexistence is still the minority outcome at 33%, and Mathis et al.'s independent finding is unaffected. [[hypotheses/H10]] should be re-examined against the corrected numbers.

  • Szathmáry 1995: Classified replicators and connected lambda calculus models to biological replicator types.

Connection to Our Project

AlChemy's unbounded space vs sim04's finite space

Sim04 (binary polymers up to length 8 = 510 species) exhausted its finite space. AlChemy's molecule space is infinite (lambda expressions are unbounded). Sim05 confirms: each run explores different species (112–162 unique, mean pairwise overlap 0.061), and the space is never exhausted. Unbounded space is necessary but not sufficient — though see the correction above: with L2 coexistence at 2/6 rather than 0/6, the "not sufficient" half now rests mainly on the literature rather than on our own result. (The figure previously given here, 246-930, is the artifact this file's correction note describes; it was left asserted as fact in this paragraph until 2026-07-27.)

L2 failure = multi-scale composition failure

The L2 composition failure is EXACTLY our H1 (Composition Hypothesis). AlChemy produces L1 organizations (single-scale stable states) but cannot compose them into L2 (multi-scale). This is the same failure as:

  • Echo (Smith & Bedau 1997): no hierarchical adaptive aggregates
  • EvoLoop: converges to stable state
  • Sim03/sim04: chemical organizations stall
  • Computational autopoiesis (1974): self-maintains but doesn't evolve

The "glue" = trace→actor crossing (H7)

Fontana & Buss's "glue" expressions — the additional expressions that enable L2 composition — are analogous to our trace→actor crossing (H7). Glue is produced by composing functions from different organizations. It bridges between scales. The fact that glue rarely emerges spontaneously confirms that the crossing requires specific mechanisms (our stigmergy + autopoiesis synthesis), not just random interaction.

Computational irreducibility (H8)

You cannot predict which L1 organization will emerge from which initial soup (sensitivity to initial conditions). You cannot predict whether two L1s will compose (L2 outcome is path-dependent). This is computational irreducibility in action — you must simulate to know.

Sensitivity to initial conditions ↔ Multi-rate environment

The dramatic effect of the random expression generator on dynamics parallels our multi-rate environment concept: the "shape" of the initial distribution (analogous to environmental structure) determines the attractor landscape. Different generators → different attractors, just as different environmental rates → different evolutionary trajectories.