Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The Computational Boundary After Removing Conditional Gates

Definition
Monodromy_ForwardBoundary

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

computabilitycovering-spacesmonodromy-computation

Defines the gate, word and program restriction excluding both zero-conditional gates with either sign. Develops translation semantics for restricted words, a finite closed control quotient and primitive-recursive stopping tests. Supplies a partial-recursive halting-problem function with undecidable domain, and a native zero test separating specified prepared-input termination domains.

Definition code
-- Generated by Lean-fact skeleton subtraction; original source is frozen in imports/monodromy/source.
module
public import Definitions.Def_Monodromy_Effectiveness
public import Definitions.Def_Monodromy_Observation
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.Halting
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.Data.Fin.Basic
public import Mathlib.Data.Fintype.Card
public import Mathlib.Data.Int.ModEq
public import Mathlib.Data.Nat.Digits.Lemmas
public import Mathlib.Data.Set.Finite.Basic
public import Mathlib.Logic.Equiv.Fin.Rotate
public import Mathlib.Logic.Function.Conjugate
public import Mathlib.RingTheory.RootsOfUnity.Complex
public import Mathlib.Tactic.FieldSimp
public import Mathlib.Tactic.FunProp
public import Mathlib.Tactic.Linarith
public import Mathlib.Tactic.Ring
public import Mathlib.Topology.Homotopy.Lifting

@[expose] public section


/-!
# The computational boundary of fixed observations

Removing the two zero-conditional loops leaves
a finite control quotient with a bounded primitive-recursive halting test.
One actual conditional loop yields a strictly different halting domain under
the same fixed input representation.
-/

@[expose] public section

namespace Monodromy.ForwardBoundary



/-- A standard numeric presentation of the halting problem. -/
def hardFunction (input : ℕ) : Part ℕ :=
  Nat.Partrec.Code.eval (Denumerable.ofNat Nat.Partrec.Code input) 0





end Monodromy.ForwardBoundary

namespace Monodromy.CoupledContinuation

/-- Remove precisely the two zero-conditional monodromy gates; finite control routing remains. -/
def Gate.ProbeFree : Gate → Prop
  | .zeroLeft | .zeroRight => False
  | .left | .right | .control => True

def Word.ProbeFree : Word → Prop
  | [] => True
  | (gate, _) :: rest => gate.ProbeFree ∧ Word.ProbeFree rest







end Monodromy.CoupledContinuation

namespace Monodromy.CoupledContinuation.Program

variable {degree : ℕ} [NeZero degree]

def ProbeFree (program : Program degree) : Prop := ∀ index, (program.table index).ProbeFree



/-- Each table entry contributes a fixed control displacement to this finite quotient. -/
def quotientNext (program : Program degree) (index : Fin degree) : Fin degree :=
  indexInt degree (((0, 0), (index.val : ℤ)) + Word.evalInt (program.table index) 0)







/-- A finite bounded search decides stopping for this controlled deletion of the native language. -/
def probeFreeHalts (program : Program degree) (labels : Labels) : Bool :=
  Observation.finiteHalts program.quotientNext program.stop (indexInt degree labels)







end Monodromy.CoupledContinuation.Program

namespace Monodromy.CoupledContinuation.Program

variable {degree : ℕ} [NeZero degree]





end Monodromy.CoupledContinuation.Program

namespace Monodromy.CoupledContinuation.Program

variable {degree : ℕ} [NeZero degree]



end Monodromy.CoupledContinuation.Program

namespace Monodromy.CoupledContinuation

/-- One native zero-conditional loop; only its marked finite control root stops execution. -/
def zeroTest : Program 2 where
  table := fun _ => Word.atom .zeroLeft false
  stop := fun index => index.val == 1





end Monodromy.CoupledContinuation
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/ForwardBoundary.lean (file SHA-256 79994010f524b607d5f4d56631e4490998ab2e44fa455569a55df12bc89c47b2): Monodromy.ForwardBoundary.hardFunction at L27-L29 [UTF-8 970:1146]. Monodromy.CoupledContinuation.Gate.ProbeFree at L45-L48 [UTF-8 1708:1914]. Monodromy.CoupledContinuation.Word.ProbeFree at L50-L52 [UTF-8 1916:2029]. Monodromy.CoupledContinuation.Program.ProbeFree at L93-L93 [UTF-8 4061:4154]. Monodromy.CoupledContinuation.Program.quotientNext at L104-L106 [UTF-8 4588:4845]. Monodromy.CoupledContinuation.Program.probeFreeHalts at L135-L137 [UTF-8 6515:6774]. Monodromy.CoupledContinuation.zeroTest at L194-L197 [UTF-8 9639:9847].
Read-back

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

For every natural input nnn, hardFunction is the partial value obtained by decoding nnn with the specified denumerable enumeration of natural partial-recursive program codes and evaluating that code at input 000, with undefinedness inherited from that evaluation. For the five native gate constructors, ProbeFree is false precisely on the left and right zero probes and true on the left and right shifts and control turn; a word is probe-free exactly when all its gates are, ignoring reversal flags, with the empty word probe-free; a program is probe-free exactly when every row word is. Native integer labels are (l,r,c)∈Z3(l,r,c)\in\mathbb Z^3(l,r,c)∈Z3; a forward or backward gate adds respectively +1+1+1 or −1-1−1 to its left/right coordinate or to control, with a probe's control update conditional on its chosen lower coordinate being zero, and word evaluation folds these updates in list order. For every positive natural degree ddd and every native program PPP (without requiring it to be probe-free), quotientNext of row j<dj<dj<d is the nonnegative Euclidean control residue modulo ddd of the componentwise sum (0,0,j)+evalWord(Pj,(0,0,0))(0,0,j)+\mathrm{evalWord}(P_j,(0,0,0))(0,0,j)+evalWord(Pj​,(0,0,0)), rather than evaluation of that word directly at (0,0,j)(0,0,j)(0,0,j). probeFreeHalts on labels starts at their control residue and returns whether, among the first ddd iterates of this finite quotient successor, including iterate 000, any row's Boolean stop flag is true. Both of these functions are defined for every positive-degree word table, irrespective of its ProbeFree predicate. Finally zeroTest is the degree-two program with the one-letter forward left-zero-probe word at both rows and a true stop flag exactly at row 111; row 000 is unmarked.

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