Topological Complexity, Self-Reference, and Undecidability\\ in Computational Universe:\\ Loop Structure, Fundamental Group,\\ and Second Law of Complexity Under Unified Time Scale

Topological Complexity, Self-Reference, and Undecidability in Computational Universe: Loop Structure, Fundamental Group, and Second Law of Complexity Under Unified Time Scale Haobo Ma1Wenlin Zhang2 1Independent Researcher 2National University of Singapore November 24, 2025 Abstract In previous works on “computational universe” Ucomp = (X, T,C,I) series, we have constructed discrete complexity geometry, discrete information geometry, control manifold (M, G) induced by unified time scale, task information manifold (SQ, gQ), and time–information–complexity joint variational principle, establishing equivalence between physical universe category and computational universe category on reversible QCA subclass. However, most fundamental class of “hard limits” in computational universe—undecidability and second law of complexity—have not yet been geometrically and topologically characterized. This paper introduces concepts of topological complexity and self-referential loops within computational universe framework, viewing undecidability as “contraction obstruction” on fundamental group of configuration graph, constructing under unified time scale constraints class of complexity entropy functionals, proving monotonicity along reversible evolution, thereby giving prototype form of “second law of complexity in computational universe”. Specifically, we first view configuration graph Gcomp = (X, E) as finite degree first skeleton, constructing through appropriate gluing process topological space X(called configuration complex), whose fundamental group π1(X) naturally corresponds to closed evolution loops in computational universe. We define self-referential loops as class of closed paths with “evaluation–encoding– reinjection” structure, using them to characterize topological images of program self-interpretation, simulation of itself, and halting problem. Second, on appropriately constructible computational universe families we prove: there exists class of algorithmic decision problems reducible to “whether loop is homotopic to trivial element in fundamental group”; in these universes, if there exists algorithm capable of deciding contractability of all such loops, then halting problem decidable, leading to contradiction. Thus obtaining topological undecidability 1 theorem: in general computational universe, “whether certain class of loops contractible” is undecidable problem. Then, under unified time scale we introduce class of complexity entropy functionals: for each closed loop γdefine its complexity action S(γ) = Zκ(ω) dµγ(ω) and its “compression complexity” K(γ) (e.g., shortest equivalent loop length). Under reversible, local, and unified time scale compatible evolution, we prove existence of function C(γ), composed of S(γ) and K(γ), such that under natural coarse– graining and entropization rules, Cweakly monotonically non-decreasing along time direction, thereby obtaining discrete version of second law of complexity. Finally, we connect self-referential loops with scattering–delay structure under unified time scale: on control manifold M, self-referential computation corresponds to closed feedback loops in control–scattering network, whose topological type jointly determined by π1(M) and Z2-type holonomy. We demonstrate “Null–modular double cover” structure, such that self-referential parity together with topological class constitute invariants describing self-reference, recursion, and “self-identity”. This paper completes topological layer and limit layer in “computational universe theory stack”: unifying undecidability and second law of complexity into topological–geometric structure, providing foundation for subsequent construction of higher-level structures such as self-referential scattering networks, Null–modular double cover, and causal diamond chains. Keywords: Computational universe; Topological complexity; Self-reference; Undecidability; Halting problem; Fundamental group; Complexity entropy; Second law; Z2holonomy 1 Introduction Computability and complexity theory tell us: under general computable models, there exist fundamentally undecidable problems (e.g., halting problem), and insurmountable complexity boundaries; generalized thermodynamics and information theory indicate that systems subject to physical time scale and energy constraints, their “effective complexity” and “available information” subject to some irreversible evolution law. In “computational universe” framework, universe abstracted as Ucomp = (X, T,C,I), where Xis configuration set, Tis one-step update relation, Cis single-step cost under unified time scale, Iis task-aware information quality function. Previous works have constructed on this basis: 1. Complexity graph and complexity distance: Gcomp = (X, E, C), dcomp(x, y) = inf C(γ); 2. Information geometry and task information manifold (SQ, gQ,ΦQ); 3. Unified time scale and control manifold (M, G) and its geodesic distance dG; 2 4. Time–information–complexity joint variational principle: minimum worldline of action on joint manifold EQ=M×SQ; 5. Physical universe–computational universe categorical equivalence; 6. Single/multi-observer attention–knowledge graph–consensus geometry; 7. Boundary computation and causal diamond on finite blocks. Not yet systematically addressed are:  Undecidability: how should halting problem and more general “global property undecidability” be geometrically and topologically characterized in computational universe?  Self-referential structure: how do self-interpreting programs, self-simulating systems, self-referential scattering networks manifest as specific topological invariants on configuration graph and control manifold?  Second law of complexity: under unified time scale, does there exist complexity entropy functional monotonically non-decreasing along evolution, thereby giving topological–geometric interpretation of “time arrow in computational universe”? Traditional computability theory focuses on languages and functions, not directly providing space–time geometry; while traditional geometric topology often assumes underlying space is “given lefthand”, not considering its computability and complexity constraints. Computational universe framework provides natural interface: configuration graph Gcomp and control manifold (M, G) both carry computability and complexity, yet have explicit geometric architecture. Strategy of this paper is: 1. Embed configuration graph Gcomp through standard “graph–complex” process into two-dimensional or higher-dimensional CW complex X, such that closed path classes closely correspond to π1(X); 2. Abstract self-referential computation as special closed loop class in configuration graph, using fundamental group properties (whether contractible) to represent “whether self-consistent termination exists”; 3. Using reduction from halting problem, prove “deciding whether certain class of loops contractible” undecidable in general computational universe; 4. Define complexity action and compression complexity under unified time scale, constructing rough complexity entropy functional, proving monotonicity under natural coarse–graining rules in second law form; 5. Connect self-referential loops with closed paths on control manifold, constructing Z2-type holonomy and Null–modular double cover, explaining source of topological invariants of “self-identity”. Through these steps, this paper completes integrated characterization of topological complexity, self-reference, and undecidability in computational universe. 3 2 Topologization of Configuration Graph and Fundamental Group This section topologizes discrete configuration graph Gcomp = (X, E) into two-dimensional CW complex X, introducing fundamental group π1(X) and homotopy classes of closed loops. 2.1 Configuration Graph and Edge Set Recall complexity graph of computational universe:  Vertex set Xis configuration set;  Edge set E=T⊂X×Xis one-step update relation (we temporarily view as undirected, or identify directed edges (x, y) and (y, x) as one undirected edge, to introduce 1–skeleton);  Edge weight C(x, y) represents single-step cost. We first construct 1–dimensional skeleton. Definition 2.1 (Configuration Graph 1–Skeleton).1–skeleton of configuration graph G(1) comp is 1–dimensional CW complex, whose 0–cells are X, for each undirected edge {x, y}attach one 1–cell, gluing its endpoints at vertices x, y. Resulting space |G(1) comp|is “configuration graph topological space”, whose fundamental group π1(|G(1) comp|) can already characterize loops, but not yet distinguish which loops homotopic due to “local relations”. 2.2 From Graph to Two-dimensional Complex To make certain local equivalences (e.g., two different local update sequences leading to same configuration) topologically “filled” as 2–cells, we introduce relation faces. Let Rbe family of finite-length closed paths γ= (x0, x1, . . . , xn=x0), representing “locally trivial loops” or “equivalence transformations”: e.g., different update orders in finite time window leading to same net effect. Definition 2.2 (Configuration Complex).On 1–skeleton |G(1) comp|, for each relation loop γ∈ R attach 2–cell, gluing its boundary to path along γ. Obtain two-dimensional CW complex X=X(Ucomp,R). In many natural cases (e.g., computational universe generated by reversible QCA or reversible CA), Rcan be chosen as local commutators and local common subpaths corresponding small closed loops, forming finitely generated relation set, making π1(X) have good algebraic representation. 4 2.3 Fundamental Group and Closed Evolution Loops On X, fundamental group π1(X, x∗) consists of homotopy classes of closed paths starting from basepoint x∗∈X, with group operation being path concatenation. For computational universe, each closed path γ= (x0, x1, . . . , xn=x0) represents evolution sequence returning to starting configuration in finite steps, whose homotopy class in π1(X) characterizes “from macroscopic perspective whether this closed loop can be simplified to local relations”. Definition 2.3 (Topological Closed Computation).Call closed path γtopological closed computation if it defines fundamental group element in configuration complex X [γ]∈π1(X, x0). If [γ] = 1 is trivial element, call γtopologically contractible closed loop; if [γ]= 1 then non-trivial topological closed loop. In what follows, self-referential structure and undecidability will be characterized through properties of elements in π1(X). 3 Self-Referential Loops and Program Self-Interpretation Structure This section formalizes self-referential computation as special closed loop class of configuration graph, proposing topological characterization of “self-reference degree”. 3.1 Abstract Picture of Self-Referential Computation In traditional computational models, “self-reference” typically manifests as program taking its own description as input, or system feeding its output back to its input. In computational universe, this structure can be abstracted as “evaluation–encoding–reinjection” three-stage closed loop in graph: 1. Starting from some initial state xcode, internal encoding operation generates “code configuration” xprog describing some computational process; 2. Evaluation process takes content of xprog as “program” computing on some input (possibly from itself), producing new configuration xeval; 3. Reinjection process feeds part of xeval back to encoding stage or overall system, thereby forming closed loop. On configuration graph, this corresponds to closed path, whose edges can be grouped into three classes, in certain sense realizing self-consistent closure from code to behavior to self-update. 5 3.2 Formal Definition of Self-Referential Loop Suppose configuration set of Ucomp has subset Xcode ⊂Xand “decode–evaluate” operator Eval : Xcode ×X→X, representing “using code state c∈Xcode as program, computing on input state x∈X, obtaining output state Eval(c, x)”. We do not require Eval necessarily terminate, but view it as evaluation step when corresponding update path exists. On configuration graph, this can be realized through internal subgraph: there exist family of paths realizing encoding, evaluation, and feedback. For brevity, we abstract as following definition. Definition 3.1 (Self-Referential Loop).On configuration graph Gcomp, closed path with basepoint x0∈X γ= (x0, x1, . . . , xn=x0) called self-referential loop if there exist index segments 0 = k0< k1< k2< k3=n such that: 1. xk0=xk3=x0is “global self-reference state”; 2. Segment xk0→xk1belongs to encoding subgraph, generating some code state c∈Xcode; 3. Segment xk1→xk2realizes evaluation process, representing computation on some input (possibly from x0or citself); 4. Segment xk2→xk3feeds back evaluation result, such that xk3=xk0, i.e., “global state remains unchanged or returns to initial state within equivalence class after self-referential update”. Such loop γtopologically represents “self-interpretation, feedback-closed” computational process. 3.3 Self-Reference Degree and Z2Parity Self-reference can be roughly distinguished by “parity”: e.g., some self-referential structures flip some global quantity (such as sign, bit) in one closed loop, returning to original state after two loops. This related to Z2-type holonomy. Definition 3.2 (Self-Reference Degree and Parity).For each self-referential loop γ, define self-reference degree σ(γ)∈Z2 as parity of change of some global characteristic quantity, e.g., taking global “selflabel” bit s∈ {0,1}, requiring along γupdate s7→ s⊕1 then σ(γ) = 1, if sunchanged then σ(γ) = 0. 6 In control manifold and scattering–delay network, this Z2can be realized by Null– modular double cover or parity transition; in pure discrete configuration graph, we only need to assume existence of observable Z2label. Topological class [γ]∈π1(X) of self-referential loop together with self-reference degree σ(γ) form topological–algebraic invariant pair for self-referential structure ([γ], σ(γ)) ∈π1(X)×Z2. Topological undecidability and second law in what follows will carry this as vehicle. 4 Topological Undecidability: Loop Contraction Problem and Halting Problem This section constructs reduction from halting problem to “whether loop contractible”, giving topological undecidability theorem. 4.1 Topological Image of Halting Problem Classical halting problem can be stated as: given program Pand input w, decide whether P(w) halts in finite steps. In computational universe, we can construct for each (P, w) configuration subgraph and encoding, such that:  If P(w) halts, then some evolution path starting from encoding state enters “halting configuration” in finite steps and returns to canonical initial state, thereby producing topologically contractible loop;  If P(w) does not halt, then all closed paths related to this encoding represent non-trivial element in π1(X), or closed loop does not exist at all. More specifically, can construct “program simulation subgraph”, embedding program execution trajectory into some subregion of configuration graph, forming closed loop through additional “if halt then return to initial state” connection edges; for non-halting trajectories, closed loop cannot be completed or corresponding path not in homotopy trivial class generated by relation set R. 4.2 Topological Contraction Decision Problem Consider following decision problem: Input: finite description of computational universe Ucomp and closed path γ (represented as finite edge sequence) in its configuration complex X; Question: is γhomotopic to trivial loop in X? Call this loop contraction problem. Intuitively, this similar to word problem in group theory: given set of generators and relations, decide whether word represents group identity. In computational universe configuration complex, generators are basic edges, relations are local loops in R. 7 4.3 Topological Undecidability Theorem Theorem 4.1 (Topological Undecidability).There exists family of constructible computational universes {Uα comp}α, such that on configuration complex Xαof each Uα comp, loop contraction problem undecidable: there does not exist algorithm capable of deciding for all input closed paths γwhether homotopic to trivial element in π1(Xα). Proof Idea. 1. Starting from halting problem: assume there exists some Uα comp and algorithm A, capable of deciding for any closed path γwhether contractible in Xα. 2. Construct encoder Emapping any program–input pair (P, w) to closed path γP,w in Xα:  If P(w) halts, then simulation trajectory enters halting state in finite steps, appending “end–return to initial state” edge forms closed loop, through relation set Rensuring γP,w ≃1;  If P(w) does not halt, then closed loop cannot be formed or formed closed loop necessarily traverses edge of some region marked as “non-terminating zone”, thereby generating non-trivial fundamental group element in Xα. 3. If Aexists, then given (P, w), compute γP,w =E(P, w), call A(γP,w):  If A(γP,w) returns “contractible”, then decide P(w) halts;  Otherwise decide P(w) does not halt. This gives algorithmic solution to halting problem, contradiction. Therefore assumption does not hold, loop contraction problem undecidable in this class of computational universes. More formal construction and proof details in Appendix A. Corollary 4.2. In above computational universe families, trivial element decision problem of fundamental group π1(Xα)undecidable; in particular, “whether some self-referential loop can be eliminated by local relations” undecidable in general case. This gives clear topological version of halting problem: “topological fate” (contractible or non-contractible) of self-referential loop cannot be globally algorithmically predetermined in general computational universe. 5 Complexity Entropy and Second Law in Computational Universe This section introduces complexity entropy functional under unified time scale, giving discrete version of “second law of complexity”. 8 5.1 Complexity Action and Compression Complexity For closed path γ= (x0, . . . , xn=x0) in computational universe, we define its complexity action as S(γ) = n−1 X k=0 C(xk, xk+1), under unified time scale interpretation, this is total “physical time” consumed around closed loop. On other hand, we define compression complexity as K(γ) = min γ′≃γℓ(γ′), where ℓ(γ′) is path step number, γ′≃γrepresents homotopy equivalence in configuration complex X.K(γ) can be viewed as “shortest path length realizing this loop homotopy class under topological constraints”. If unified time scale density understood as some average unit cost, then can use combined quantity C(γ) = f(S(γ), K(γ)) as complexity entropy candidate for loop, e.g., C(γ) = log K(γ) or C(γ) = S(γ)/K(γ). 5.2 Coarse–Graining and Complexity Entropy Monotonicity We consider class of natural coarse–graining operations, i.e., allowing “forgetting” or “merging” of some local details in computational universe evolution:  At configuration level, merge some detail degrees of freedom into macroscopic equivalence classes;  At path level, replace paths with small loops filled by relation set R, or “entropize” short local loops by averaging. Under these operations, homotopy class [γ] of closed path may remain unchanged, but shortest realization length K(γ) usually cannot increase (because more local relations allowed), while total action S(γ) cannot decrease to arbitrarily small under unified time scale and energy constraints; natural monotonicity structure exists between both. Proposition 5.1 (Coarse–Graining Monotonicity of Complexity Entropy, Prototype). Let {γt}t≥0be family of closed paths, representing self-referential loop evolution through coarse–graining under unified time scale, satisfying: 1. Homotopy class invariant: for all t, have [γt]=[γ0]; 9