Axiomatic Structure of Computational Universes:\\ Discrete Configurations, Update Relations, and the Unified Time Scale Framework

Axiomatic Structure of Computational Universes: Discrete Configurations, Update Relations, and the Unified Time Scale Framework Haobo Ma1Wenlin Zhang2 1Independent Researcher 2National University of Singapore November 24, 2025 Abstract Under the assumptions of finite information density and local reversible updates, we provide a unified axiomatic definition for the “computational universe.” The core object is a quadruple Ucomp = (X, T,C,I), where Xis the discrete configuration space of the entire universe, T⊂X×Xis the one-step update relation, C is the single-step cost (time, energy, or gate count), and Iis a state function characterizing “information quality.” We introduce axioms of locality, finite metricity, and (generalized) reversibility, proving that classical Turing machines, cellular automata, and reversible quantum cellular automata can all be embedded as special cases within this framework. Furthermore, we prove that under the unified time scale hypothesis (i.e., the existence of a single-step cost function compatible with physical scattering time scales), the configuration graph (X, T,C) induces a “complexity geometry” in appropriate limits, whose geodesic distances are equivalent to a continuous version of traditional time complexity. Finally, we characterize relationships between different computational universes via simulation mappings, constructing a category CompUniv with computational universes as objects and structure-preserving simulations as morphisms, proving that the classical Turing universe, classical cellular automaton universe, and quantum cellular automaton universe form equivalent full subcategories within this category. As the first work in the “Computational Universe Theory” series, this paper aims to provide a minimal discrete and physicalizable axiomatic foundation, establishing a unified benchmark structure for subsequent complexity geometry, information geometry, and the category equivalence between physical and computational universes. Keywords: Computational Universe, Cellular Automata, Turing Machine, Quantum Cellular Automata, Unified Time Scale, Complexity Geometry, Simulation, Category Equivalence MSC 2020: 68Q05, 68Q10, 81P68, 68Q12, 18D99 1 1 Introduction “The universe is computation” represents a unified vision spanning physics, computer science, and information theory. If the entire universe is viewed as a vast discrete dynamical system, then traditional models such as classical Turing machines, cellular automata, and reversible quantum cellular automata can be understood as different slices of this “computational universe.” However, in existing literature, these models are often developed separately, rarely appearing within a unified axiomatic system, let alone establishing systematic connections with physical time scales, geometric structures, and category-theoretic “equivalences between universes.” The goal of this paper is to construct such a foundational layer: under minimal assumptions, we provide an abstract “computational universe object” Ucomp, characterizing its structure and constraints through a clear set of axioms to simultaneously encompass: 1. Classical Turing machines and their “Turing universes”; 2. Classical cellular automata and more general local discrete dynamical systems; 3. Reversible quantum cellular automata (QCA) and their universe models. We emphasize two points:  On one hand, the entire framework is discrete: universe states are modeled as points on a countable set X, and time evolution is realized by stepping on a graph (X, T);  On the other hand, the cost function Cis interpreted as discrete samples of a unified time scale, providing a bridge for subsequently viewing complexity as “geometric length.” On this basis, we define “simulation morphisms” between different computational universes, constructing the category CompUniv. This not only unifies traditional “multimodel computability equivalence” results but also provides an abstract framework for subsequently establishing “equivalence between physical universe categories and computational universe categories.” The structure of this paper is as follows. Section 2 provides basic notation and preliminaries. Section 3 presents the axiomatic definition of computational universe objects. Sections 4 and 5 respectively explain how Turing machines, classical cellular automata, and quantum cellular automata are embedded within this framework. Section 6 introduces the unified time scale and basic constructions of complexity geometry. Section 7 constructs simulation morphisms and the category CompUniv. The appendices provide detailed proofs of main propositions and theorems along with several technical discussions. 2 Preliminaries and Notation All sets, mappings, and algebraic structures in this paper are discussed within the background of Zermelo–Fraenkel set theory with the axiom of choice. By default, all sets are at most countable unless otherwise stated. 2 1. Let N={0,1,2, . . . },Zbe the set of integers, Rbe the real field. 2. For a set X, let Pfin(X) denote the family of finite subsets of X. 3. If G= (V, E) is a directed graph, then Vis the vertex set and E⊂V×Vis the directed edge set. 4. For a Hilbert space H, let B(H) denote the algebra of bounded linear operators. If U∈ B(H) satisfies U∗U=UU∗= id, then Uis called unitary. 5. When unambiguous, denote the image of f:A→Bas f(A) and the preimage as f−1(C). We are particularly concerned with locality and finite information density, which naturally appear in classical cellular automata and QCA. For uniformity, we adopt the following abstract setting. Definition 2.1 (Local Structure).Let Xbe a countable set. A local structure is a finite-degree directed graph GX= (X, EX), where for each x∈X, deg+(x) = |{y: (x, y)∈EX}| <∞ deg−(x) = |{y: (y, x)∈EX}| <∞ Intuitively, GXcharacterizes the finite-range adjacency relation of each configuration in “space.” 3 Axiomatization of Computational Universe Objects This section presents the core object of this paper: the axiomatic definition of a computational universe Ucomp. 3.1 Basic Data of Computational Universe Definition 3.1 (Computational Universe Object).A computational universe object is a quadruple Ucomp = (X, T,C,I) where: 1. Xis a countable set, called the configuration space of the universe; 2. T⊂X×Xis the one-step update relation; 3. C:X×X→[0,∞] is the cost function; 4. I:X→Ris the information quality function. To view this as a “universe-scale computational system,” we impose the following axioms on the above data. 3 3.2 Axiom System Axiom 1 (Finite Information Density).There exists a local structure GX= (X, EX) such that for any finite vertex set R⊂X, the set of configurations adjacent to R, N(R) = {x∈X:∃y∈R, (x, y)∈EXor (y, x)∈EX} satisfies |N(R)|<∞. Additionally, for each x∈X, the set of “internal states” locally relevant to xis also finite (ensured by encoding in concrete models). Axiom 2 (Local Update).For any x∈X, the one-step reachable set T(x) = {y∈X: (x, y)∈T} is finite, and there exists a finite radius r(independent of x) such that the determination of T(x) depends only on the information in a neighborhood of radius raround xin GX. Axiom 3 (Generalized Reversibility).There exists a relation T−1⊂X×Xsuch that for any x∈X, T−1(x) = {y: (y, x)∈T} is finite, and when restricted to a “physically relevant” configuration subset Xphys ⊂X,T and T−1are mutually inverse function graphs on Xphys (i.e., time evolution is bijective). Axiom 4 (Additivity and Positivity of Cost).For any (x, y)∈T, we have C(x, y)∈ (0,∞); if (x, y)/∈T, define C(x, y) = ∞. For any finite path γ= (x0, x1, . . . , xn), define C(γ) = n−1 X k=0 C(xk, xk+1) Then C(γ) depends only on Tand C, and satisfies the triangle inequality for path concatenation. Axiom 5 (Monotonicity of Information Quality).There exists a task family Q(e.g., decision problems, function computation, or measurement tasks) such that for each task Q∈ Q, there exists an information quality function IQ:X→Rsatisfying: if a path γsupports computation for task Q, then the expected information quality along γis non-decreasing; i.e., for typical paths x0→x1→ · · · → xn, E[IQ(xk+1)] ≥E[IQ(xk)] In most concrete cases, we can fix a single task (e.g., simulating a fixed external system) and omit the subscript Q, where Icharacterizes information proximity relative to some “true state” or target distribution. 3.3 Paths, Complexity, and Reachable Domains Under the above axioms, we obtain the following natural definitions. 4 Definition 3.2 (Path and Complexity).In a computational universe Ucomp, a path from x to yis a finite sequence γ= (x0, x1, . . . , xn) satisfying x0=x,xn=y, and (xk, xk+1)∈T for all 0 ≤k < n. The cost of a path is C(γ) = n−1 X k=0 C(xk, xk+1) Among all paths connecting xand y, define the distance d(x, y) = inf γ:x→y C(γ) called the complexity distance from xto y. Proposition 3.3. Under Axioms A2 and A4, if for any x, y ∈Xthere exists at least one finite path connecting them, then ddefines a generalized metric on X(possibly taking value ∞) satisfying: 1. d(x, x)=0; 2. d(x, y) = d(y, x)if Tis bijective on Xphys; 3. d(x, z)≤d(x, y) + d(y, z). The detailed proof is in Appendix A.1. Definition 3.4 (Reachable Domain and Complexity Horizon).For a given initial configuration x0∈Xand resource budget T > 0, define the reachable domain BT(x0) = {x∈X:d(x0, x)≤T} If there exists x∗∈Xand constant T∗such that for all T < T∗,x∗/∈BT(x0), while for all T > T∗,x∗∈BT(x0), then T∗is called the complexity threshold from x0to x∗. More generally, topological transitions in the boundary of the reachable domain family {BT(x0)}T >0as a function of Tcharacterize the “horizons” of complexity. 4 Embedding Classical Turing Machines and Cellular Automata This section demonstrates that both classical Turing machines and cellular automata can be viewed as special cases of computational universe objects, thus being incorporated into the Ucomp system. 4.1 Turing Machine Universe Recall the definition of a classical deterministic Turing machine: Definition 4.1 (Deterministic Turing Machine).A single-tape deterministic Turing machine is a 5-tuple M= (Q, Σ,Γ, δ, q0), where: 1. Qis the finite state set; 5 2. Σ ⊂Γ is the input alphabet, Γ is the tape symbol alphabet containing the blank symbol; 3. δ:Q×Γ→Q×Γ× {−1,0,+1}is the transition function; 4. q0∈Qis the initial state. We encode the “global configuration” of a Turing machine run as a combination of the contents of a bi-infinite tape, head position, and current state. Definition 4.2 (Configuration Space of Turing Machine Universe).Let Zdenote integer positions on the tape. Define the configuration space XM=Q×ΓZ×Z where a configuration x= (q, (ai)i∈Z, p) represents: the machine is in state q, the symbol at tape position iis ai, and the head is at position p. Define the one-step transition relation TM⊂XM×XMas: (x, y)∈TMif and only if yis the configuration obtained by applying δonce at configuration x. Let the single-step cost be CM(x, y) = 1 if (x, y)∈TM, otherwise ∞. Let IMbe the decision correctness information relative to a given input and task (e.g., a 0–1 value or negative distance to target output). Proposition 4.3. For any deterministic Turing machine M, the quadruple Ucomp(M) = (XM,TM,CM,IM) satisfies Axioms A1–A5, thus is a computational universe object. Proof sketch: A1 is guaranteed by the local structure of XMand finite tape alphabet; A2 by the locality of δ; A3 holds on the subset of “physically reachable configurations” (i.e., trajectories actually traversed by the Turing machine and their reverse trajectories); A4 is evident from CM≡1; A5 is ensured by monotonic design under task definitions (e.g., only reaching maximum information value at accepting configurations). See Appendix A.2 for details. 4.2 Classical Cellular Automaton Universe Definition 4.4 (Classical Cellular Automaton).Let Λ be a countable lattice point set (e.g., Zd), Sa finite state set. A cellular automaton is a local update rule F:SΛ→SΛ, where there exists a finite neighborhood N ⊂ Λ and local rule f:SN→Ssuch that (F(c))i=f((c)i+N) for all i∈Λ. Define the configuration space XCA =SΛ, one-step transition relation TCA ={(c, F(c)) : c∈XCA}, single-step cost CCA(c, F(c)) = 1, others ∞. The information quality function ICA is defined according to tasks. Proposition 4.5. For any classical cellular automaton F, the quadruple Ucomp(F)=(XCA,TCA,CCA,ICA) is a computational universe object. A1–A2 come from locality and finite states; A3 strictly holds for reversible cellular automata, and for non-reversible cases can be handled through state space extension or subspace restriction; detailed discussion in Appendix A.3. 6 5 Embedding Reversible Quantum Cellular Automata To incorporate quantum universe models into the same framework, we consider the abstract form of reversible QCA. 5.1 Basic Definition of QCA Definition 5.1 (Reversible Quantum Cellular Automaton).Let Λ be a countable lattice point set. For each i∈Λ, assign a finite-dimensional local Hilbert space Hi. The global Hilbert space is H=O i∈Λ Hi A reversible QCA is a unitary operator U:H → H satisfying: 1. Locality: For any bounded region R⊂Λ, there exists a finite expansion R′⊃R such that U∗A(R)U⊂ A(R′), where A(R) is the local operator algebra supported on R; 2. Translation symmetry (optional): For all translations τ: Λ →Λ, Ucommutes with the corresponding translation operator. To fit the discrete framework, we view the set of basis states of Hin a fixed orthonormal basis as the configuration set. Definition 5.2 (Configuration and Update of QCA Universe).Choose an orthonormal basis {|s⟩:s∈Si}for each Hi. Let XQCA =Y i∈Λ Si be the set of all basis state labels. For any x∈XQCA, denote the corresponding basis vector as |x⟩. Define the one-step relation TQCA ⊂XQCA ×XQCA as: (x, y)∈TQCA if and only if ⟨y|U|x⟩ = 0 The single-step cost CQCA(x, y) is taken as a constant corresponding to the singlestep physical implementation time of Uor a weighted value depending on frequency. The information quality function IQCA is defined according to the observation task of interest (e.g., classical post-processing of some measurement result). 5.2 Axioms Satisfied by QCA Universe Proposition 5.3. Under the assumptions of locality and finite-dimensional Hilbert space, Ucomp(U)=(XQCA,TQCA,CQCA,IQCA) satisfies Axioms A1–A5. Key proof points:  Finite information density comes from the finite dimension of each Hiand locality; 7  Finiteness of the one-step reachable set is given by Ubeing a local linear combination;  Inverse evolution is provided by U∗;  Positivity of single-step cost is guaranteed by the positivity of actual physical implementation time;  Monotonicity of information quality can be proved via relative entropy functions in the Heisenberg picture. Detailed arguments in Appendix A.4. 6 Unified Time Scale and Initial Construction of Complexity Geometry While this paper focuses on discrete axioms, the unified time scale is the key bridge for subsequent “complexity geometry” and “physical-computational universe equivalence.” This section provides an initial structure: how to abstract a geometric distance compatible with physical time scales from the single-step cost C. 6.1 Consistency of Single-Step Cost and Time Scale Assume there exists a physical scattering process whose frequency-resolved time scale density is κ(ω) (e.g., defined by scattering phase derivative, spectral shift function derivative, or group delay trace). We consider that the single-step cost C(x, y) in the computational universe is a combination of several such basic physical processes, with implementation time cost writable as C(x, y) = ZΩ(x,y) κ(ω) dµx,y(ω) where Ω(x, y) is the set of activated frequency bands in the corresponding physical process, and µx,y is the corresponding spectral measure. Thus, the path cost C(γ) = X k C(xk, xk+1) can be approximately viewed as discrete sampling of some continuous time integral, ultimately inducing a “complexity distance consistent with physical time scale” d(x, y). 6.2 Complexity Geometry of Configuration Graph Under Axioms A1–A4, we can view (X, T,C) as a weighted graph and consider its geometrization in certain limits. Definition 6.1 (Complexity Graph).The complexity graph of a computational universe is a weighted directed graph Gcomp = (X, T,C), with edge weights C. In some cases (e.g., when continuous control parameters exist and local rules approach continuous transformations), through Gromov–Hausdorff limits or spectral analysis of graph Laplacians, one can obtain a continuous manifold Mwith metric Gsuch that 8 shortest path distances on the graph converge to geodesic distances on the manifold at appropriate scales. This process constitutes the bridge from discrete complexity to continuous complexity geometry. Proposition 6.2 (Continuous Limit of Graph Metric, Schematic).Let {U(h) comp}be a family of computational universes corresponding to complexity graphs G(h) comp, where “mesh size” h→0. If there exists a manifold Mwith metric Gsuch that (X(h), d(h))converges to (M, dG)in the Gromov–Hausdorff sense, then discrete complexity can be viewed at large scales as “time complexity” given by geodesic distance of G. This proposition is schematic; a precise version requires additional technical assumptions; see Appendix B.1 for discussion. 7 Simulation Morphisms and the Category CompUniv To compare different computational universes, we introduce the concept of simulation morphisms. 7.1 Definition of Simulation Mapping Definition 7.1 (Simulation Mapping).Let Ucomp = (X, T,C,I), U′ comp = (X′,T′,C′,I′) be two computational universes. If there exists a map f:X→X′and constants α, β > 0 such that: 1. Step preservation: If (x, y)∈T, then (f(x), f(y)) ∈T′; 2. Cost control: For any path γ:x→y, there exists γ′:f(x)→f(y) such that C′(γ′)≤αC(γ) + β 3. Information fidelity: There exists a monotone function Φ : R→Rsuch that for all x∈X, I(x)≤Φ(I′(f(x))) then fis called a simulation mapping from Ucomp to U′ comp, denoted f:Ucomp ⇝U′ comp. If fis invertible on its image (there exists g:X′→Xsuch that g◦fand f◦gare homotopic to identity on relevant subsets), and α, β are within acceptable complexity scaling ranges, then Ucomp and U′ comp are called equivalent in complexity sense. 7.2 Category Structure Proposition 7.2. Taking computational universe objects as objects and simulation mappings as morphisms, we obtain a category CompUniv: 1. For any Ucomp, the identity map idX:X→Xis a simulation mapping; 2. If f:Ucomp ⇝U′ comp and g:U′ comp ⇝U′′ comp are simulation mappings, then the composite g◦fis also a simulation mapping; 3. Composition of simulation mappings satisfies associativity. 9 This paper provides basic axiomatic system of computational universe, embedding of classical and quantum models, and prototype construction of simulation category structure, laying a discrete and rigorous foundation for subsequent complexity geometry, information geometry, and unification with physical universe. 16