The Hard Function Is Not Realizable Without Conditional Gates
OpenMonodromy.Structure.no_probeFree_hardFunctioncomputabilitycovering-spacesmonodromy-computation
The standard numeric presentation of the halting problem, namely the partial function where is the -th partial-recursive code, cannot be realized under the fixed numeric interface by any positive-degree native program whose table words contain neither the left nor the right zero-conditional gate, in either direction. Arbitrary finite routing, stopping bits, and the remaining signed gates are allowed.
This is the probe-free lower-bound component of the strict extension theorem for the full native continuation language.
Formalization Note. The function is Monodromy.ForwardBoundary.hardFunction, and realizability is Monodromy.Structure.ProbeFreeRealizable with its fixed input and output labels.
Preamble
import Definitions.Def_Monodromy_Structure open Monodromy open Monodromy.Structure open CoupledContinuation NativeInterface
Formal statement
theorem Monodromy.Structure.no_probeFree_hardFunction :
¬ ProbeFreeRealizable ForwardBoundary.hardFunction := by sorry
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. src/Monodromy/Structure.lean; original proof dependency Monodromy.Structure.no_probeFree_hardFunction of conditional_gates_strictly_extend at L107-L113.