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. **□**