WorksComputer Science
Monodromy Computation Model
Abstract
A closed path can return to its starting point while analytic continuation reaches another branch. We construct a finite computational calculus in which retained logarithmic branches supply memory, analytic observations select operations, and descent through a covering exposes deeper memory. Three branch coordinates suffice, and every finite observation uses the same cubic power covering. Each program defines a globally real analytic return map whose integer-lattice execution is realized by actual path lifting. Our first theorem simulates every finite-alphabet, finite-control Post–Turing machine, preserving complete configurations, halting, and divergence. Our second theorem identifies the partial numeric functions of the calculus, under fixed primitive-recursive input and output maps, with exactly the partial recursive functions. Deleting descent leaves a Forward language with a syntax-derived finite observation quotient and a primitive-recursive halting predicate. This yields a strict separation within the calculus and identifies access to deeper memory as its decisive additional operation. The constructions and semantic correspondences are formalized in Lean 4 with Mathlib.
Introduction
Digital computation is described by discrete state transitions. Continuous-time models such as Shannon’s general-purpose analog computer [11] and real-arithmetic models such as the Blum–Shub–Smale machine [1] organize computation through different state spaces and primitive operations. Here the organizing structure is branch transport under analytic continuation.
A closed path can change an analytic branch. Continuing a logarithm around the origin changes its value by times the winding number. The retained branch records this integer, and endpoint-fixed homotopies preserve its transport [9 §1.3]. Can this geometry support memory, conditional execution, and universal computation within a finite effective calculus?
We introduce the Monodromy computation calculus. Logarithmic branches retain integers; a cubic covering observes their residues; analytic selectors turn those observations into internal control. Affine writing and covering-level descent expose successive digits of memory. Finite expressions determine each return and its stopping signal, and generate paths whose actual lifts reach the next state. The contributions are:
A finite calculus with three retained branch coordinates, integer affine updates, analytic selection, descent, and internal feedback. Each program has a globally real analytic return map and a path-lifting realization of every finite run.
Theorem I: a native simulation of every finite-alphabet, finite-control Post–Turing machine, preserving each primitive step, the complete configuration, halting, and divergence.
Theorem II: under fixed primitive-recursive input and output maps, . Deleting descent gives a Forward language with primitive-recursive halting. An undecidable partial-recursive domain proves strict separation between the two languages.
A Lean 4 formalization of the definitions, compilation, complete-execution correspondences, and structural separation.
Analytic simulation of Turing machines has a substantial history. Koiran and Moore [10] use integer encodings, analytic selectors, and radix division to obtain universal analytic maps. Graça, Campagnolo, and Buescu [8] develop robust analytic simulations, and Graça and Zhong [7] obtain robust one-dimensional analytic maps. Our contribution organizes these established computational ingredients through a finite covering syntax, actual transport semantics, a fixed effective interface, and a descent deletion theorem. The latter identifies a structural difference between retaining unbounded state and being able to access it in future computation.
Conventions. We write . Division of integers by a positive integer is Euclidean: , with $0 \leq k \mathbin{\operatorname{mod}} B < B$, also when . A value of Part A is either a result in A or undefined. For a partial value , the expression means its image under a total map ; it is undefined exactly when is undefined. Thus equalities in Part A preserve both results and divergence.
Mathematical Preliminaries
Transport and logarithmic memory
A covering supplies a precise meaning for carrying a branch. A map is a covering when every point of has an open neighborhood whose preimage is a disjoint union of open sets, each mapped homeomorphically onto that neighborhood. For a path and each , there is a unique lift starting at . Its endpoint defines transport
If means first , then , the standard lifting theorems give [9 §1.3]
Endpoint-fixed homotopies preserve transport. For loops, these endpoint maps form the monodromy action on a fiber.
For the complex exponential and the power maps on , local inverse branches are holomorphic. Carrying such a branch along a path is analytic continuation, represented by the path’s lift. A Riemann surface separates different branches into distinct points over a common base [6]. The construction below uses the explicit exponential and power coverings, together with their regular-root selectors.
For memory we use the exponential’s real angular restriction
Its fiber above 1 is . These are the angular representatives of logarithmic branches. We use the normalized coordinate for the retained angle . The loop transports to : its lift is . In particular, a fixed loop acts by the same translation on every branch.
Retaining a point of the fiber is essential. The common base value 1 alone contains no record of the integer . Several retained branches will be represented by a vector .
A finite observation of an infinite branch
To inspect one digit of a retained integer, factor the exponential covering through a power covering. For , put
For integer , the observed root depends exactly on . The state retains all of , while this observation has only values. Throughout the computational calculus we fix .
This observation is itself compatible with path lifting. For a continuous real curve , is the lift through of starting at . Uniqueness of lifting proves that its endpoint is . Each expression using an observation will have its own induced curve of this form.
Regular roots as analytic selectors
A finite observation becomes a choice of operation through an analytic interpolant. Suppose is entire and is a regular point, so . Define the normalized divided-difference kernel
The singularity at is removable. Consequently is entire; on the fiber it equals 1 at and 0 at every other point. If are distinct regular roots in one fiber, then selects at .
For the cubic cover, let , . The kernels and their real observations are
The polynomial formula includes the removable value in (4). Each is real analytic on , and
Thus a finite choice is an analytic formula, evaluated at the current retained state.
The kernels also respect hierarchical composition. For entire with and , the divided-difference chain rule gives
When the factors telescope. When and both sides vanish, and at both sides equal one. This is a normalized instance of the classical chain rule for divided differences [5]. It explains how selection at one level can be refined by selection at the next. Our finite syntax will implement the hierarchy by nested cubic queries.
Syntax and Semantics of the Monodromy Calculus
The universal calculus retains three normalized logarithmic coordinates , representing the angles above the common base point 1. In the Turing realization, stores finite control and the current symbol, and store two words. We first describe the memory operations, then give their finite syntax for an arbitrary finite number of coordinates. Both main theorems use .
Memory, writing, and descent
The selectors provide both a branch query and its companion descent:
For integers, these formulas satisfy
The second equality is the Euclidean decomposition of . Descent removes a digit whose value has first been observed; applying the same observation to the result reveals the following digit.
For binary words, reserve zero for the empty word and use the nonzero ternary digits for letters:
This is injective. Indeed, the residue modulo three distinguishes an empty word from its first letter, and division by three recovers the tail; induction recovers the whole word. Prepending is the affine write , and removes the first letter. For example,
The two observations identify the letters 0 and 1, followed by the empty word. The same cubic covering is used throughout.
Finite expressions and guards
A program must give a finite description of every operation it can perform. Fix coordinates. Its expressions are generated by
The integer interpretation uses ordinary integer arithmetic, selects branch , and interprets as Euclidean division by three. The real interpretation uses the same arithmetic and the formulas
Both the key and the possible outcomes can depend on the whole current state. All expressions are finite trees.
Stopping is specified in the same language of finite observations. A guard is generated by
Its integer interpretation is Boolean. Replacing its constant leaves by 0 and 1 gives an expression and hence a real analytic indicator . For a guard and expressions , define by replacing each true leaf of by and each false leaf by , preserving all query nodes. This is again an expression of (3.4).
Lemma 3.1 (Exact analytic interpretation). Every expression defines a real analytic function on , and
where integers on the right are embedded in . A guard indicator is 1 exactly at its true integer states and 0 at its false integer states. Moreover,
Proof. Use simultaneous structural induction. Coordinates and constants are analytic, and sums and products preserve analyticity. A query is the finite sum (3.5) of analytic compositions and products; descent is (3.6). On integer states, each induction hypothesis makes the key an integer, so (3.2) gives the required query or quotient. The guard and gate assertions follow by induction on the guard tree.
Returns, stopping, and complete execution
The program consists of a guard and an update expression for each coordinate.
Definition 3.2 (Program and execution). A program has returning expressions . Write
Its partial step stops at when is true, and otherwise continues at . The complete result is at the first with true, and is undefined if no such exists.
By Lemma 3.1, is globally jointly real analytic, preserves the integer lattice, and restricts there to . At a stopped integer state , so returns can be counted after halting by keeping the state stationary. The native memory domain is the exact lattice inside , with its real coordinates and retained exponential branches. Its native step tests the internally generated indicator and otherwise applies .
Let be the inclusion of an integer state into this native domain. Induction on each step and the first stopping time yields the full partial-value equality
The same induction shows that an infinite integer run has an infinite native run. Conversely, every native step on this domain is the image of the integer step. Thus (3.8) also preserves divergence.
The guard, branch choices, and writes are functions of the current state and the fixed finite syntax. That syntax is the runtime controller; a source Turing table enters when the program is constructed. Execution consists of discrete returns, with the stopping signal read at those returns. The following path generator realizes each return.
Actual continuation paths
We now connect a return to transport rather than merely identifying its endpoint symbolically. For a native state , define the coordinate angle curves and their base loops by
Both endpoints of are 1. The retained starting angle is . The curve is a lift of the generated loop with this starting point, so uniqueness of lifting gives
The program’s internal analytic rules first determine its return; the interpolation in (16) then generates a path realizing that return through the exponential covering.
Proposition 3.3 (Finite-run lifting). Concatenate the generated loops for consecutive returns, updating the state after each return. The resulting path satisfies
Every query node also follows actual transport through the cubic power covering along its own induced base path.
Proof. Equation (17) proves the case of one return, and transport composition (1) proves the finite-run statement by induction. For a query key along a continuous state curve , use the continuous real curve . Equation (3) identifies as the unique lifted query curve. Its endpoint at an integer state is the root indexed by .
Endpoint-fixed homotopies of the generated base paths preserve these transport results. This statement concerns the path realization of a specified return. Its computational meaning comes from the finite analytic rule that generated the path.
Theorem I: Turing Universality
Arbitrary finite tables from cubic queries
Repeated observation and descent read an arbitrary finite ternary address. Let be the expression querying a table with entries. Define
Induction using proves
The same construction works for guards. Every tree is finite, and every node uses the same cubic query or descent.
For an alphabet with , encode letter as the binary word of length whose only 1 is at position . Its ternary block value is
The are distinct and satisfy . A query of depth therefore reads the first letter, including the empty-word sentinel, and descents expose the tail. The recurrence proves injectivity of by the same residue-and-quotient argument as for (10). This block encoding accommodates any finite alphabet while keeping the covering degree fixed.
Two stacks and a finite controller
We use the Post–Turing convention formalized as Mathlib’s [3]. A table has a finite alphabet with a distinguished blank and a finite control set with an initial label. Each pair either halts or specifies a new label together with one primitive instruction: write a symbol, move left, or move right. A conventional write-and-move instruction is represented by a finite sequence of these primitives.
A complete configuration can be represented by
where and are finite words, nearest symbols first, and is the current symbol. Words represent blank-extended half-tapes: appending trailing blanks gives the same half-tape. Every finitely supported tape has such a representative. Let return the first symbol, or the blank on an empty word. A right move with target label is
A left move is symmetric, and writing changes only and the label. These operations induce exactly the usual operations on the entire blank-extended tape.
Choose blank-preserving enumerations and , with the blank and initial label numbered zero. Encode a stack configuration by three integers:
The first coordinate jointly stores the finite controller and the current symbol; the other coordinates store the two unbounded words.
The integer return row for a right move is explicit. If encodes , set
where is a finite table on , returning the decoded letter at a valid block and blank at zero. Its other entries can be assigned arbitrarily, for instance blank. Equation (20) implements this table. A left row exchanges the stack roles, and a write row is . Thus every row belongs to the finite cubic syntax.
There are possible control-symbol pairs. A table query of depth selects the corresponding row from coordinate ; indeed . Addresses outside the source table are stationary halting entries. A guard tree with the same address reports exactly the halting entries of the source. The compiled program is denoted .
Lemma 4.1 (One-step compilation). For every stack configuration , including halting ones,
Here both sides are optional successors: a halting step has no successor. The code is injective on stack configurations.
Proof. The control query selects the entry indexed by . For a write, the first coordinate changes to the prescribed label and symbol and both stacks stay fixed. For a right move, , while and its block residue recovers . These are exactly (22) and (24). The left case is symmetric. The compiled guard is true exactly when the source entry halts. Finally, the first code coordinate recovers by finite product enumeration and the other two recover their words by injectivity of .
The full simulation theorem
Theorem 4.2 (Theorem I: Turing simulation). For every finite-alphabet, finite-control Post–Turing machine , there is a program with three retained logarithmic branches and only cubic queries and descents, with the following properties. Every complete source configuration has a representing native state. From every such representation, one source primitive step is one native return. For each number of returns, the native state represents the entire source configuration, with halting configurations kept stationary. Complete execution preserves the final configuration, halting, and divergence in both directions. Every finite native run is realized by the actual transports in (18), and its return map is globally jointly real analytic.
Proof. First enumerate the finite alphabet and control, preserving their distinguished elements. A complete source tape has representatives , as above. Initialize the native state with . Lemma 4.1 and induction give the exact stack execution at every return. Passing to blank-extended half-tapes commutes with each move and write, so this execution represents the whole source tape, independently of trailing-blank representatives.
At any represented configuration, the source has no successor exactly when the native guard is true. Consequently, a source halt yields a native halt at the same return with the represented final configuration. Conversely, the first native halt is a source halt, since its guard is precisely the source table’s stopping predicate. If either run continues forever, this equivalence at every finite return forces the other to continue forever. Equivalently, on stack representatives the complete partial values satisfy
and decoding the right side gives the complete source result. Equation (15) transfers this equality to native execution. Lemma 3.1 gives global analyticity, and Proposition 3.3 supplies each finite run’s actual lifted paths.
A complete computation
Consider a two-symbol alphabet with blank , two controls , , and the table
with all other entries halting. Start with current symbol and right word . For , the blocks of letters and are and , so , , and . The entire run is
| Return | Source configuration | Integer state | Action |
| 0 | write 1 | ||
| 1 | move right | ||
| 2 | halt |
Table 2.
The first return changes the control coordinate by . The second changes the three coordinates by . Thus their exponential base loops have these respective integer windings; lifting from the retained branches gives exactly the displayed states. The halting guard is generated by the same finite control query as the updates. This example is a direct instance of the compilation rules; the general theorem proves the same correspondence for arbitrary finite tables and unbounded word lengths.
Theorem II: Characterization and Sublanguage Separation
A fixed numeric interface
A computational characterization must account for the encoding of both inputs and results. We fix once and for all two total maps
They are independent of the requested function and the program. The input map prepares a canonical binary numeric tape over the fixed alphabet used by Mathlib’s partial-recursive-to-Turing translation. It then stores the current symbol, an empty left word, and the encoded right word in the three coordinates. The output map decodes only the right word, reads its main-track bits in order, and ignores separators and blank symbols. Appendix A specifies both maps, including their values on malformed integer states.
Lemma 5.1 (Effective interface). The fixed maps and are primitive recursive. If a completed configuration is the canonical numeric result for , then its native code has output .
Proof. Finite-symbol encoding, binary numeral construction, list operations, and the recurrence (21) are primitive recursive. For decoding a natural code , scan its lowest block and replace by . A valid nonempty block code decreases, and the encoded number bounds the word length. Running exactly the original scan steps, with zero or an invalid block ending the scan, gives a total primitive-recursive decoder. On valid codes it inverts . Clamp negative integer coordinates to zero. The output fold replaces an accumulator by at a bit and leaves it unchanged at every other symbol. It is primitive recursive and reads the canonical numeric tape as . Trailing blanks leave the fold unchanged, so the result also holds for any representative of the same half-tape.
Upper bound: effective syntax
Lemma 5.3 (Effectiveness of finite execution). For each fixed finite program , its integer next-state map and guard are primitive recursive. Its complete execution is partial recursive under a standard finite-vector integer encoding.
Proof. Integer addition, multiplication by a fixed integer, and Euclidean division and remainder by a positive fixed integer are primitive recursive in the signed integer encoding. Structural induction on expressions therefore proves the claim for their interpretations: a query is a case distinction over three primitive-recursive branch values, and descent is division by three. Induction on guards proves their claim, including the gate used for the returning expressions. The partial step, with its optional successor, is consequently primitive recursive.
Iterate this effective step until it stops. Formally, the loop body returns either the current state as a final result or a successor to iterate. Unbounded iteration of such an effective body is partial recursive. Alternatively, search for the least with the primitive-recursive predicate true, and return . This computes exactly Definition 3.2, with the search undefined precisely on the infinite runs.
Proposition 5.4 (Computational upper bound). Every function in is partial recursive.
Proof. eq:5.2 expresses the function as the composition of the primitive-recursive input, the partial-recursive execution, and the primitive-recursive output. These classes are closed under the indicated composition.
Lower bound: preserving numeric results
For completeness, we describe the classical computation-theoretic bridge used in addition to Theorem 4.2. The partial recursive functions are generated from zero, successor, and projections by composition, primitive recursion, and unbounded search. Each has a finite code and can be executed by a finite-control stack machine on a fixed finite alphabet. Composition stores intermediate results; primitive recursion keeps a counter and accumulator; unbounded search increases a candidate until its defining test returns zero, continuing forever when that computation supplies no result. These constructions are the standard route from partial recursion to Turing computation. Mathlib supplies their formal implementation and the translations from stacks to a tape and then to Post–Turing primitives [2, 3].
The following form records the exact interface needed here. For every partial recursive , there is a source code and a finite-support Post–Turing table over one fixed alphabet such that
Here is the fixed numeric input word, and is the complete canonical final configuration carrying numeric result . It includes the final label and the entire tape. The translated code visits only finitely many labels: induction over its finite syntax supplies a closed finite support containing the initial label. Restricting to that support makes the control set finite while preserving every reachable step.
The complete partial equality (5.3) follows through the translations, rather than just a stopping equivalence. The stack-to-tape representation determines the whole packed tape from all its track projections. Hence each terminal stack configuration has its specified canonical terminal tape; the later primitive translation preserves that complete configuration. This also gives the converse implication for termination and preserves divergence.
Proposition 5.5 (Computational lower bound). Every partial recursive belongs to .
Proof. Choose as in (5.3), restrict to its closed finite support, enumerate its control with the initial label zero, and apply the cubic compilation of Section 4. The source alphabet and are fixed independently of . Since the initial label is zero, the code of the initial stack configuration is exactly : its first coordinate is just the numbered current symbol, regardless of the number of control labels. The remaining coordinates are zero and the encoded right word. The exact partial equalities of the source translations and (26) identify every native terminal state with the corresponding canonical result tape. Lemma 5.1 reads that state as . Thus if returns , native execution returns a state read as ; if native execution returns a state, the source has returned, and its unique numeric result is its readout. If is undefined, the complete-execution equalities force native execution to be undefined as well. This is precisely (5.2).
Theorem 5.6 (Theorem II: exact characterization). Under the fixed primitive-recursive maps and ,
where is the class of partial recursive functions . Each realizing program uses three retained branches and the same degree-three power covering for every finite query and descent. Its native return map is globally jointly real analytic and its finite runs satisfy (18).
Proof. Propositions 5.4 and 5.5 give the two inclusions. Lemma 3.1 and Proposition 3.3 supply the analytic and transport properties for the very same realizing program.
Forward execution and its finite observation
The characterization establishes the capacity of the whole calculus. To isolate the contribution of descent, call a term, guard, or program Forward when every expression in it is built without . The remaining operations still allow unbounded integer growth and arbitrarily nested finite queries.
Lemma 5.7 (Closed residue observation). For each Forward program in coordinates, one can compute from its syntax a positive integer such that coordinatewise congruence modulo is preserved by and determines the guard .
Proof. More generally allow any finite query degree in the syntax; the cubic language is its special case. Define a syntactic support certificate at recursively. Coordinates and constants are supported; sums and integer scaling preserve support of their subterms. A query of degree is supported when and its key and all branches are supported at . Induction on a certificate proves that the term’s value modulo depends only on the input modulo : at a query, congruent keys have equal residues modulo , select the same branch, and give congruent results.
A positive sufficient modulus is obtained recursively: use 1 for coordinates and constants, multiply moduli at sums, preserve the modulus at integer scaling, and at a query multiply , the key’s modulus, and all branch moduli. Induction on support certificates shows that they persist on replacing a modulus by a multiple. The analogous recursion on guard trees makes their Boolean values equal on congruent inputs. Take a common product for the guard and all updates. The guarded return then preserves congruence, since congruent states make the same stopping choice. All these are finite computations on syntax.
Consequently the observation evolves autonomously on the finite set . It carries a well-defined successor and stopping predicate :
This quotient preserves the whole observed partial execution, including its domain of definition.
Theorem 5.8 (Forward halting and strict separation). For a Forward program and a syntax-derived modulus ,
Its halting predicate on integer states is primitive recursive. There is a function in computed by no three-coordinate Forward program under the fixed interface .
Proof. The quotient has states. If its first observations contain no stopping state, either they already contain a repetition or the next observation repeats one of them. Determinism then makes all subsequent observations cycle without stopping. This proves (30). The finite iteration and guard are primitive recursive by Lemma 5.3, and the bound is a constant for the fixed program, so bounded search proves primitive-recursive halting.
For strictness, enumerate the ordinary partial-recursive codes and let be the result of the code numbered on input zero. This is partial recursive and has an undecidable domain by the halting theorem. Theorem 5.6 realizes in the full calculus. A Forward realization would decide its domain by applying the halting test to the fixed primitive-recursive input , a contradiction.
The argument uses only a finite autonomous observation carrying the stopping decision. In particular it gives a general principle beyond this syntax.
Corollary 5.9 (Closed observation barrier). Suppose has an observation into a finite set with a fixed finite encoding, , and stopping is . If an input initialization has a computable observation , then the halting domain on these inputs is decidable.
Proof. Start at and inspect the first finite observations. The preceding repetition argument decides whether a stopping observation occurs. The hidden state space may be infinite.
Descent and the depth of observation
Descent breaks the closed residue argument in an exact way. The following result concerns all integers, making its quantifiers independent of any particular word encoding.
Proposition 5.10 (Exact resolution of descent). Let , , , and . Then
If , preservation at every depth is equivalent to , where congruence modulo zero is equality.
Proof. First prove the one-step assertion for a positive divisor . If , replacing by changes its quotient by , a multiple of . For necessity, write with . Comparing the congruent inputs gives . If , compare the congruent inputs and . Their quotients are and , which would give , a contradiction. Thus and . Apply this with ; repeated Euclidean division by equals division by . If every divides a nonzero , then for all , contradicting unbounded growth of the powers. Conversely, congruent inputs modulo zero are equal and remain equal at every depth.
For the cubic tower, every further digit removal multiplies the required input modulus by three. Forward execution keeps all future stopping observations inside one finite quotient. Descent permits future queries to depend on successively deeper memory, and the full language uses this access to implement the two stacks. The strict separation is a property of these languages; particular programs containing descent can still halt immediately, for example when their guard is constantly true.
Formalization in Lean 4
The development uses Lean 4 [4] and Mathlib [12]. Its proof architecture connects three layers: actual covering-space transport, exact analytic execution on an invariant lattice, and effective discrete computation. The final statements combine these layers for the same finite program.
Geometric states and dependent fibers
A geometric state has type , so its type records the base point . A path from to transports between these two fiber types. In Covering.lean, transport is defined by Mathlib’s IsCoveringMap.monodromy, applied to the path’s endpoint-fixed homotopy class under an explicit covering-map hypothesis. Lift existence and uniqueness identify this operation with an actual continuous lifted curve.
The dependent fiber types make endpoint compatibility a mathematical obligation. A supplied lift carries a continuity proof, its projection equation, and its specified initial value. To identify the terminal fiber element with the intended state, Lattice.segment_transport proves equality of their underlying points and uses subtype extensionality. Concatenation then yields the finite-run transport law. Thus the geometric certificate concerns actual lifts with compatible endpoints throughout the run.
Analytic execution and the grid invariant
The inductive expression type in CoverExpressions.lean has integer and real interpretations. Structural induction proves evalReal_int and joint real analyticity. The quotient and remainder identities use Euclidean integer division, including negative inputs; the factor connects normalized integers to the actual retained angular branches.
Native memory is a real vector together with a proof of membership in the embedded integer grid. Grid preservation makes the analytic return a map on this subtype. Its value is computed by the real expression interpretation; the integer witness certifies legality. The guard’s analytic indicator is proved to agree with the Boolean decision on this same grid. These correspondences give the exact optional step and then Program.evalReal_init, the complete partial-execution equality (3.8).
Complete results and effective representations
The Turing lower bound composes Mathlib’s verified stack and tape translations with the cubic compiler. Two additional bridges recover the required complete result. First, equality of all track projections determines the entire packed tape. Second, a fixed source code has a finite transition-closed control support. Restricting labels to this support produces a finite control subtype: each target label carries the membership proof supplied by transition closure. Forgetting these certificates preserves the complete configuration and execution. The pointed enumeration keeps the initial label zero, which gives the program-independent input map.
For the upper bound, primitive-recursive certificates cover signed integer arithmetic, finite expressions, guards, and transitions. Stopped iteration is then partial recursive. The state encoding explicitly uses the encoding associated with its chosen Primcodable finite-vector representation. The fixed input and total output maps have separate primitive-recursive proofs. These choices align the numerical interface with the execution semantics in Structure.continuation_characterization.
Source and verification
The Lean development is in src/Monodromy/, with root import src/Monodromy.lean. Toolchain and dependency versions are recorded in lean-toolchain, lakefile.lean, and lake-manifest.json. Appendix B gives the pinned versions and the correspondence between the paper’s statements and formal declarations. From the repository root, verification uses
lake build
lake env lean -DautoImplicit=false -DwarningAsError=true src/Audit.lean
The audit checks every exported Monodromy declaration and its transitive proof dependencies against the standard Lean axioms propext, Quot.sound, and Classical.choice.
Discussion and Conclusion
The computational role of deeper observation
The construction organizes computation around three related structures. An infinite covering fiber retains an unbounded discrete state. A finite covering observation turns selected information into analytic control. Descent changes which part of that retained state becomes available to the same finite observation. Affine writing and finite feedback complete the execution mechanism. The resulting three-coordinate calculus has exactly classical partial-recursive power, with a geometric realization of its finite runs.
The distinction between retention and access matters. An infinite state space by itself can still support only decidable stopping when a closed finite observation governs every future decision. Corollary 5.9 states this obstruction without assuming a particular geometry. In the present calculus, Proposition 5.10 measures exactly how descent escapes a fixed residue observation, and Theorem 5.8 converts that distinction into a separation of computational power.
The covering groups needed here are elementary: the logarithmic memory has integer translations, and the finite power observations have cyclic monodromy. Conditional execution is supplied by state-dependent analytic feedback. Thus this realization already arises from abelian covering actions; its computational organization lies in how retained branches, finite queries, and descent interact. Transport composition and homotopy invariance govern the paths that implement that organization.
Physical realization and path deformation
Homotopy invariance gives exact protection of branch transport against endpoint-fixed path deformations within the covering base. A physical realization would require a quantitative account of the perturbations that preserve this class, together with reliable branch observation, internal selection, and path generation. The robustness techniques of [7, 8] provide a starting point for studying the analytic selectors and returns away from the exact integer lattice.
Optical phase transport and fluid circulation suggest possible media in which to investigate winding-based memory. A corresponding device model would have to specify its physical state space and covering, construct the read and write operations, and bound their precision, energy, and execution costs. The discrete-return semantics identifies the mathematical operations that such an implementation would need to realize.
Open problems
A broader mathematical question is which effective continuation systems admit an analogous combination of retained state, separating finite observations, and recursive access to deeper structure. The present finite calculus gives one complete instance and a general finite-observation obstruction. It provides a precise starting point for studying that question across other analytic coverings.
Within the calculus, further sublanguage classifications can ask which restrictions admit a finite closed stopping observation and which extensions escape it. Quantitative questions concern the size of compiled query trees, the growth of memory codes, and the cost of realizing a return. Reusable formal interfaces for covering transport, analytic observations, and complete-execution refinement could support these investigations across different geometric models.
The present model joins persistent branches, finite analytic control, and access to deeper memory in one finite syntax. Its execution has both an exact partial-recursive characterization and an actual path-lifting realization. The Forward separation makes the contribution of deeper access visible as a theorem about computational power.
AI contributions and author responsibility. Generative AI (OpenAI ChatGPT and Codex, including collaborating AI agents) contributed substantially to the conception and mathematical development of this work, including research ideation, theoretical constructions, conjectures, proofs, Lean formalization, implementation, and manuscript preparation.
The human author directed the research, determined its scope and principles, established its aesthetic aims and the use of Lean as the native research environment, critically evaluated the results, and assumes full responsibility for the work.
The formalization and source code accompany this manuscript for independent verification.
The fixed input and output maps
This appendix specifies the interface of (27) without reference to the function being computed. It is inherited from the fixed alphabet of Mathlib’s partial-recursive compiler, and the Monodromy block encoding is applied only after that alphabet is fixed.
Let be four track names and four stack symbols. Use the finite tape alphabet
The Boolean marks a stack bottom, and each track stores either a symbol or an empty entry. The blank is the false marker with every entry empty. Fix an enumeration sending this blank to zero. This same enumeration is used for every program, input, and output. In Lean it is obtained from a fixed finite enumeration by swapping the blank’s index with zero.
For , let be the letter with bottom marker false, symbol on the main track, and empty other tracks. Let be the same letter with marker true. Write for the ordinary binary digits of in most-significant-first order, with . The input word is
interpreting each binary digit as its corresponding stack symbol. This is exactly the compiler’s packed word for the singleton numeric list : the stack’s little-endian bits and final separator are reversed when packed into the tape. Its first separator column carries the bottom marker. The native input is
The current symbol occupies the first coordinate because the initial control label is zero in (23).
Define a total block decoder . Starting from , take exactly iterations of this rule: look up the residue modulo in the finite list ; if it names , replace the state by ; otherwise replace it by . Finally reverse the accumulated word. Zero has no matching letter, so it remains stationary. The inequalities give
The second inequality proves that the chosen iteration budget always suffices for valid encodings. The bounded definition gives a total primitive-recursive map on every natural input.
For , form . Fold this word from left to right, starting with zero. A main-track replaces the accumulator by ; every other symbol leaves it unchanged. Call the resulting number . The marker and the other three tracks are ignored. Thus is total, independent of the source table, and reads the canonical final right half-tape as its binary value. Since appended blank symbols leave the fold unchanged, the readout is well-defined on blank-extended half-tapes. The compiler leaves the separator in the current cell and the numeric bits in the right half-tape at termination, so reading only coordinate two recovers the entire numeric answer.
All constants and finite tables here are fixed. In particular, the input and decoder introduce no source-dependent preprocessing or readout. The formal certificates of primitive recursiveness use a fixed primitive coding of the finite alphabet and of integer vectors.
Proof correspondence and reproducibility
The project pins Lean to leanprover/lean4:v4.35.0 and Mathlib to commit 56a005855ea17e0b0958f73ec801ae140b0a1679.
Definitions and proofs are in src/Monodromy/. The following table lists the principal bridges; names are relative to the Monodromy namespace.
| Mathematical statement | Formal entry points |
| Covering transport | Transport.transport_trans, Transport.transport_homotopic |
| Logarithmic branches | Logarithm.transport_turn |
| Regular-root selectors | Choice.kernel_fiber, Choice.analyticAt_kernel, Choice.kernel_comp |
| Lemma 3.1 | CoverExpressions.evalReal_int, CoverExpressions.analyticAt_evalReal, CoverExpressions.Guard.evalReal_int, CoverExpressions.Guard.eval_gate |
| Complete native equality | CoverExpressions.Program.evalReal_init |
| Proposition 3.3 | CoverExpressions.Program.run_transport, CoverExpressions.query_transport, CoverExpressions.query_integer |
| Finite ternary tables | CoverExpressions.Ternary.eval_selectPower, CoverExpressions.Ternary.eval_quotientPower |
| Block word encoding | BinaryBlocks.encode_cons, BinaryBlocks.encode_injective, BinaryBlocks.decode_encode |
| Lemma 4.1 | CoverCompiler.stepInt_code, CoverCompiler.code_injective |
| Theorem 4.2 | TwoStacks.decode_surjective, TwoStacks.eval_decode, FiniteRenaming.eval_configuration, CoverCompiler.evalInt_code, CoverCompiler.advance_iterate_realize, CoverCompiler.run_transport; see also Universality.every_finite_machine for the direct radix realization |
| Classical compiler bridge | FormalCompilation.every_partrec, FormalCompilation.eval1, FormalCompilation.eval0, NativeLowerBound.every_partrec |
| Lemma 5.1 | NativeIO.primrec_input, NativeIO.primrec_output, NativeIO.output_represents |
| Lemma 5.3 | IntegerPrimrec.add, CoverExpressions.Program.primrec_stepInt, CoverExpressions.Program.partrec_evalInt |
| Theorem 5.6 | Structure.continuation_characterization, Structure.analytic_continuation_realization, Structure.computes_iff |
| Lemma 5.7 | CoverExpressions.Program.forward_supported, CoverExpressions.Program.forward_finite_observation |
| Theorem 5.8 | CoverExpressions.Program.forward_halting_bound, ForwardBoundary.primrec_halting, Structure.descent_strictly_extends |
| Corollary 5.9 | Structure.closed_observation_barrier |
Table 3.
| Mathematical statement | Formal entry points |
| Proposition 5.10 | Resolution.iterate_tail_degree_iff, Resolution.all_depths_iff |
Table 1.
The formal syntax allows any positive query degree; the predicate UsesRadix3 selects exactly the cubic expressions of this paper. Its constructors use parameter 2 to specify degree . The formal definition Structure.Computes uses the result graph of native evalReal directly; computes_iff proves its equivalence with the complete partial equality (5.2).
The verification commands and axiom audit are given in § 6. The main equivalence is an existence theorem for a finite realizing program for each partial recursive function; its proof uses finite enumerations and finite-support restrictions. This is the formal compilation interface used in the mathematical results above.
References
References
- [1]Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society (New Series), 21(1):1–46, 1989. doi: 10.1090/S0273-0979-1989-15750-9. URL https://profshub.github.io/articles/1989-On_a_theory_of_computation_and_complexity_over_the_real_numbers.pdf.DOI
- [2]Mario Carneiro. Formalizing computability theory via partial recursive functions. In John Harrison, John O’Leary, and Andrew Tolmach, editors, 10th International Conference on Interactive Theorem Proving (ITP 2019), volume 141 of Leibniz International Proceedings in Informatics, pages 12:1–12:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPIcs.ITP.2019.12. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.12.DOI
- [3]Mario Carneiro and The mathlib Community. Modelling partial recursive functions using Turing machines. mathlib4 computability source, 2020. URL https://github.com/leanprover-community/mathlib4/blob/56a005855ea17e0b0958f73ec801ae140b0a1679/Mathlib/Computability/TuringMachine/ToPartrec.lean. Pinned source and imported machine translations; revision specified in Appendix B.
- [4]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In André Platzer and Geoff Sutcliffe, editors, Automated Deduction – CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer, 2021. doi: 10.1007/978-3-030-79876-5_37. URL https://lean-lang.org/papers/lean4.pdf.DOI
- [5]Michael S. Floater and Tom Lyche. Two chain rules for divided differences and Faà di Bruno’s formula. Mathematics of Computation, 76(258):867–877, 2007. doi: 10.1090/S0025-5718-06-01916-8.DOI
- [6]Otto Forster. Lectures on Riemann Surfaces, volume 81 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1981. doi: 10.1007/978-1-4612-5961-9. URL https://link.springer.com/book/10.1007/978-1-4612-5961-9. Translated by Bruce Gilligan.DOI
- [7]Daniel S. Graça and Ning Zhong. Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machines. Computability, 12(2):117–144, 2023. doi: 10.3233/COM-210381. URL https://arxiv.org/abs/2109.15073.
- [8]Daniel S. Graça, Manuel L. Campagnolo, and Jorge Buescu. Robust simulations of Turing machines with analytic maps and flows. In S. Barry Cooper, Benedikt Löwe, and Leen Torenvliet, editors, New Computational Paradigms, volume 3526 of Lecture Notes in Computer Science, pages 169–179. Springer, 2005. doi: 10.1007/11494645_21. URL https://sqigmath.tecnico.ulisboa.pt/pub/GracaDS/05-GCB-stable.pdf.DOI
- [9]Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. ISBN 978-0-521-79540-1. URL https://pi.math.cornell.edu/~hatcher/AT/ATpage.html.
- [10]Pascal Koiran and Christopher Moore. Closed-form analytic maps in one and two dimensions can simulate universal Turing machines. Theoretical Computer Science, 210 (1):217–223, 1999. doi: 10.1016/S0304-3975(98)00117-0. URL https://sites.santafe.edu/~moore/pubs/elem.html.DOI
- [11]Claude E. Shannon. Mathematical theory of the differential analyzer. Journal of Mathematics and Physics, 20(1–4):337–354, 1941. doi: 10.1002/sapm1941201337. URL https://onlinelibrary.wiley.com/doi/10.1002/sapm1941201337.DOI
- [12]The mathlib Community. The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 367–381. Association for Computing Machinery, 2020. doi: 10.1145/3372885.3373824. URL https://leanprover-community.github.io/papers/mathlib-paper.pdf.DOI