Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One Fixed Effective Numeric Interface for Native Programs

Definition
Monodromy_NativeIO

by Xiaoyang Liu · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycovering-spacesmonodromy-computation

Defines source-independent integer input labels and a total natural-number output readout. Inputs use a fixed finite tape alphabet and prime-three tape coding; outputs extract the bounded prime-three exponent of one memory label and decode its tape symbols. A finite entry prefix connects this interface to the native Turing compiler and yields complete numeric-graph correctness.

Definition code
-- Generated by Lean-fact skeleton subtraction; original source is frozen in imports/monodromy/source.
module
public import Definitions.Def_Monodromy_CanonicalIO
public import Definitions.Def_Monodromy_Effectiveness
public import Lean.Elab.Tactic.Omega
public import Mathlib.Analysis.Analytic.Constructions
public import Mathlib.Analysis.Analytic.IsolatedZeros
public import Mathlib.Analysis.Analytic.Linear
public import Mathlib.Analysis.Calculus.DSlope
public import Mathlib.Analysis.Calculus.Deriv.Add
public import Mathlib.Analysis.Calculus.Deriv.Comp
public import Mathlib.Analysis.Calculus.Deriv.Mul
public import Mathlib.Analysis.Calculus.Deriv.Pow
public import Mathlib.Analysis.Complex.Basic
public import Mathlib.Analysis.Complex.CoveringMap
public import Mathlib.Analysis.Real.Pi.Bounds
public import Mathlib.Analysis.SpecialFunctions.Complex.Analytic
public import Mathlib.Analysis.SpecialFunctions.Complex.Circle
public import Mathlib.Analysis.SpecialFunctions.Trigonometric.Deriv
public import Mathlib.Analysis.SpecialFunctions.Trigonometric.Sinc
public import Mathlib.Computability.PartrecCode
public import Mathlib.Computability.Primrec.Basic
public import Mathlib.Computability.Primrec.List
public import Mathlib.Computability.StateTransition
public import Mathlib.Computability.TuringMachine.PostTuringMachine
public import Mathlib.Computability.TuringMachine.ToPartrec
public import Mathlib.Data.Fin.Basic
public import Mathlib.Data.Fintype.Card
public import Mathlib.Data.Fintype.EquivFin
public import Mathlib.Data.Fintype.Sets
public import Mathlib.Data.Int.ModEq
public import Mathlib.Data.Nat.Digits.Lemmas
public import Mathlib.Data.Nat.Factorization.Basic
public import Mathlib.Logic.Equiv.Fin.Basic
public import Mathlib.Logic.Equiv.Fin.Rotate
public import Mathlib.Logic.Function.Basic
public import Mathlib.Logic.Function.Conjugate
public import Mathlib.RingTheory.RootsOfUnity.Complex
public import Mathlib.Tactic.FieldSimp
public import Mathlib.Tactic.FinCases
public import Mathlib.Tactic.FunProp
public import Mathlib.Tactic.Linarith
public import Mathlib.Tactic.Ring
public import Mathlib.Topology.Homotopy.Lifting

@[expose] public section


/-!
# A fixed numeric interface

One primitive-recursive preparation and readout serve every finite native
program. A static prefix supplies the initial head symbol to the compiled
Turing table. Complete results are obtained by actual covering-space lifts;
the numeric readout recovers the right tape from its prime-three exponent.
-/

@[expose] public section

noncomputable section

namespace Monodromy.NativeInterface

open Turing CoupledContinuation

abbrev Alphabet := CanonicalIO.Alphabet
abbrev letters : ℕ := Fintype.card Alphabet

def word (input : ℕ) : List (Fin letters) :=
  (FormalCompilation.tapeData [input]).map (FiniteRenaming.toFin Alphabet)

def rightCode (input : ℕ) : ℕ := TapeCode.Readout.wordCode letters (word input).tail

/-- This preparation uses only the numeric argument and the fixed tape alphabet. -/
def inputLabels (input : ℕ) : Labels :=
  ((Int.ofNat (3 ^ rightCode input), 0), 3 * ((word input).headI.val : ℤ))

def read (letter : Fin letters) (value : ℕ) : ℕ :=
  CanonicalIO.readSymbol value (FiniteRenaming.fromFin Alphabet letter)





/-- The total output map ignores every control address and the workspace counter. -/
def outputLabels (labels : Labels) : ℕ :=
  TapeCode.Readout.decode read (PrimeReadout.exponent 3 labels.1.1.toNat)











variable (source : ToPartrec.Code)

abbrev FiniteControl : Type := (FormalCompilation.finiteSupport source).Control
abbrev controls : ℕ := Fintype.card (FiniteControl source)

def table : TM0.Machine (Fin letters) (Fin (controls source)) :=
  FiniteRenaming.machine (FormalCompilation.finiteSupport source).restrict

