Incompleteness = Non-Halting: An Equivalence Theorem Under a Unified Framework of Logic--Computation--Information--Dynamics

Incompleteness = Non-Halting: An Equivalence Theorem Under a Unified Framework of Logic–Computation–Information–Dynamics Haobo Ma1Wenlin Zhang2 1Independent Researcher 2National University of Singapore November 19, 2025 Version: 1.7 Abstract We establish a rigorous equivalence chain across three layers—logic–computation, information–measurement, and reversible dynamics—in an augmentation process subject to a “liveness (completeness-halting) constraint”: unreachable completeness if and only if non-termination. At the logical layer, Turing’s undecidability of the halting problem and the G¨odel–Rosser incompleteness theorem form the necessary and sufficient endpoints; at the information–measurement layer, Windowed Scattering–Information Geometry (WSIG) yields, under finite resources, a residual budget composed of aliasing–Bernoulli layer–tail term and KL model mismatch; unless all four ideal conditions—bandlimited+Nyquist, infinite-order EM (or exact-order cases), no tail truncation, and p=q—are met simultaneously (including degeneracies), this budget is strictly positive under the corresponding non-degenerate conditions at any finite stage, thus precluding halting under the liveness constraint of “residual→0”; at the dynamical layer, “completeness” is characterized by reversible local boundary completion (RLBC) of reversible cellular automata (RCA), and since surjectivity/reversibility of twodimensional CA is undecidable and there exists no uniform procedure that certifies “global bijection attained” for all instances in finite stages, boundary extension generally cannot be guaranteed to terminate in finite steps. The three layers merge into the main equivalence “Incompleteness = Non-Halting”, with several reproducible instances and extensible directions provided. Keywords: Halting problem; Incompleteness; Σ0 1-hard; Windowed scattering; Pinsker inequality; Birman–Kre˘ın formula; Wigner–Smith group delay; Reversible cellular automata; Garden-of-Eden Notation & Axioms / Conventions (Card A: Gauge Unification) We adopt the scattering unified gauge φ′(E) π=ρrel(E) = 1 2πtr Q(E),Q(E) = −iS(E)†∂ES(E).(1) 1 With the Birman–Kre˘ın formula convention det S(E) = exp(2πiξ(E)), we have ∂Earg det S(E) = 2πξ′(E) = tr Q(E). Define the total scattering phase φ(E) := 1 2arg det S(E) (continuous branch) (2) so that φ′(E) = 1 2tr Q(E), consistent with the gauge ρrel(E) = (1/2π) tr Q(E). This notation coincides with the relative density of states under unitary scattering. [?] (Card B: Finite-Order NPE Discipline) Any windowed measurement employs the Nyquist–Poisson–Euler–Maclaurin three-fold decomposition: under bandlimiting and Nyquist sampling step, aliasing terms vanish; finite-order Euler–Maclaurin provides only bounded and controllable Bernoulli layer errors; tail terms from truncated windows are controlled by support/regularity. Constant normalization follows NIST DLMF. [?] Terminology Convention: “Window/measurement/readout” uniformly refer to operator–measure–function objects (Toeplitz/Berezin compression), without experimental narratives; “liveness (completeness-halting) constraint” is defined in § 3.1. Probability Notation and KL Convention: Let pdenote the target/true readout reference probability measure and qthe model measure; p≪qmeans pis absolutely continuous with respect to q;DKL(p|q) uses natural logarithm scale throughout. 1 Introduction In an automatic augmentation process that halts only upon achieving completeness for a problem class Q, does “unreachable completeness” necessarily imply “nontermination”? We give an affirmative answer and establish equivalent criteria across three layers: 1. Logic–Computation Layer: If Qis at least Σ0 1-hard, halting would decide the halting set, contradicting Turing; in a consistent, recursively enumerable, and arithmetically sufficient stage-theory augmentation, G¨odel–Rosser ensures completeness is unreachable at any finite stage, thus the process cannot halt. [?] 2. Information–Measurement Layer: WSIG provides unified gauge and finiteresource error theory. Unless all four ideal conditions—bandlimited+Nyquist, infiniteorder EM (or exact-order), no tail truncation, and p=q—hold simultaneously, the NPE decomposition and KL–Pinsker bound guarantee a positive residual budget R>0 under the corresponding non-degenerate conditions, forcing the process to continue under the “residual→0” goal. [?] 3. Dynamical Layer: “Completeness” is realized as global bijective completion of RCA. Since surjectivity/reversibility of two-dimensional CA is undecidable, there exists no uniform procedure that certifies “global bijection attained” for all instances in finite stages; thus boundary extension generally cannot be guaranteed to terminate in finite steps. [?] 2 2 Preliminaries 2.1 Computation and Logic Notation Supplement (Halting Set): Denote K:= {(M, x)|M(x)↓} (3) the Turing halting set (Mis a Turing machine, xits input, M(x)↓means halts). Classical result: Kis Σ0 1-complete. Undecidability of Halting: No universal algorithm decides whether an arbitrary Turing machine halts. [?]Rice’s Theorem: Any non-trivial semantic property of programs is undecidable. [?]G¨odel–Rosser: A consistent, recursively enumerable, and arithmetically sufficient theory is incomplete; Rosser weakened ω-consistency to mere consistency. [?] Σ0 1-hard and r.e.: Σ0 1is equivalent to recursively enumerable; many-one reduction characterizes “at least as hard”. [?] 2.2 Information Geometry and I-Projection Pinsker Inequality (natural log): TV(p, q)≤q1 2DKL(p|q). I-Projection: The minimal DKL projection q⋆over convex constraint families exists and is unique (under moderate regularity), and is equivalent in statistics and convex optimization. [?] 2.3 Phase–Density–Delay Gauge and Birman–Kre˘ın Wigner–Smith Group Delay: Q(E) = −iS†∂ES,∂Earg det S(E) = tr Q(E). Birman– Kre˘ın: det S(E) = exp(2πiξ(E)), so ξ′(E) = 1 2πtr Q(E), equivalent to relative density of states. [?] 2.4 NPE Three-Fold Decomposition and Nyquist Condition If window wand kernel hare bandlimited with sampling step ∆ < π/(Ωw+ Ωh), then aliasing term is zero; finite-order Euler–Maclaurin provides Bernoulli layer error upper bound; finite window truncation yields tail term. Constant normalization and formulas per DLMF § 1.8 and § 2.10. [?] 2.5 Reversible Cellular Automata and Garden-of-Eden Surjectivity and reversibility of two-dimensional CA are undecidable; the Garden-ofEden theorem on amenable groups gives two equivalences: existence of no pre-image (Garden-of-Eden configuration) ⇔non-surjective, and surjective ⇔pre-injective, linked to reversibility/surjectivity properties. [?] 3 3 Model and Setup 3.1 Problem Class and Liveness (Completeness-Halting) Constraint Let Qbe a computably described decision problem class that is at least Σ0 1-hard. Process Agenerates a consistent, recursively enumerable theory augmentation T0⊂T1⊂ · · · , Ttcan decide q∈ Q.(4) Define the liveness (completeness-halting) constraint: Ahalts ⇐⇒ Tthas completely decided all q∈ Q .(5) 3.2 Resource–Window–Kernel Quadruple and Residual Budget For any finite resource quadruple R= (R, T, ∆; M)and model q, define the residual budget R:= Ealias(∆) | {z } Poisson +EEM(M) | {z } Euler–Maclaurin (absolute value/norm bound of remainder) +Etail(R, T) | {z } Truncation +cq1 2DKL(p|q) | {z } Model mismatch , (6) where the three NPE-error terms are non-negative (absolute value or norm upper bound), the last term given by Pinsker as a root upper bound from mismatch to readout difference; constant cabsorbs normalization differences. 3.3 RLBC of RCA Let Λt⊂Z2be an increasing finite domain. RLBC abstracts “external interpretation/modeling” as a reversible boundary bijection on Λt, cascaded with interior reversible updates to a global map; “completeness” means existence of t⋆such that extension to a global bijection requires no further expansion. 4 Logic–Computation Layer Main Theorems Theorem 4.1 (“Halting ⇒Decidability of Halting”, Hence Cannot Halt).If Qis at least Σ0 1-hard and Asatisfies the liveness constraint, then Adoes not halt. Proof. Since Qis Σ0 1-hard, there exists a many-one reduction fsuch that for any TMinput pair (M, x), (M, x)∈K⇐⇒ f(M, x)∈ Q. If Ahalts at t⋆, then Tt⋆decides Q, thus decides K, contradicting Turing’s theorem. [?] Theorem 4.2 (“Unreachable Completeness ⇒Non-Halting”).If each Ttis consistent, recursively enumerable, and interprets PA, then for Qsufficient to express arithmetic, there exists no t⋆such that Tt⋆is complete (G¨odel–Rosser). By the liveness constraint, Adoes not halt. [?] Corollary 4.3 (Equivalence).Under the above conditions, Never complete ⇐⇒ Never halts. 4 5 Information–Measurement Layer: Forced Non-Halting Theorem 5.1 (Non-Negative Residual Budget and Sufficient Condition for Strict Positivity).For any finite (R, T, ∆; M)and model q,R≥0. Moreover, if at least one of the following four items and its corresponding non-degeneracy condition hold simultaneously, then R>0: (i) Bandlimited+Nyquist fails and combined spectrum has non-zero mass outside [−π/∆, π/∆]; (ii) M < ∞and the 2M-th derivative of the relevant function is not identically zero on some interval (then EM remainder’s upper bound is strictly positive; per § 3.2’s “absolute value/norm upper bound” inclusion, this term is strictly positive); (iii) Window truncation exists and the observed object has non-zero mass outside the window domain; (iv) DKL(p|q)>0(zero iff p=qalmost everywhere; if they differ on a positive pmeasure set or p≪ q, then >0, possibly +∞). Proof Sketch (Revised). All four terms are non-negative; under respective non-degeneracy conditions, the corresponding term’s included quantity (upper bound) is strictly positive, other terms non-negative, so the sum is positive. If all four ideal conditions hold simultaneously (including degeneracies, e.g., truly bandlimited and Nyquist-satisfied, Mgives exact precision for involved functions, zero mass outside domain, and p=q), then R= 0. [?] Theorem 5.2 (Correct Relation of “Rand Halting”).Lemma (Necessary Condition for Complete Decision): If the liveness (completeness-halting) constraint is met at stage t, then for the readout–budget definition of § 3.2, necessarily R(t)=0; otherwise there exists ineliminable readout uncertainty, making consistent decision of some q∈ Q unattainable under finite resources. Thus, halting can only occur at stages where R= 0. If any non-degeneracy condition of Theorem ?? holds, then for any finite stage t,R(t)>0, so cannot halt in finite steps; R(t)may approach 0with resource investment, which does not affect the “unreachable completeness ⇒non-halting” conclusion. Discussion 5.3 (Observable Image of Phase–Density Mother Gauge) Under the gauge unification formula, ideal completeness corresponds to global alignment of ξ′(E) = 1 2πtr Q(E); under finite resources, “stochasticity” is the measurable projection of R>0. [?] 6 Dynamical Layer: Endless Boundary of RLBC Theorem 6.1 (No Uniform Finite-Stage Certification Procedure).Define “completeness” as existence of t⋆such that RLBC extends to a global bijection. Surjectivity/reversibility of two-dimensional CA is undecidable. If there exists a uniform procedure for all instances that outputs “attained” or “unattainable” in finite stages (two-sided finite certification), one could construct a decision algorithm, thus deciding surjectivity/reversibility, 5 contradiction. Only one-sided (“attained” only) finite certification at most gives semidecidability, insufficient for decidability; thus we assert no “two-sided” finite certification uniform procedure exists. Hence, generally RLBC boundary extension is not guaranteed to reach a terminal point in finite steps. Individual special cases (e.g., local permutation-type CA) can prove reversibility in finite stages, not contradicting this conclusion. [?] Supporting Evidence: The Garden-of-Eden theorem on amenable groups gives “surjective ⇔pre-injective”, compatible with reversibility characterization.[?] 7 Examples and Constructions Example 7.1 (Windowed Threshold and Σ0 1Embedding): Construct bandlimited window–kernel such that the predicate “there exists an energy interval where windowed relative density of states exceeds threshold” is equivalent to some machine halting; then any finite (R, T, ∆; M) makes R>0, forcing the process to continue under the “reduce residual” goal. Feasibility relies on gauge unification and Nyquist/EM error theory. [?] Example 7.2 (RLBC Completion of RCA): Take “whether Garden-of-Eden exists” or “global reversibility” as predicate, gradually expand reversible boundary; designing a terminal certification mechanism for all two-dimensional CA guaranteed to appear in finite stages would yield a decision algorithm, violating undecidability; finite certification for specific reversible/surjective CA does not imply universal decision. [?] 8 Interface with Unified System  Gauge Bridge: ∂Earg det S= tr Q= 2πξ′(E) unifies “phase derivative–group delay–relative density of states”. [?]  NPE-Nyquist Discipline: ∆< π/(Ωw+ Ωh)⇒ Ealias = 0; finite-order EM and tail terms provide controllable upper bounds. [?]  I-Projection and Stability: Minimal DKL projection gives “closest attainable model” readout alignment and stable chain. [?] 9 Limitations and Extensions 1. About Q:The equivalence relies on Σ0 1-hardness; weaker classes require individualization. [?] 2. Scattering Scenarios: Non-unitary/dissipative systems can be handled with generalized BK and trace formulas; constant normalization depends on specific coupling; see modern surveys. [?] 3. CA on Groups: For non-amenable groups, Garden-of-Eden conclusions differ; corrections needed per group properties. [?] 6 10 Conclusion Under the liveness (completeness-halting) constraint, the logic–computation layer’s Turing and G¨odel–Rosser, the information–measurement layer’s finite-resource residual budget, and the dynamical layer’s RLBC unreachability tightly interlock into Never complete ⇐⇒ Never halts .(7) This equivalence grounds the intuition “stochasticity stems from incompleteness” on verifiable unified gauge and undecidability criteria, providing structural constraints for windowed readout design and reversible dynamical semantics. References [1] A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proc. Lond. Math. Soc., 1936. [2] H. G. Rice. Classes of Recursively Enumerable Sets and Their Decision Problems. Trans. AMS, 1953. [3] K. G¨odel. ¨ Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme I, 1931; J. B. Rosser, Extensions of Some Theorems of G¨odel and Church, 1936. [4] P. G. Hinman. Recursion-Theoretic Hierarchies. Springer, 1978. [5] I. Csisz´ar. I-Divergence Geometry of Probability Distributions and Minimization Problems. Ann. Probab., 1975. [6] G. L. Gilardoni. On Pinsker’s Type Inequalities, 2006. [7] E. P. Wigner. Lower Limit for the Energy Derivative of the Scattering Phase Shift. Phys. Rev., 1955. [8] F. T. Smith. Lifetime Matrix in Collision Theory. Phys. Rev., 1960. [9] J. Behrndt, M. Malamud, H. Neidhardt. Trace Formulae for Dissipative and Coupled Scattering Systems, 2008. [10] NIST DLMF § 1.8 (Poisson Summation), § 2.10 (Euler–Maclaurin). [11] J. Kari. Reversibility and Surjectivity Problems of Cellular Automata. JCSS, 1994. [12] Moore–Myhill (Garden-of-Eden) and extensions on amenable groups. 7