Reversibilization of Free Will: Reversible Local Boundary Conditions, KL/Bregman Choice Operators, and Reversible Ledgers in Reversible Cellular Automata

Reversibilization of Free Will: Reversible Local Boundary Conditions, KL/Bregman Choice Operators, and Reversible Ledgers in Reversible Cellular Automata Anonymous Author Version: 1.10 Abstract We propose a methodology for rigorously implementing “free will” as reversible local boundary conditions (RLBC) on finite domains of reversible cellular automata (RCA), and placing both the information fidelity characterization of “why choose this not that” and the choice operator in the same reversible ledger. The core approach is: design each “decision” as a bijective update on the boundary strip, carrying reversible evidence/randomness registers when necessary to preserve flattening and sampling paths, so that it composes as an overall bijection with one-step evolution of internal RCA; the decision itself given by minimal-KL/I-projection soft selection, degenerating to hard selection (argmax) in the Γ-limit, with all information overhead precisely accounted for in Bennett reversible embedding and reversibly recoverable. Reversibility and decidability are guaranteed by CHL representation theorem, Garden-of-Eden theorem, block/partition reversible cellular automaton structure, and linear-boundary matrix criteria; the undecidability of general neighborhoods in two and higher dimensions is circumvented by selecting block permutation or linear reversible block verifiable subclasses. This paper also connects the boundary-decision paradigm with the unified windowed readout–phase– relative density of states–group delay calibration, providing end-to-end error and stability statements. 1 Notation & Axioms / Conventions 1. RCA and configuration space. Finite alphabet A,d≥1, full space X=AZd. Onetime-step global update F:X→Xcontinuous under Cantor topology and commuting with shifts if and only if it is given by finite-range local rule (Curtis–Hedlund–Lyndon, CHL). If Fis bijective, called RCA; on full lattice Zd, Garden-of-Eden theorem gives surjective ⇔pre-injective (no twins) ⇔no orphans (no predecessor patterns), and injective ⇒surjective; thus bijective if and only if both injective and surjective [?]. 2. Block/partition reversibility and linear reversibility. Adopt Margolus partition: if intra-block transformation is permutation, then global is reversible; reverse evolution implemented by inverse permutation and reverse-order partition. Reversibility of linear cellular automata under various boundary conditions (including “intermediate boundary”) reduces to invertibility of rule matrix and Kronecker decomposition criterion [?]. 3. General undecidability and verifiable subclasses. Reversibility problem of generalneighborhood CA in two and higher dimensions is undecidable (Kari); therefore this 1 paper focuses on block permutation and linear-boundary matrix two verifiable subclasses [?]. 4. Calibration identity (WSIG–EBOC convention). On windowed scattering calibration, adopt the identity ρrel(E) = 1 2πi d dElog det S(E) = 1 2πtr Q(E) = 1 2πφ′(E), where Q(E) = −i S†(E)∂ES(E), det S(E) = eiφ(E). Birman–Kre˘ın formula connects scattering phase and spectral shift function, serving as common mother scale for energy/time readout and “submission” [?]. 5. Information geometry and choice. “Minimal-KL under linear consistency constraints gives exponential family/softmax and satisfies Pythagorean identity and Fenchel duality”; “TV–KL” Pinsker bound used for temperature-perturbation-jitter stability estimation [?]. 6. Reversible ledger. Only information erasure dissipates (Landauer lower bound); logical reversibility can achieve arbitrarily low dissipation in the limit; random sampling and flattening evidence accounted for through reversible registers (Bennett) [?]. 2 Model: Reversible Local Boundary Conditions (RLBC) on Finite Domain Let Λ ⋐Zdbe a connected finite domain, take boundary strip ∂Λ of sufficient thickness. Onestep internal evolution given by some RCA FΛ. Define boundary layer operator B:A∂Λ× E −→ A∂Λ× E, where Eis reversible auxiliary register (evidence/randomness/flattening labels, etc.); this paper defaults Ealphabet finite, and localizes configurations by boundary-touching blocks to ensure overall finite-alphabet CA framework (applicable to CHL/GOE). One-round evolution defined as UFΛ◦B(boundary first, then internal). Call Breversible local boundary condition (RLBC) if satisfying:  (R1) Locality: Bcan read finite outer shell beyond ∂Λ (compress observations into E if necessary), but only writes ∂Λ and E, not touching Λ◦;  (R2) Bijectivity: (b, ϵ)7→ (b′, ϵ′) is a permutation;  (R3) Evidence accounting: All randomness, flattening indices, selected action index a⋆(or minimal sufficient evidence to reconstruct a⋆)and observation evidence used for decision are written into Efor inversion recovery (Bennett embedding) [?]. In partition implementation, let all “boundary-touching blocks” each undergo intra-block permutation; by parallel direct product of block permutations = permutation,Bautomatically satisfies (R2). Reverse-order Margolus partition and inverse permutations give B−1 [?]. 2 3 Cascade Reversibility and Decidability Proposition 3.1 (Finite Domain Cascade as Bijection).Let global Fbe RCA, and take its local implementation FΛon Λ. If Bis RLBC, and Band FΛadopt partition two-phase (e.g., Margolus) implementation such that boundary-touching blocks in each phase are pairwise disjoint, and execute synchronously according to “boundary phase → internal phase” two-phase schedule, then U=FΛ◦B is a finite-domain bijection on state (x|Λ, b, ϵ), with U−1=B−1◦F−1 Λ. When Λand Bare applied synchronously to the full lattice according to the above partition tiling and two-phase schedule, the resulting global evolution is RCA. Proof. Uis bijective with U−1=B−1◦F−1 Λ. When Λ and Bare applied synchronously to full lattice via partition tiling, by CHL the corresponding global map is continuous and commutes with shifts, and its inverse likewise [?]. Proposition 3.2 (Decidable Subclasses for Boundary-Internal Unity).In the following two implementation types, reversibility of Uis decidable and inversion constructible:  Block/partition RCA: If and only if each block rule is a permutation [?].  Linear-intermediate boundary: Reversibility reduces to invertibility of rule matrix and its Kronecker decomposition; efficient algorithms available for multi-dimensional and intermediate boundaries [?]. Remark 3.3 (General Undecidability).Reversibility of general-neighborhood CA in two and higher dimensions is undecidable (Kari), hence this paper’s RLBC selects from verifiable subclasses [?]. 4 Choice Operator: KL/Bregman Fidelity (Soft→Hard) Let boundary feasible action set A(b). Given baseline q(· | b) and moment constraints, introduce feature map ϕ:A(b)→Rm. Assumption (Feasibility): b⋆∈conv{ϕ(a) : a∈ A(b)}. Definition 4.1 (Soft Selection / I-Projection). p⋆(· | b)∈arg min p∈∆(A(b)) nDKL(p∥q) : X a p(a|b)ϕ(a) = b⋆o, whose KKT condition gives p⋆(a|b)∝q(a|b) exp ⟨λ, ϕ(a)⟩, i.e., exponential family/softmax; satisfies information geometry’s Pythagorean identity and FenchelLegendre duality [?]. Proposition 4.2 (Robustness and TV-KL Bound).When temperature/regularization parameter change introduces KL error δ, total variation deviation controlled by Pinsker bound ∥p1−p2∥TV ≤q1 2DKL(p1∥p2), serving as “temperature–jitter” upper bound; Bretagnolle–Huber bound available for refinement when necessary [?]. 3 Theorem 4.3 (Γ-Limit: Soft→Hard, via Entropy/KL Regularization).Let q∈∆(A), cost c:A → R. For τ > 0, let pτ∈arg min p∈∆(A)⟨c, p⟩+τDKL(p∥q) then pτ(a)∝q(a) exp(−ca/τ), and as τ↓0,pτ⇒δa⋆where a⋆∈arg minaca; convergence unique if minimizer unique. (With linear moment constraint) If adding Pap(a)ϕ(a) = b⋆ with feasibility (b⋆∈conv ϕ(A)), then there exists dual variable λ(τ)such that pτ(a)∝q(a) exp ⟨λ(τ),ϕ(a)⟩−ca τ. If minimizer in feasible set is unique and a point mass (exists a⋆∈ A with ϕ(a⋆) = b⋆), then as τ↓0,pτ⇒δa⋆[?]. Proof sketch. As τ↓0, entropy/KL term weight decreases, linear objective dominates; in exponential family expression −ca/τ exponent difference amplifies, concentrating probability mass on minimizer; Γ-convergence and large deviation principle give rigorous limit; moment constraint case via Lagrange multiplier scale analysis yields same conclusion. Uniqueness and selection stability given by Proposition ??. 5 Reversible Implementation: Bennett Embedding and “Reversible Sampling” Theorem 5.1 (Reversible Decider).Any soft/hard selection on finite action set admits a reversible extension writing randomness, flattening evidence, and sampling path into E: (b, ϵ)7→ (b′= Sel(b;ϵ), ϵ′), making this extension a permutation on (b, ϵ); inversion recovers sampling tree and flattening order from ϵ′and erases evidence, hence no irreversible dissipation. Proof. By Bennett logical reversibility: as long as intermediate information is not erased, can reverse erase. Implement sampling as controlled permutation of prefix-tree/alias method: Knuth–Yao DDG-tree gives entropy-optimal binary sampling framework; Walker/Vose alias method gives equivalent discrete sampling structure in constant amortized time. Writing tree/table indices and coin-flip sequences into Eyields the result [?]. Remark 5.2 (Implementation Note (Verifiable Operator Family)).On Margolus partition’s boundary-touching blocks, apply in parallel via “selection result →intra-block permutation” to obtain B; its sufficiency and necessity as permutation and inversion construction directly follow from block reversibility [?]. 6 Formal Definitions and Main Theorems Definition 6.1 (RLBC).In one-round evolution, boundary layer update B(b, ϵ) = b′, ϵ′ satisfies (R1)–(R3), and in block implementation is direct product of disjoint in one phase boundary-touching block permutations. 4 Theorem 6.2 (RLBC ⊗Local RCA ⇒Finite Domain Bijection).If FΛis RCA and Bis RLBC, then U=FΛ◦Bis finite-domain bijection; U−1=B−1◦F−1 Λ. If applying isomorphic B and corresponding FΛvia partition two-phase schedule to every translate copy of the full lattice, with boundary-touching blocks pairwise disjoint in any phase, then obtain global RCA, with inverse given by reverse phase and inverse permutation playback [?]. Theorem 6.3 (Choice = I-Projection; Soft→Hard).Let Pap(a)ϕ(a) = b⋆be moment constraint with feasibility (b⋆∈conv ϕ(A)), then (i) p⋆= arg min DKL(p∥q)unique and exponential family; (ii) For regularized family pτ∈arg min p∈∆(A)n⟨c, p⟩+τDKL(p∥q) : X a p(a)ϕ(a) = b⋆o, there exists dual variable λ(τ); and if b⋆is in relative interior of conv ϕ(A)(Slater condition), then {λ(τ)}is bounded (has cluster point). In general feasible but non-interior case, λ(τ)may diverge while the following still holds: pτ(a)∝q(a) exp ⟨λ(τ),ϕ(a)⟩−ca τ. If minimizer unique and a point mass (exists a⋆with ϕ(a⋆) = b⋆), then as τ↓0, pτ⇒δa⋆; (iii) Jitter stability controlled by Pinsker/Bretagnolle–Huber bounds [?]. Theorem 6.4 (Reversible Ledgerization).Let Sel be the soft/hard selection of Theorem ??. There exists a family of boundary block-permutations {Π(a) block}a∈A and reversible register updates such that Bθ=Y boundary-touching blocks Πblocka⋆ θ constitutes RLBC, with all sampling/flattening information written into Eand erased back in B−1 θ, no Landauer cost [?]. Theorem 6.5 (Linear-Boundary Reversibility Criterion).In linear CA and “intermediate boundary” settings, reversibility of Uis equivalent to invertibility of corresponding rule matrix; matrix can be reduced-dimension tested via Kronecker decomposition [?]. 7 Connection with Windowed Readout–Phase–Density of States– Group Delay Calibration Take the “evidence aggregation/consistency constraint” at boundaries from a class of windowed spectral readouts: in the absolutely continuous spectrum region, with the unified calibration ρrel(E) = 1 2πi d dElog det S(E) = 1 2πtr Q(E) = 1 2πφ′(E), where Q=−i S†∂ES, det S(E) = eiφ(E), express “readout” as integral functional of phase derivative/relative density of states/group delay trace; Birman–Kre˘ın formula gives equivalence of spectral shift and scattering phase, enabling explicit binding of “submission/decision” consistency constraint Pap(a)ϕ(a) = b⋆to energy-phase ledger. Sensitivity of boundary-selection soft→hard transition to “readout jitter” controlled by Pinsker-type inequalities and linearized response estimates [?]. 5 8 Paradigm Construction: Margolus-Boundary Reversible Decider On two-dimensional Margolus partition, let outer ring all be “boundary-touching blocks”. For each boundary-touching block, given finite action set A ⊂ S(A2×2) (intra-block permutation family) and feature map ϕ:A × ∂Λ→Rm. According to § ?? I-projection, for temperature τ > 0 define soft selection distribution p⋆ τ,θ(a|b)∝qθ(a|b) exp ⟨λθ, ϕ(a, b)⟩/τ, whose hard limit is a⋆ θ(b)∈arg max a∈A ⟨λθ, ϕ(a, b)⟩. Define Bθ=Y boundary-touching blocks Πblocka⋆ θ(b), with reversible register update (b, ϵ)7→ b′= Πblocka⋆ θ(b)(b), ϵ′=ϵ⊕code a⋆ θ(b), where code(·) is reversible encoding of action index. Soft case uses reversible sampling to draw afrom p⋆ τ,θ(· | b), writing sampling path and code(a) into Eto guarantee replay; hard case first computes a⋆ θ(b) based on b, writes code a⋆ θ(b)then applies permutation. Inverse process reads encoding, applies Πblock(a⋆)−1and erases encoding, thus Bθis permutation on (b, ϵ). After cascading with internal block RCA, Umaintains reversibility; ϵaccounting guarantees inversion can recover all random/evidence paths [?]. 9 End-to-End Verifiable Checklist (Theory-Only, ExperimentFree) 1. Reversibility verification: Block-permutation or linear-boundary matrix method; undecidable region of two-dimensional general neighborhoods not entered into implementation aperture [?]. 2. Choice-fidelity: Solve I-projection (or its convex dual); soft/hard mutually accessible under temperature parameter tuning; jitter-error via Pinsker/Bretagnolle–Huber bounds [?]. 3. Reversible ledger: Reversibilization of Knuth–Yao/DDG-tree or alias method; randomness and indices written into E; inversion erase-back [?]. 4. Calibration binding: Via ρrel =1 2πφ′=1 2πtr Qand Birman–Kre˘ın formula, embed “readout→constraint” in unified energy/phase ledger [?]. Appendix A: Garden-of-Eden and RLBC Consistency On Euclidean lattice, Garden-of-Eden theorem gives local pre-injectivity⇔global surjectivity. RLBC’s block permutation implementation makes boundary layer locally injective in its action domain; internal RCA is also globally bijective; their cascade maintains injectivity and surjectivity, hence overall remains RCA. This argument relies on CHL’s continuity-equivariance closedness and GOE’s surjectivity-pre-injectivity equivalence (and injectivity⇒surjectivity) [?]. 6 Appendix B: Γ-Limit for Soft→Hard Selection Let feasible set be simplex ∆(A), cost c:A → R, baseline distribution q∈∆(A). Define functional Φτ(p) = ⟨c, p⟩+τDKL(p∥q). Then pτ∈argmin Φτgives pτ(a)∝q(a) exp(−ca/τ). As τ↓0, KL term weight tends to zero, Φτ Γ-converges to linear functional Φ0(p) = ⟨c, p⟩, minimized at simplex vertices (point masses). If further assuming equi-tightness and unique minimizer a⋆∈arg minaca,then minimizer sequence pτconverges in weak topology to point mass: pτ⇒δa⋆. Large deviation principle guarantees probability mass concentration rate at exponential scale 1/τ.Moment constraint case (assuming feasibility): Adding Pap(a)ϕ(a) = b⋆(assuming b⋆∈conv ϕ(A)), there exists dual variable λ(τ); if b⋆is relative interior (Slater condition), {λ(τ)}is bounded (has cluster point), otherwise its norm may diverge while hard limit still equivalent to constrained linear programming. Exponential family solution pτ(a)∝q(a) exp ⟨λ(τ),ϕ(a)⟩−ca τ. As τ↓0, limit problem equivalent to min{⟨c, p⟩:Pap(a)ϕ(a) = b⋆}; if minimizer a⋆unique and a point mass, then pτ⇒δa⋆[?]. Appendix C: Reversible Sampler Construction Outline  DDG-tree (Knuth–Yao): Optimal discrete sampling with random bits as source; writing visit path (left-right branches) and leaf number into Eyields reversible implementation [?].  Alias (Walker/Vose): Constant-time sampling after preprocessing two tables; writing table index and threshold comparison result into E, replaying in inversion [?].  Both compatible with Bennett’s “save-erase-back” strategy, hence no irreversible thermal lower bound [?]. References [1] Hedlund. Endomorphisms and Automorphisms of the Shift Dynamical System (CHL characterization). https://link.springer.com/article/10.1007/BF01691062 [2] Reversible cellular automaton. Wikipedia. https://en.wikipedia.org/wiki/ Reversible_cellular_automaton [3] Kari. Reversibility of 2D cellular automata is undecidable.https://ui.adsabs.harvard. edu/abs/1990PhyD...45..379K/abstract [4] Smith, F.T. Lifetime Matrix in Collision Theory. Phys. Rev. 1960. https://link.aps. org/doi/10.1103/PhysRev.118.349 [5] Csisz´ar, I. I-Divergence Geometry of Probability Distributions and Minimization Problems. 1975. https://pages.stern.nyu.edu/~dbackus/BCZ/entropy/Csiszar_geometry_AP_ 75.pdf [6] Bennett, C.H. Logical reversibility of computation. IBM J. 1973. https://dl.acm.org/ doi/10.1147/rd.176.0525 7 [7] Chang et al. Reversibility of linear cellular automata with intermediate boundary condition. https://www.aimspress.com/article/doi/10.3934/math.2024371 [8] Pinsker’s inequality. Wikipedia. https://en.wikipedia.org/wiki/Pinsker’s_ inequality [9] An Introduction to Γ-Convergence. Springer. https://link.springer.com/book/10. 1007/978-1-4612-0327-8 [10] Knuth, Yao. The complexity of nonuniform random number generation.https://www.semanticscholar.org/paper/ The-complexity-of-nonuniform-random-number-Knuth-Yao/ 58f10efb7c76b41a6ddc26ff9ff94f7faa1e2e35 [11] Alias method. Wikipedia. https://en.wikipedia.org/wiki/Alias_method [12] The Garden of Eden theorem: old and new. arXiv:1707.08898. https://arxiv.org/abs/ 1707.08898 8