abbrev bodySize : ℕ := Counter.Compression.size
  (NativeTuring.source3 letters (controls source) (table source))

def body : Counter.Program 2 (bodySize source) :=
  NativeTuring.source2 letters (controls source) (table source)

def entries (letter : Fin letters) : Fin (bodySize source) :=
  Counter.Compression.dispatch
    (NativeTuring.source3 letters (controls source) (table source))
    (Counter.TuringCompiler.dispatch letters (controls source) (0, letter))

def counterProgram : Counter.Program 2 (letters + bodySize source) :=
  Counter.EntryDispatch.program (body source) (entries source)

instance prefix_nonempty : NeZero (letters + bodySize source) := by
  have positive : 0 < letters := Fintype.card_pos
  exact ⟨by omega⟩

/-- The only added source rows are one static entry jump for each input-head letter. -/
def program : CoupledContinuation.Program ((letters + bodySize source) * 3) :=
  CounterContinuation.compile (counterProgram source)

def initial (input : ℕ) : Counter.Configuration 2 (letters + bodySize source) :=
  Counter.EntryDispatch.entryState (word input).headI ![3 ^ rightCode input, 0]








/-- Integer labels describe the native encoding of an ordinary two-counter state. -/
def counterLabels {m : ℕ} (state : Counter.Configuration 2 m) : Labels :=
  (((state.counters 0 : ℤ), (state.counters 1 : ℤ)), CounterContinuation.label state.pc 0)



def resultLabels (state : TM0.Cfg (Fin letters) (Fin (controls source))) : Labels :=
  counterLabels (Counter.mapConfiguration (Fin.natAdd letters)
    (Counter.Compression.encode
      (NativeTuring.source3 letters (controls source) (table source))
      (Counter.TuringCompiler.encode letters (controls source) state)))













def rawOutput (state : TM0.Cfg Alphabet (FormalCompilation.Control0 source)) : ℕ :=
  CanonicalIO.decodeTape state.Tape.right















end Monodromy.NativeInterface
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. The remote Git base is incomplete and is not asserted to contain these declarations. src/Monodromy/NativeIO.lean (file SHA-256 f357e5900e9519e1b4c8b1093625f0b20cb261741f46157a662a7738b2f4a25d): Monodromy.NativeInterface.Alphabet at L23-L23 [UTF-8 538:577]. Monodromy.NativeInterface.letters at L24-L24 [UTF-8 578:623]. Monodromy.NativeInterface.word at L26-L27 [UTF-8 625:746]. Monodromy.NativeInterface.rightCode at L29-L29 [UTF-8 748:836]. Monodromy.NativeInterface.inputLabels at L31-L33 [UTF-8 838:1040]. Monodromy.NativeInterface.read at L35-L36 [UTF-8 1042:1168]. Monodromy.NativeInterface.outputLabels at L49-L51 [UTF-8 1714:1916]. Monodromy.NativeInterface.FiniteControl at L80-L80 [UTF-8 3231:3310]. Monodromy.NativeInterface.controls at L81-L81 [UTF-8 3311:3371]. Monodromy.NativeInterface.table at L83-L84 [UTF-8 3373:3512]. Monodromy.NativeInterface.bodySize at L86-L87 [UTF-8 3514:3629]. Monodromy.NativeInterface.body at L89-L90 [UTF-8 3631:3744]. Monodromy.NativeInterface.entries at L92-L95 [UTF-8 3746:3982]. Monodromy.NativeInterface.counterProgram at L97-L98 [UTF-8 3984:4116]. Monodromy.NativeInterface.prefix_nonempty at L100-L102 [UTF-8 4118:4258]. Monodromy.NativeInterface.program at L104-L106 [UTF-8 4260:4480]. Monodromy.NativeInterface.initial at L108-L109 [UTF-8 4482:4644]. Monodromy.NativeInterface.counterLabels at L145-L147 [UTF-8 6560:6815]. Monodromy.NativeInterface.resultLabels at L152-L156 [UTF-8 6973:7294]. Monodromy.NativeInterface.rawOutput at L224-L225 [UTF-8 10516:10643].
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (independent agent)

