Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Native work-prefix addressing by read-only head distances

Definition
CatalyticTreeEval_NativePrefixAddress

by sragavan · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryturing-machines

Finite binary machine templates for transferring an actual input-head or catalyst-head distance to the work-head position, followed by a write to a runtime-selected dense work-prefix cell. The tables use only origin sensors and fixed control; all distances are physical head positions. The shared interface records the exact running time and source trajectories. Preparing the head distances from binary banks is a separate native call.

Definition code
import Definitions.Def_CatalyticTreeEval_NativeBankAllocation

/- Bundled addressing definition: Definitions.Def_CatalyticTreeEval_NativeHeadDrain -/
section

set_option autoImplicit false

namespace CatalyticTreeEval.Contracts.NativeHeadDrain

open CatalyticMatching.General
open NativeHeadStationary (Head position)

/-- Transfer an actual read-only head distance into the work-head position.
Each non-origin transition moves the selected head left and the work head
right. The last transition observes origin and halts. Neither a distance nor
an input-dependent address occurs in the finite control. -/
def machine (head : Head) : Main.Machine where
  states := 1
  start := 0
  table _ _ work _ io _ co :=
    let origin := match head with | .input => io | .catalyst => co
    { next := if origin then none else some 0
      workWrite := work
      catalystWrite := none
      inputMove := match head with
        | .input => if origin then .stay else .left
        | .catalyst => .stay
      workMove := if origin then .stay else .right
      catalystMove := match head with
        | .input => .stay
        | .catalyst => if origin then .stay else .left
      emit := none }

def cursor (head : Head) (c : Config (machine head))
    (remaining work : ℕ) (live : Bool) : Config (machine head) :=
  { c with
    state := if live then some (machine head).start else none
    inputHead := match head with | .input => remaining | .catalyst => c.inputHead
    catalystHead := match head with | .input => c.catalystHead | .catalyst => remaining
    workHead := work }

def envelope (head : Head) (c : Config (machine head)) : Envelope :=
  ⟨c.workHead, c.workHead + position head c + 1,
    match head with | .input => c.catalystHead | .catalyst => 0,
    c.catalystHead + 1⟩

end CatalyticTreeEval.Contracts.NativeHeadDrain
end

/- Bundled addressing definition: Definitions.Def_CatalyticTreeEval_WorkHome -/
section

set_option autoImplicit false

namespace CatalyticTreeEval.Contracts.WorkHome

open CatalyticMatching.General

/-- Return the work head to the native work origin; no remembered width or tags
are needed, so this remains valid after a scratch-bank erasure. -/
def machine : Main.Machine where
  states := 1
  start := 0
  table _ _ work _ _ origin _ :=
    { next := if origin then none else some 0
      workWrite := work
      catalystWrite := none
      inputMove := .stay
      workMove := if origin then .stay else .left
      catalystMove := .stay
      emit := none }

def cursor (c : Config machine) (head : ℕ) (live : Bool) : Config machine :=
  { c with
    state := if live then some machine.start else none
    workHead := head }

def envelope (c : Config machine) (head : ℕ) : Envelope :=
  ⟨0, head+1, c.catalystHead, c.catalystHead+1⟩

def footprint : Footprint := ⟨∅, ∅⟩

end CatalyticTreeEval.Contracts.WorkHome
end

/- Bundled addressing definition: Definitions.Def_CatalyticTreeEval_NativePrefixWrite -/
section

set_option autoImplicit false

namespace CatalyticTreeEval.Contracts.NativePrefixWrite

/-- The two real read-only heads carry the distances `p` and `G-p` before
entry. This fixed finite machine seeks the actual work origin, drains the
input head to reach `p`, writes the finite pending bit, then drains the
catalyst head to return to `G`. Setting up those distances is a separate,
charged native routine; this code never reads an integer from a host oracle. -/
def machine (bit : Bool) : Main.Machine :=
  Sequential.machine WorkHome.machine
    (Sequential.machine (NativeHeadDrain.machine .input)
      (Sequential.machine (NativeLiteral.machine .stay 0 (some bit))
        (NativeHeadDrain.machine .catalyst)))

def time {N : Main.Machine} (c : Config N) : ℕ :=
  (c.workHead+1) + ((c.inputHead+1) + (1+(c.catalystHead+1)))

end CatalyticTreeEval.Contracts.NativePrefixWrite
end

Source
Original native auxiliary construction for Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/abs/2602.14320, supporting the machine implementation in Section 4. Formal source: https://github.com/sragavan99/lean-prove2me-fills/tree/codex/catalytic-tree-evaluation/Solutions/CatalyticTreeEvaluation. This helper and its explicit transition tables are new formalisation infrastructure, not a separately numbered assertion in the paper.

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