The Computational Boundary After Removing Conditional Gates
DefinitionMonodromy_ForwardBoundaryDefines 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.
-- 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
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For every natural input , hardFunction is the partial value obtained by decoding with the specified denumerable enumeration of natural partial-recursive program codes and evaluating that code at input , 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 ; a forward or backward gate adds respectively or 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 and every native program (without requiring it to be probe-free), quotientNext of row is the nonnegative Euclidean control residue modulo of the componentwise sum , rather than evaluation of that word directly at . probeFreeHalts on labels starts at their control residue and returns whether, among the first iterates of this finite quotient successor, including iterate , 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 ; row is unmarked.
Confirmed by the mission captain (proposal self-audit).