irreducible

Computational irreducibility as functoriality in Rust, implementing Jonathan Gorard's "A Functorial Perspective on (Multi)computational Irreducibility" (arXiv:2301.04690).

Core insight: A computation is irreducible iff a certain functor Z': T -> B (from computations to cobordisms) preserves composition. No shortcuts exist when Z' is functorial.

irreducible is the example consumer of the catgraph core + physics layer (v0.25.0): catgraph supplies the Fong-Spivak categorical infrastructure (cospans, spans, hypergraph categories, cospan-algebras), catgraph-applied the Petri-net substrate, and catgraph-physics the hypergraph DPO rewriting, multiway evolution graphs, confluence diamond detection, and branchial spectral analysis. irreducible owns the computation-facing layer -- interval algebra, adjunctions, monoidal coherence, discrete exterior calculus, trace analysis -- plus the computation models (TM, CA, SRS, NTM, Petri nets).

Zero clippy warnings at -D warnings. Rust 2024 edition, MSRV 1.98 (measured cross-feature maximum; the default feature set builds on 1.90, the persist tiers need 1.94, the dc-geometry tiers 1.98).

Re-exports from catgraph v0.25.0 implementing Fong & Spivak, Hypergraph Categories SS2-3:

Frobenius verification: verify_cospan_chain_frobenius() decomposes each cospan in a chain via CospanToFrobeniusFunctor and checks that composition is preserved -- a stronger categorical check than monoidal coherence.

[dependencies]
irreducible = { git = "https://github.com/tsondru/irreducible" }

use irreducible::machines::{TuringMachine, Direction};
use irreducible::analyze_trace;

let bb = TuringMachine::busy_beaver_2_2();
let history = bb.run("", 20);
let analysis = analyze_trace(&history);
assert!(analysis.is_contiguous_without_repeats);
assert_eq!(analysis.step_count, 6);

use irreducible::{
    IrreducibilityFunctor, StokesIrreducibility, TuringMachine,
};

let bb = TuringMachine::busy_beaver_2_2();
let history = bb.run("", 20);
let intervals = history.to_intervals();

// 1. Functorial: consecutive intervals compose under Eq 12
let functorial = IrreducibilityFunctor::is_composable_chain(&intervals);

// 2. Stokes: conservation laws hold
let stokes = StokesIrreducibility::analyze(&intervals).unwrap();
let stokes_ok = stokes.is_irreducible();

// 3. Frobenius: valid decomposition into generators (Fong-Spivak)
let frobenius = stokes.verify_frobenius();
let frobenius_ok = frobenius.all_valid && frobenius.composition_preserved;

assert!(functorial && stokes_ok && frobenius_ok); // all agree

persist brings in EvolutionPersistence, which stores a Vec<Cospan<u32>> — from HypergraphEvolution::to_cospan_chain or TemporalComplex::to_cospan_chain — and loads it back. It selects no storage engine on its own, so a build needs persist-mem (endpoint memory, the store lives and dies with the process) or persist-rocksdb (endpoint rocksdb://<path>). The surface is async; the library takes no runtime dependency, so the caller supplies one.

cargo run --example gorard_demo           # 12-part presentation demo
cargo run --example builders              # TuringMachineBuilder + NTMBuilder
cargo run --example bifunctor_tensor      # Tensor products, monoidal laws
cargo run --example fong_spivak           # Fong-Spivak three-perspective agreement
cargo run --example lattice_gauge         # Wilson loops, plaquette action
cargo run --example multiway_coherence    # Non-confluent fragment failing coherence
cargo run --example multiway_stokes --features dec  # Closed vs non-closed 1-forms
cargo run --example persist_evolution --features persist-mem  # Store and reload a cospan chain

cargo test --workspace                               # default features
cargo test --workspace --features manifold-curvature,dec  # CI feature leg
cargo test --features dc-geometry                    # dc_topology smoke + bridge tests
cargo test --workspace --features persist-mem        # persistence against the in-memory engine
cargo clippy --workspace --all-targets -- -D warnings  # CI gate
cargo clippy --workspace -- -W clippy::pedantic      # advisory, zero warnings

Integration suites cover: adjunction laws (Z' ⊣ Z triangle identities), the catgraph cospan bridge, computation-model classification (TM, CA, SRS, NTM, Petri), Fong-Spivak Frobenius verification, functor laws, hypergraph DPO rewriting + Wilson loops, multiway coherence (associator/braiding), branchial evolution + curvature foliation, DEC closed forms (dec), and temporal cospan-chain conservation.

Z' maps states to step numbers and computations to intervals. Theorem: Z' is a functor iff all computations in T are irreducible.

For non-deterministic (multiway) systems, both categories gain symmetric monoidal structure. Theorem: Z' is a symmetric monoidal functor iff the system is multicomputationally irreducible.

From the paper (Section 4.2): computational irreducibility is dual/adjoint to locality of time evolution in quantum mechanics. For multiway systems, Z' is adjoint to the functor defining functorial quantum field theory (Atiyah-Segal axioms).

Coherence verification now operates on real multiway evolution graphs from catgraph-physics -- a genuine non-strict symmetric monoidal category where confluence up to causal equivalence is a falsifiable property. verify_associator checks that parallel independent events at a fork point are pairwise confluent; verify_braiding checks that two events commute (share a common descendant). Non-confluent fragments produce CoherenceError::NonConfluent.

Confluence diamonds in a multiway graph are 2-simplices. A 1-form assigns costs to edges; the exterior derivative d: Omega^1 -> Omega^2 evaluates on each diamond. A closed 1-form (d_omega = 0) means cost is path-independent across every diamond -- the categorical manifestation of causal invariance.

For 1D simplicial complexes, Stokes conservation reduces to contiguity + monotonicity -- exactly the conditions for cospan composability in B. This bridges differential geometry (Stokes theorem) to category theory (cospan composition).

Cospan<Lambda> implements HypergraphCategory (Thm 3.14). CospanToFrobeniusFunctor decomposes each cospan into Frobenius generators. If composition is preserved through decomposition, the cospan chain has valid Frobenius structure -- a categorical invariant complementing the Stokes and functorial perspectives.

• catgraph v0.25.0 -- category theory infrastructure (cospans, spans, Fong-Spivak hypergraph categories); workspace tag shared with catgraph-applied (Petri nets) and catgraph-physics (hypergraph DPO rewriting, multiway evolution, confluence diamonds, discrete curvature, branchial spectral analysis)
• serde + serde_json -- serialization
• Optional: deep_causality_topology 0.10 + deep_causality_tensor 0.5 + deep_causality_linear 0.1 (Regge curvature + DEC substrate), nalgebra (matrix ops), nalgebra-lapack (LAPACK)

• Gorard (2022): "A Functorial Perspective on (Multi)computational Irreducibility"
• Fong & Spivak (2019): "Hypergraph Categories"
• Mac Lane (1998): Categories for the Working Mathematician
• Wolfram (2002): A New Kind of Science
• Abramsky & Coecke (2004): "A categorical semantics of quantum protocols"
• Atiyah (1988): "Topological quantum field theories"

• tsondru
• Claude (Anthropic)

MIT