Write τ=2πi\tau=2\pi iτ=2πi. The memory space M\mathcal MM consists of triples (zL,zR,w)∈(C∗)2×C(z_L,z_R,w)\in(\mathbb C^*)^2\times\mathbb C(zL​,zR​,w)∈(C∗)2×C with ezL=ezR=ee^{z_L}=e^{z_R}=eezL​=ezR​=e and ew=zLzRe^w=z_Lz_Rew=zL​zR​; the integer-labelled point Φ(l,r,c)\Phi(l,r,c)Φ(l,r,c) is (1+τl,1+τr,log⁡(1+τl)+log⁡(1+τr)+τc)(1+\tau l,1+\tau r,\log(1+\tau l)+\log(1+\tau r)+\tau c)(1+τl,1+τr,log(1+τl)+log(1+τr)+τc) with principal complex logarithms. The fixed numeric interface uses the four symbols bit0,bit1,cons,consL\mathrm{bit0},\mathrm{bit1},\mathrm{cons},\mathrm{cons}_{L}bit0,bit1,cons,consL​ and four tracks main, reverse, auxiliary and stack; its alphabet is a Boolean marker paired with an optional symbol on each track, blank meaning false marker and all tracks empty. To encode a list of naturals, encode each number in binary least-significant-bit first (zero as an empty bit list), append cons\mathrm{cons}cons after each number, reverse the resulting symbol list, put its symbols on the main track alone, and set the first letter's marker true (an empty list gives one marked blank). Choose the specified finite alphabet bijection to {0,…,A−1}\{0,\ldots,A-1\}{0,…,A−1} taking blank to 000, where AAA is its cardinality, and let W(n)W(n)W(n) be this numeric word for the singleton list [n][n][n]. Put r(n)=∑i(W(n).tail)i(A+1)ir(n)=\sum_i(W(n).\mathrm{tail})_i(A+1)^ir(n)=∑i​(W(n).tail)i​(A+1)i and in(n)=(3r(n),0,3 W(n).head)∈Z3\mathrm{in}(n)=(3^{r(n)},0,3\,W(n).\mathrm{head})\in\mathbb Z^3in(n)=(3r(n),0,3W(n).head)∈Z3, using a default-zero head for an empty word. To read an alphabet letter from an accumulator vvv, use 2v2v2v for main-track bit0\mathrm{bit0}bit0, 2v+12v+12v+1 for main-track bit1\mathrm{bit1}bit1, and vvv otherwise, ignoring the marker and other tracks. For any integer label triple (l,r,c)(l,r,c)(l,r,c), let N=max⁡(l,0)N=\max(l,0)N=max(l,0) and kkk be the greatest j≤Nj\le Nj≤N with 3j∣N3^j\mid N3j∣N (so k=0k=0k=0 if N=0N=0N=0). The output out(l,r,c)\mathrm{out}(l,r,c)out(l,r,c) starts with (k,0)(k,0)(k,0) and performs exactly kkk iterations of taking the first component modulo A+1A+1A+1, dividing that component by A+1A+1A+1, and applying the corresponding letter-read operation to the accumulator; the unused residue AAA is interpreted as blank 000, and the final accumulator is the output. Thus this total readout ignores the right and control labels, and negative left labels give output 000. This bundle fixes that alphabet, its cardinality AAA, the word WWW, its tail code, preparation labels, finite-letter reader, and output labels as total maps independent of a source program. For each code sss in the specified list-function partial-recursive language, its compiled Post-Turing machine has a finite closed control support; restrict to that subtype and rename alphabet and controls by finite bijections taking defaults to 000, obtaining a table with AAA letters and QsQ_sQs​ controls. Let Cs3C^3_sCs3​ be its three-counter Turing compilation and Cs2C^2_sCs2​ its ordinary two-counter prime compression, with body size msm_sms​. For each input-head letter j<Aj<Aj<A, the entry address is the ordinary-compression dispatch of the three-counter (initial-control 000,head jjj) dispatch. The counterProgram prepends AAA rows to Cs2C^2_sCs2​, one at each letter address, and each such row tests the second counter and, if it is nonzero, decrements it by one, while sending either branch to that body's shifted entry address; body addresses are shifted by AAA. A nonzero-size instance is supplied for A+msA+m_sA+ms​. The native program is the three-phase counter-to-native compilation, of degree 3(A+ms)3(A+m_s)3(A+ms​), and the initial ordinary two-counter configuration is the prefix row W(n).headW(n).\mathrm{head}W(n).head with values (3r(n),0)(3^{r(n)},0)(3r(n),0). For any natural mmm and any ordinary two-counter configuration with address p<mp<mp<m and values (u,v)(u,v)(u,v), counterLabels is (u,v,3p)(u,v,3p)(u,v,3p) with integer casts, including all natural counter values; if m=0m=0m=0 there is no such configuration. resultLabels of a configuration of the renamed finite Post-Turing machine applies its three-counter encoding, then its ordinary two-counter encoding, shifts its address by AAA, and applies counterLabels. The three-counter tape codes use base A+1A+1A+1, and the ordinary compression encodes them using primes 2,3,52,3,52,3,5 with workspace zero. rawOutput of a configuration of the unrestricted compiled machine applies the canonical main-track bit-reading fold to its right half-tape modulo trailing blanks. These interfaces include every natural input, every integer label triple for total output, and arbitrary configurations of the specified machine types; their definitions do not themselves assert that resultLabels are reached by execution.

Human review
  • Endorsed by marwahaha · Nov 6, 2026

  • Endorsed by Xiaoyang Liu · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me