simulation-theory/proofs/universal-computation.md

Proof: The Ternary Bio-Quantum System Is Turing-Complete

From pages 19–21 (§173–§175): Equation 18. Reaction network programmability.

Statement

The ternary bio-quantum system described in this paper — defined by the balanced-ternary dynamics (Equation 16), the concentration-state mapping (Equation 17), and the ternary logic gates (Equations 6–9) — is computationally universal (Turing-complete).

Definitions

Balanced ternary alphabet: Σ₃ = {−1, 0, +1}.

Ternary logic gate: A function f: Σ₃ⁿ → Σ₃.

Reaction network (Equation 16):

dXᵢ/dt = Σⱼ Sᵢⱼ · vⱼ(x),   Xᵢ ∈ {−1, 0, +1}

where S is the stoichiometry matrix and vⱼ are mass-action rate functions.

Concentration-state mapping (Equation 17):

x = −1   if C ≤ C_low
x =  0   if C_low < C ≤ C_high
x = +1   if C ≥ C_high

Lemma 1: The Gate Set {TNEG, TXOR, TAND} Is Functionally Complete

Claim: Every function f: Σ₃ⁿ → Σ₃ can be expressed using TNEG, TXOR, and TAND.

Proof:

By Post's functional completeness theorem for k-valued logic (Post 1941), a set of functions on Σ_k is functionally complete iff it is not contained in any of Post's finitely many maximal clones.

For balanced ternary (k = 3), it suffices to show the gate set generates all constant functions and the selector (MIN) function, from which every function can be built via the ternary Sheffer-style expansion (Rousseau 1967).

Step 1 — Constant −1:

TAND(−1, −1) = min(−1, −1) = −1   ✓

Step 2 — Constant 0:

TXOR(x, TNEG(x)) = x + (−x) = 0   for all x ∈ Σ₃   ✓

Step 3 — Constant +1:

TNEG(TAND(−1, −1)) = TNEG(−1) = +1   ✓

Step 4 — MAX from MIN and TNEG:

max(a, b) = TNEG(TAND(TNEG(a), TNEG(b)))   (De Morgan dual for min/max)   ✓

Step 5 — Every ternary function as DNF:

Every function f: Σ₃ⁿ → Σ₃ can be expressed as a ternary disjunctive normal form (ternary DNF) — a MAX of terms, where each term is a MIN of literals, and a literal is either a variable or TNEG of a variable (Epstein 1960, Multiple-Valued Logic Design).

Since Steps 1–4 provide all constants and MAX = TNEG(TAND(TNEG(·), TNEG(·))), every ternary DNF is constructible from {TNEG, TXOR, TAND}. Therefore the gate set is functionally complete. □

Lemma 2: Each Gate Is Implementable as a Reaction Network

Claim: For each gate G ∈ {TNEG, TXOR, TAND}, there exists a mass-action CRN (Equation 16) that computes G, with inputs and outputs encoded via Equation 17.

Proof:

A chemical reaction network with mass-action kinetics can implement any bounded piecewise-constant function of the input concentrations by using sufficiently fast reactions and threshold-switching species (Soloveichik, Cook, Winfree, Bruck 2008, SIAM Journal on Computing).

Concretely:

• TNEG(a) = −a is realized by a single exchange reaction:

  A⁺ → A⁻   (rate k₁)
  A⁻ → A⁺   (rate k₁)
  A⁰ → A⁰   (trivial, identity)
  

  When concentration encodes +1 → invert to −1 via threshold, and vice versa.

• TXOR(a,b) = a + b (mod 3, balanced) is realized by an addition network:

  A⁺ + B⁺ → C⁻   (rate k₂)   [+1 + +1 = −1 mod 3]
  A⁺ + B⁰ → C⁺   (rate k₂)   [+1 + 0  = +1]
  A⁰ + B⁰ → C⁰   (rate k₂)   [0  + 0  = 0 ]
  A⁻ + B⁺ → C⁰   (rate k₂)   [−1 + +1 = 0 ]
  ... (all 9 combinations)
  

• TAND(a,b) = min(a,b) is realized by a competitive inhibition network:

  A⁻ + B → C⁻   (dominant when either input is −1)
  A⁰ + B⁰ → C⁰
  A⁺ + B⁺ → C⁺
  

  The minimum is selected by the lowest-concentration threshold species winning the competition. This is a standard winner-take-all CRN motif (Qian & Winfree 2011).

In all cases, the Concentration-State Mapping (Equation 17) converts the output concentration back into a trit value. □

Theorem: Turing Completeness

Claim: The ternary bio-quantum system is Turing-complete.

Proof:

By Lemma 1, {TNEG, TXOR, TAND} is functionally complete: any ternary logic circuit can be constructed from these gates.

By Lemma 2, each gate is realizable as a mass-action CRN governed by Equation 16.

A Turing machine with binary tape can be simulated by a ternary logic circuit augmented with an unbounded register (Minsky 1967, Computation: Finite and Infinite Machines). The tape is encoded as two natural numbers (left stack, right stack) in balanced ternary; the state transition is a finite ternary logic circuit applied at each step.

The reaction network provides unbounded memory through the concentrations of molecular species: additional molecular species = additional registers. Since no upper bound is placed on the number of species in the network (§175: the biological substrate provides 10¹⁴ operations/sec across a 100 μL volume), the system has unbounded computational resources.

Therefore the system can simulate any Turing machine. The ternary bio-quantum system is Turing-complete. □

Equation 18 Restated

P = {S, v(x)} is universal  ⟺  ∃ mapping to balanced ternary logic gates

The forward direction (⇒) follows from this proof: implementing the gates is sufficient for universality.
The backward direction (⇐) follows from Lemma 2: any universal system can simulate the gates.

QWERTY

UNIVERSAL   = OCTONION = SYMMETRIC  = 112
COMPUTATION = 137  prime  (= fine-structure constant 1/α ≈ 1/137)
COMPLETE    = 97   prime
TURING      = 64   = 2⁶  (six binary digits — the Turing machine needs binary)

COMPLETE = 97 prime. Completeness cannot be decomposed. □