Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Native adjacent catalyst-bit exchange

Definition
CatalyticTreeEval_NativeAdjacentSwap

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

A five-state native binary machine exchanges two adjacent catalyst bits in three transitions, using only its finite control to retain their transient values. This interface specifies the finite code and associated contract data. Exact execution, tape frames and head bounds are proved separately.

Definition code
import Definitions.Def_CatalyticTreeEval_MachineContracts

set_option autoImplicit false

namespace CatalyticTreeEval.Contracts.NativeAdjacentSwap

open CatalyticMatching.General

/-- Exchange the current catalyst bit with its right neighbour in three native steps.
The first and second bits are saved in finite control, never on the work tape. -/
def machine : Main.Machine where
  states := 5
  start := 0
  table q _ work catalyst _ _ _ :=
    if q = 0 then
      { next := some (if catalyst == some true then 2 else 1)
        workWrite := work, catalystWrite := none
        inputMove := .stay, workMove := .stay, catalystMove := .right, emit := none }
    else if q = 1 ∨ q = 2 then
      { next := some (if catalyst == some true then 4 else 3)
        workWrite := work, catalystWrite := some (q == 2)
        inputMove := .stay, workMove := .stay, catalystMove := .left, emit := none }
    else
      { next := none, workWrite := work, catalystWrite := some (q == 4)
        inputMove := .stay, workMove := .stay, catalystMove := .stay, emit := none }

def first (c : Config machine) (a : Bool) : Config machine :=
  { c with
    state := some (if a then (2 : Fin 5) else (1 : Fin 5))
    catalystHead := c.catalystHead + 1 }

def second (c : Config machine) (a b : Bool) : Config machine :=
  { c with
    state := some (if b then (4 : Fin 5) else (3 : Fin 5))
    catalyst := c.catalyst.set (c.catalystHead + 1) a }

def finish (c : Config machine) (a b : Bool) : Config machine :=
  { c with
    state := none
    catalyst := (c.catalyst.set (c.catalystHead + 1) a).set c.catalystHead b }

def envelope (c : Config machine) : Envelope :=
  ⟨c.workHead, c.workHead + 1, c.catalystHead, c.catalystHead + 2⟩

def footprint (c : Config machine) : Footprint :=
  ⟨∅, {c.catalystHead, c.catalystHead + 1}⟩

end CatalyticTreeEval.Contracts.NativeAdjacentSwap
Source
Henzinger, Pyne and Ragavan, Catalytic Tree Evaluation from Matching Vectors, https://arxiv.org/html/2602.14320v3, Section 4.3 and Corollary 4.2, register permutation infrastructure.

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