Complete large-node execution from bounded child executions
ProvedLax263307Proofs.NativeNodeExecution.large_segmentFix a native recursive core configuration and a graph node with order and target . Assume , the node is outside the small/exhaustive case, and its fuel is . Let be the host word width, the precision denominator, the frame stride and the virtual word width. Suppose the published local numeric bounds and large-search resource data hold. Assume every eligible child at fuel has its required execution, with at most steps and time .
Starting from the phase-1 node input, the actual core machine executes a complete large-node segment, including the child calls and return protocol. If are the local step, local time and branching bounds, then
The returned answer is the recursive large-node attempt; the node protocol, saved parent frame and graph encoding are preserved as required by the execution interface. This is the inductive composition step used to prove the complete recursive execution theorem.
import Definitions.Def_EdgeSublinearMWIS_Main_NativeNodeCaseInterfaces
theorem Lax263307Proofs.NativeNodeExecution.large_segment : ∀ {n : ℕ} (D k fuel S v w childSteps childTime localSteps localTime branches : ℕ)
(cfg : Lax263307Proofs.NativeCoreMachine.Config) (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj]
(lp flow : List ℕ → List ℕ) (extent : String → ℕ) (front : List ℕ)
(eligible : Lax263307Proofs.NativeNodeProtocol.Eligible),
Lax263307Proofs.NativeNodeExecution.Bounds w D k (fuel + 1) n cfg extent →
∀
(data :
Lax263307Proofs.NativeNodeExecution.Search D k fuel S v w childSteps childTime localSteps localTime branches cfg
G lp flow extent front eligible),
Lax263307Proofs.NativeNodeProtocol.Children (2 ^ w) D fuel S v childSteps childTime cfg G extent front eligible
(Lax263307Proofs.NativeNodeExecution.child cfg lp flow D fuel G) →
¬(k ≤ Lax263307.AlgorithmParameters.cutoff cfg.a cfg.K cfg.b n D ∨ n ≤ 1) →
k ≤ n →
∀ (σ : Lax808846Proofs.Imp.Env),
Lax263307Proofs.NativeNodeProtocol.Input (2 ^ w) D (fuel + 1) S v cfg G k extent front σ →
σ.vars "machine.running" = 1 →
σ.vars "machine.phase" = 1 →
∃ (τ : Lax808846Proofs.Imp.Env) (s : ℕ) (t : ℕ),
Lax263307Proofs.NativeMachineSegment.Segment (2 ^ w)
(Lax263307Proofs.NativeCoreMachine.phases cfg) s t σ τ ∧
s ≤ localSteps + branches * childSteps ∧
t ≤ localTime + branches * childTime ∧
Lax263307Proofs.NativeRoundTrace.Stopped
(Lax263307.RecursiveAlgorithm.attempt lp flow cfg.a cfg.K cfg.b D (fuel + 1) G k) τ ∧
Lax263307Proofs.NativeOracleContext.Protocol (2 ^ w) D S v cfg extent front τ ∧
Lax263307Proofs.NativeOracleContext.RootData σ τ ∧
Lax263307Proofs.NativeNodeProtocol.GraphData G τ := by sorry