Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorValidityStack

Definition
PricingWithTips3DM_3cfd233f8783d3b63f3bc36b

by qmaai2907271020 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypricing-with-tipsthree-dimensional-matching

A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.

Definition code
import Definitions.Def_PricingWithTips3DM_87933a2fffb91ad12b2d5206
import Definitions.Def_PricingWithTips3DM_166c06c474f89905830560ba
import Definitions.Def_PricingWithTips3DM_6a1518192c1a84a68b127ace
import Definitions.Def_PricingWithTips3DM_83a098e25b569613edf49c77
import Definitions.Def_PricingWithTips3DM_cd70d4a11c417526c08b1da3
import Definitions.Def_PricingWithTips3DM_9c8d8fdf86a8ea3ddcb42e89
import Definitions.Def_PricingWithTips3DM_9222df11121649b938e4dcc6
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Arithmetic stack-cell equality in the validity generator

This module fixes one machine stack and one bounded cell, closes every wire
index used by its canonicality constraint, and instantiates the contextual
five-gate Boolean-equality serializer at those indices.
-/

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder
open StateTransition

noncomputable section

/-- Ordinal of a fixed machine stack in the canonical finite stack order. -/
noncomputable def arithmeticStackOrdinal
    (tm : _root_.Turing.FinTM2) (k : tm.K) : Nat := by
  letI : Fintype tm.K := tm.kFin
  exact (Fintype.equivFin tm.K k).val

/-- Number of stacks of the fixed machine, using its bundled finite instance. -/
def arithmeticStackCount (tm : _root_.Turing.FinTM2) : Nat :=
  @Fintype.card tm.K tm.kFin

/-- Canonical fixed-machine stack enumeration used by validity traces. -/
noncomputable def arithmeticStackEquiv (tm : _root_.Turing.FinTM2) :
    tm.K ≃ Fin (arithmeticStackCount tm) :=
  @Fintype.equivFin tm.K tm.kFin

/-- Enumerating a stack and then taking its arithmetic ordinal returns the
original finite index. -/
@[simp] theorem arithmeticStackOrdinal_equiv_symm
    (tm : _root_.Turing.FinTM2) (j : Fin (arithmeticStackCount tm)) :
    arithmeticStackOrdinal tm ((arithmeticStackEquiv tm).symm j) = j.val := by
  change ((@Fintype.equivFin tm.K tm.kFin)
    ((@Fintype.equivFin tm.K tm.kFin).symm j)).val = j.val
  exact congrArg Fin.val
    ((@Fintype.equivFin tm.K tm.kFin).apply_symm_apply j)

/-- First fresh gate index of the complete stack-validity family. -/
noncomputable def arithmeticStackValidityStart
    (tm : _root_.Turing.FinTM2) (H start : Nat) : Nat :=
  arithmeticHaltedMatchStart tm H start + 5

/-- First fresh gate index of one fixed stack's active-mask block. -/
noncomputable def arithmeticStackBlockStart
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K) : Nat :=
  arithmeticStackValidityStart tm H start +
    (H + 1 + 6 * H) * arithmeticStackOrdinal tm k

/-- First stack-height source wire scanned by one active-mask suffix OR. -/
def arithmeticStackMaskWireBase
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K) : Nat :=
  rowBase + (1 + (labelCount tm + 1) + stateCount tm +
    cfgStackBitOffset tm H k + 1)

/-- Closed output wire of the suffix-OR active mask at one cell. -/
noncomputable def arithmeticStackMaskOutputWire
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) : Nat :=
  arithmeticStackBlockStart tm H start k + H - i.val

/-- First fresh gate of the per-cell family following one stack's mask. -/
noncomputable def arithmeticStackCellTraceStart
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K) : Nat :=
  arithmeticStackBlockStart tm H start k + (H + 1)

/-- Output wire of the cell's leading negation of the blank bit. -/
noncomputable def arithmeticStackCellNotWire
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) : Nat :=
  arithmeticStackCellTraceStart tm H start k + 6 * i.val

/-- First fresh gate of the cell's five-gate active/nonblank equality. -/
noncomputable def arithmeticStackCellBoolEqStart
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) : Nat :=
  arithmeticStackCellNotWire tm H start k i + 1

/-- Closed row wire of the distinguished blank symbol in one stack cell. -/
def arithmeticStackBlankWire
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) : Nat :=
  rowBase + (1 + (labelCount tm + 1) + stateCount tm +
    cfgStackBitOffset tm H k + (H + 1) +
      ((reachableAlphabet tm k).card +
        ((reachableAlphabet tm k).card + 1) * i.val))

/-- Ordered stack-height sources of one semantic suffix-OR mask. -/
def arithmeticStackMaskWires
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K) :
    List CircuitBuilder.Wire :=
  List.ofFn fun i : Fin H =>
    (arithmeticCfgWires tm H rowBase).stackHeight k i.succ

/-- The semantic stack-height sources form one literal affine interval. -/
theorem arithmeticStackMaskWires_eq_range'
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K) :
    arithmeticStackMaskWires tm H rowBase k =
      List.range' (arithmeticStackMaskWireBase tm H rowBase k) H := by
  have hwires : ∀ i : Fin H,
      (arithmeticCfgWires tm H rowBase).stackHeight k i.succ =
        arithmeticStackMaskWireBase tm H rowBase k + i.val := by
    intro i
    rw [arithmeticCfgWires_stackHeight]
    simp only [arithmeticStackMaskWireBase, Fin.val_succ]
    ring
  apply List.ext_getElem
  · simp [arithmeticStackMaskWires]
  · intro i hleft hright
    have hi : i < H := by
      simpa [arithmeticStackMaskWires] using hleft
    simpa [arithmeticStackMaskWires] using hwires ⟨i, hi⟩

/-- Semantic suffix-OR trace whose outputs are the active masks of a fixed
stack. -/
def arithmeticStackMaskTrace
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    SuffixOrGateTrace (arithmeticStackMaskWires tm H rowBase k).length :=
  suffixOrGateTrace (arithmeticStackBlockStart tm H start k)
    (arithmeticStackMaskWires tm H rowBase k)

/-- The closed active-mask wire is exactly the semantic suffix-OR output. -/
theorem arithmeticStackMaskOutputWire_eq_trace
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackMaskOutputWire tm H start k i =
      (arithmeticStackMaskTrace tm H start rowBase k).outputs
        (Fin.cast (by simp [arithmeticStackMaskWires]) i) := by
  unfold arithmeticStackMaskOutputWire arithmeticStackMaskTrace
  rw [suffixOrGateTrace_output_eq]
  simp [arithmeticStackMaskWires]

/-- Explicit encoded stream of one arithmetic stack's complete active mask. -/
noncomputable def arithmeticStackMaskGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    List CircuitSym :=
  affineSuffixOrGateStream (arithmeticStackBlockStart tm H start k)
    (arithmeticStackMaskWireBase tm H rowBase k) H

/-- The affine active-mask stream is exactly the semantic suffix-OR trace. -/
theorem arithmeticStackMaskGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    arithmeticStackMaskGateStream tm H start rowBase k =
      (arithmeticStackMaskTrace tm H start rowBase k).gates.flatMap
        encodeCircuitGate := by
  unfold arithmeticStackMaskGateStream arithmeticStackMaskTrace
  rw [affineSuffixOrGateStream_eq_trace,
    ← arithmeticStackMaskWires_eq_range']

/-- Concrete contextual run for one arithmetic stack's active mask. -/
def arithmeticStackMaskRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (output : List CircuitSym) :
    EvalsToInTime (step sequentialExactlyOneRevProgram)
      (affineSuffixOrBodyCfg (arithmeticStackBlockStart tm H start k)
        (arithmeticStackMaskWireBase tm H rowBase k) H output)
      (some (haltCfg sequentialExactlyOneRevProgram
        ((arithmeticStackMaskGateStream tm H start rowBase k).reverse ++
          output)))
      (affineSuffixOrRevSteps (arithmeticStackBlockStart tm H start k)
        (arithmeticStackMaskWireBase tm H rowBase k) H) :=
  affineSuffixOrRev_runFrom _ _ _ output

/-- The arithmetic active-mask invocation inherits the affine quadratic
running-time bound. -/
theorem arithmeticStackMaskRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    affineSuffixOrRevSteps (arithmeticStackBlockStart tm H start k)
        (arithmeticStackMaskWireBase tm H rowBase k) H ≤
      25 * (arithmeticStackBlockStart tm H start k +
        arithmeticStackMaskWireBase tm H rowBase k + H + 1) ^ 2 :=
  affineSuffixOrRev_steps_le _ _ _

/-- The closed blank wire is exactly the last alphabet coordinate in the
arithmetic row bundle. -/
theorem arithmeticStackBlankWire_eq_row
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackBlankWire tm H rowBase k i =
      (arithmeticCfgWires tm H rowBase).stackCell k i
        (Fin.last (reachableAlphabet tm k).card) := by
  rw [arithmeticCfgWires_stackCell]
  simp [arithmeticStackBlankWire]

/-- Encoded leading negation of the blank bit for one fixed stack cell. -/
def arithmeticStackCellNotGateStream
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) : List CircuitSym :=
  affineNotGateStream (arithmeticStackBlankWire tm H rowBase k i)

/-- The closed source index makes the single-NOT stream exactly the semantic
leading gate of this cell-validity block. -/
theorem arithmeticStackCellNotGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackCellNotGateStream tm H rowBase k i =
      ([CircuitGate.not
        ((arithmeticCfgWires tm H rowBase).stackCell k i
          (Fin.last (reachableAlphabet tm k).card))]).flatMap
        encodeCircuitGate := by
  unfold arithmeticStackCellNotGateStream
  rw [arithmeticStackBlankWire_eq_row,
    affineNotGateStream_eq_trace]

/-- Concrete contextual run for the leading blank-bit negation. -/
def arithmeticStackCellNotRev_runFrom
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) (output : List CircuitSym) :
    EvalsToInTime (step sequentialExactlyOneRevProgram)
      (affineNotBodyCfg (arithmeticStackBlankWire tm H rowBase k i) output)
      (some (haltCfg sequentialExactlyOneRevProgram
        ((arithmeticStackCellNotGateStream tm H rowBase k i).reverse ++
          output)))
      (affineNotRevSteps (arithmeticStackBlankWire tm H rowBase k i)) :=
  affineNotRev_runFrom _ output

/-- The arithmetic cell-NOT invocation inherits the generic quadratic bound. -/
theorem arithmeticStackCellNotRev_steps_le
    (tm : _root_.Turing.FinTM2) (H rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    affineNotRevSteps (arithmeticStackBlankWire tm H rowBase k i) ≤
      10 * (arithmeticStackBlankWire tm H rowBase k i + 1) ^ 2 :=
  affineNotRev_steps_le _

/-- Encoded five-gate equality stream for one fixed stack cell.  Its left
operand is the semantic active-mask output, and its right operand is the
fresh result of the immediately preceding blank-bit negation. -/
noncomputable def arithmeticStackCellBoolEqGateStream
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) : List CircuitSym :=
  affineBoolEqGateStream (arithmeticStackCellBoolEqStart tm H start k i)
    (arithmeticStackMaskOutputWire tm H start k i)
    (arithmeticStackCellNotWire tm H start k i)

/-- The closed stream is the exact Boolean-equality subtrace used by the
semantic stack-validity construction. -/
theorem arithmeticStackCellBoolEqGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackCellBoolEqGateStream tm H start k i =
      (CircuitBuilder.boolEqGateTrace
        (arithmeticStackCellBoolEqStart tm H start k i)
        ((arithmeticStackMaskTrace tm H start rowBase k).outputs
          (Fin.cast (by simp [arithmeticStackMaskWires]) i))
        (arithmeticStackCellNotWire tm H start k i)).gates.flatMap
          encodeCircuitGate := by
  unfold arithmeticStackCellBoolEqGateStream affineBoolEqGateStream
  rw [arithmeticStackMaskOutputWire_eq_trace]

/-- Concrete contextual run for one arithmetic stack-cell equality. -/
def arithmeticStackCellBoolEqRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) (output : List CircuitSym) :
    EvalsToInTime (step sequentialExactlyOneRevProgram)
      (affineBoolEqBodyCfg (arithmeticStackCellBoolEqStart tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackCellNotWire tm H start k i) output)
      (some (haltCfg sequentialExactlyOneRevProgram
        ((arithmeticStackCellBoolEqGateStream tm H start k i).reverse ++
          output)))
      (affineBoolEqRevSteps (arithmeticStackCellBoolEqStart tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackCellNotWire tm H start k i)) :=
  affineBoolEqRev_runFrom _ _ _ output

/-- Every fixed stack-cell invocation inherits the contextual quadratic
running-time envelope. -/
theorem arithmeticStackCellBoolEqRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start : Nat) (k : tm.K)
    (i : Fin H) :
    affineBoolEqRevSteps (arithmeticStackCellBoolEqStart tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackCellNotWire tm H start k i) ≤
      100 * (arithmeticStackCellBoolEqStart tm H start k i +
        arithmeticStackMaskOutputWire tm H start k i +
        arithmeticStackCellNotWire tm H start k i + 1) ^ 2 :=
  affineBoolEqRev_steps_le _ _ _

/-- Complete encoded six-gate canonicality block of one arithmetic stack
cell: one blank-bit negation followed by active/nonblank equality. -/
noncomputable def arithmeticStackCellGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) : List CircuitSym :=
  arithmeticStackCellNotGateStream tm H rowBase k i ++
    arithmeticStackCellBoolEqGateStream tm H start k i

/-- The closed arithmetic stream is exactly the semantic six-gate cell block. -/
theorem arithmeticStackCellGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackCellGateStream tm H start rowBase k i =
      let mask := arithmeticStackMaskTrace tm H start rowBase k
      let blank := (arithmeticCfgWires tm H rowBase).stackCell k i
        (Fin.last (reachableAlphabet tm k).card)
      ([CircuitGate.not blank] ++
        (CircuitBuilder.boolEqGateTrace
          (arithmeticStackCellBoolEqStart tm H start k i)
          (mask.outputs (Fin.cast
            (by simp [arithmeticStackMaskWires]) i))
          (arithmeticStackCellNotWire tm H start k i)).gates).flatMap
            encodeCircuitGate := by
  unfold arithmeticStackCellGateStream
  rw [arithmeticStackCellNotGateStream_eq_semantic tm H rowBase k i,
    arithmeticStackCellBoolEqGateStream_eq_semantic
      tm H start rowBase k i]
  simp

/-- Exact contextual run for the complete six-gate arithmetic stack-cell
block.  Unlike the separate primitive interfaces above, this run does not halt
between the leading blank-bit negation and the following Boolean equality. -/
noncomputable def arithmeticStackCellRev_runToHaltLabel
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) (output : List CircuitSym) :
    EvalsToInTime (step sequentialExactlyOneRevProgram)
      (affineCellBodyCfg (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i) output)
      (some (sequentialExactlyOneCfg .halt none none false []
        ((arithmeticStackCellGateStream tm H start rowBase k i).reverse ++
          output) [] [] [] [] []))
      (affineCellRevCoreSteps (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i)) := by
  simpa [arithmeticStackCellGateStream,
    arithmeticStackCellNotGateStream,
    arithmeticStackCellBoolEqGateStream,
    arithmeticStackCellBoolEqStart,
    affineCellGateStream] using
      affineCellRev_runToHaltLabel
        (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i) output

/-- Exact standalone run for the complete six-gate arithmetic stack-cell
block.  Unlike the separate primitive interfaces above, this run does not halt
between the leading blank-bit negation and the following Boolean equality. -/
noncomputable def arithmeticStackCellRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) (output : List CircuitSym) :
    EvalsToInTime (step sequentialExactlyOneRevProgram)
      (affineCellBodyCfg (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i) output)
      (some (haltCfg sequentialExactlyOneRevProgram
        ((arithmeticStackCellGateStream tm H start rowBase k i).reverse ++
          output)))
      (affineCellRevSteps (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i)) := by
  simpa [arithmeticStackCellGateStream,
    arithmeticStackCellNotGateStream,
    arithmeticStackCellBoolEqGateStream,
    arithmeticStackCellBoolEqStart,
    affineCellGateStream] using
      affineCellRev_runFrom
        (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i) output

/-- The complete arithmetic stack-cell invocation inherits the generic
quadratic running-time envelope. -/
theorem arithmeticStackCellRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    affineCellRevSteps (arithmeticStackCellNotWire tm H start k i)
        (arithmeticStackMaskOutputWire tm H start k i)
        (arithmeticStackBlankWire tm H rowBase k i) ≤
      200 * (arithmeticStackCellNotWire tm H start k i +
        arithmeticStackMaskOutputWire tm H start k i +
        arithmeticStackBlankWire tm H rowBase k i + 1) ^ 2 :=
  affineCellRev_steps_le _ _ _

/-- The arithmetic six-gate stream is one literal `cellValidityGateBlock`. -/
theorem arithmeticStackCellGateStream_eq_block
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (i : Fin H) :
    arithmeticStackCellGateStream tm H start rowBase k i =
      (cellValidityGateBlock
        (arithmeticStackCellTraceStart tm H start k) H
        (fun j => (arithmeticStackMaskTrace tm H start rowBase k).outputs
          (Fin.cast (by simp [arithmeticStackMaskWires]) j))
        (fun j => (arithmeticCfgWires tm H rowBase).stackCell k j
          (Fin.last (reachableAlphabet tm k).card)) i).flatMap
            encodeCircuitGate := by
  rw [arithmeticStackCellGateStream_eq_semantic]
  simp [cellValidityGateBlock, arithmeticStackCellBoolEqStart,
    arithmeticStackCellNotWire]

/-- Encoded ordered family of every six-gate cell block of one stack. -/
noncomputable def arithmeticStackCellFamilyGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    List CircuitSym :=
  (List.ofFn fun i : Fin H =>
    arithmeticStackCellGateStream tm H start rowBase k i).flatten

/-- Runtime frame list for the complete ordered cell family of one fixed
stack.  Every index remains stack data of the single family controller. -/
noncomputable def arithmeticStackCellFrames
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    List AffineCellFrame :=
  List.ofFn fun i : Fin H =>
    { right := arithmeticStackCellNotWire tm H start k i
      left := arithmeticStackMaskOutputWire tm H start k i
      blank := arithmeticStackBlankWire tm H rowBase k i }

private theorem flatMap_eq_map_flatten {α β : Type*}
    (xs : List α) (f : α → List β) :
    xs.flatMap f = (xs.map f).flatten := by
  induction xs with
  | nil => rfl
  | cons x xs ih => simp [ih]

/-- Interpreting the arithmetic runtime frames yields exactly the existing
semantic `6H` byte stream. -/
theorem arithmeticStackCellFamilyGateStream_eq_framed
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    affineCellFamilyGateStream
        (arithmeticStackCellFrames tm H start rowBase k) =
      arithmeticStackCellFamilyGateStream tm H start rowBase k := by
  rw [affineCellFamilyGateStream_eq_flatMap]
  rw [flatMap_eq_map_flatten]
  unfold arithmeticStackCellFrames arithmeticStackCellFamilyGateStream
  rw [List.map_ofFn]
  simp [Function.comp_def,
    arithmeticStackCellGateStream, arithmeticStackCellNotGateStream,
    arithmeticStackCellBoolEqGateStream, affineCellGateStream,
    arithmeticStackCellBoolEqStart]

/-- One fixed framed controller executes every ordered cell of a runtime-height
stack without halting between cells. -/
noncomputable def arithmeticStackCellFamilyRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (output : List CircuitSym) :
    EvalsToInTime (step affineCellFamilyRevProgram)
      (affineCellFamilyLoopCfg
        (encodeAffineCellFamily
          (arithmeticStackCellFrames tm H start rowBase k)) output)
      (some (haltCfg affineCellFamilyRevProgram
        ((arithmeticStackCellFamilyGateStream tm H start rowBase k).reverse ++
          output)))
      (affineCellFamilyRevSteps
        (arithmeticStackCellFrames tm H start rowBase k)) := by
  simpa [arithmeticStackCellFamilyGateStream_eq_framed] using
    affineCellFamily_run
      (arithmeticStackCellFrames tm H start rowBase k) output

/-- The complete runtime-height cell family inherits the controller's
quadratic bound in its explicit framed input length. -/
theorem arithmeticStackCellFamilyRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    affineCellFamilyRevSteps
        (arithmeticStackCellFrames tm H start rowBase k) ≤
      250 * (encodeAffineCellFamily
        (arithmeticStackCellFrames tm H start rowBase k)).length ^ 2 + 2 :=
  affineCellFamilyRev_steps_le _

private theorem flatten_encoded_blocks (blocks : List (List CircuitGate)) :
    (blocks.map fun block => block.flatMap encodeCircuitGate).flatten =
      blocks.flatten.flatMap encodeCircuitGate := by
  induction blocks with
  | nil => rfl
  | cons block blocks ih => simp [ih]

/-- The ordered arithmetic family is exactly the semantic `6H` cell-validity
trace after the active mask. -/
theorem arithmeticStackCellFamilyGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    arithmeticStackCellFamilyGateStream tm H start rowBase k =
      let mask := arithmeticStackMaskTrace tm H start rowBase k
      let active : Fin H → CircuitBuilder.Wire := fun i =>
        mask.outputs (Fin.cast (by simp [arithmeticStackMaskWires]) i)
      let blank : Fin H → CircuitBuilder.Wire := fun i =>
        (arithmeticCfgWires tm H rowBase).stackCell k i
          (Fin.last (reachableAlphabet tm k).card)
      (cellValidityGateTrace
        (arithmeticStackCellTraceStart tm H start k) H active blank).gates.flatMap
          encodeCircuitGate := by
  unfold arithmeticStackCellFamilyGateStream
  simp_rw [arithmeticStackCellGateStream_eq_block]
  rw [cellValidityGateTrace_gates_eq_blocks]
  simpa [Function.comp_def] using flatten_encoded_blocks
    (List.ofFn fun i : Fin H =>
      cellValidityGateBlock (arithmeticStackCellTraceStart tm H start k) H
        (fun j => (arithmeticStackMaskTrace tm H start rowBase k).outputs
          (Fin.cast (by simp [arithmeticStackMaskWires]) j))
        (fun j => (arithmeticCfgWires tm H rowBase).stackCell k j
          (Fin.last (reachableAlphabet tm k).card)) i)

/-- Complete encoded canonicality stream of one fixed stack: its active mask
followed by every ordered six-gate cell block. -/
noncomputable def arithmeticStackGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    List CircuitSym :=
  arithmeticStackMaskGateStream tm H start rowBase k ++
    arithmeticStackCellFamilyGateStream tm H start rowBase k

/-- Complete runtime frame for one arithmetic stack block. -/
noncomputable def arithmeticStackFrame
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    AffineStackFrame :=
  { start := arithmeticStackBlockStart tm H start k
    base := arithmeticStackMaskWireBase tm H rowBase k
    count := H
    cells := arithmeticStackCellFrames tm H start rowBase k }

/-- Interpreting the arithmetic stack frame yields exactly the established
semantic mask-plus-`6H` byte stream. -/
theorem arithmeticStackGateStream_eq_framed
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    affineStackGateStream (arithmeticStackFrame tm H start rowBase k) =
      arithmeticStackGateStream tm H start rowBase k := by
  simp [affineStackGateStream, arithmeticStackFrame,
    arithmeticStackGateStream, arithmeticStackMaskGateStream,
    arithmeticStackCellFamilyGateStream_eq_framed]

/-- One fixed controller executes the complete arithmetic stack block without
halting between its active mask and any of its runtime-height cells. -/
noncomputable def arithmeticStackRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K)
    (output : List CircuitSym) :
    EvalsToInTime (step affineStackRevProgram)
      (affineStackLoopCfg
        (encodeAffineStackFrame
          (arithmeticStackFrame tm H start rowBase k)) output)
      (some (haltCfg affineStackRevProgram
        ((arithmeticStackGateStream tm H start rowBase k).reverse ++ output)))
      (affineStackRevSteps
        (arithmeticStackFrame tm H start rowBase k)) := by
  simpa [arithmeticStackGateStream_eq_framed] using
    affineStack_run (arithmeticStackFrame tm H start rowBase k) output

/-- The complete arithmetic stack invocation inherits the generic quadratic
bound in the explicit mask-and-cells frame length. -/
theorem arithmeticStackRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    affineStackRevSteps (arithmeticStackFrame tm H start rowBase k) ≤
      400 * (encodeAffineStackFrame
        (arithmeticStackFrame tm H start rowBase k)).length ^ 2 + 2 :=
  affineStackRev_steps_le _

/-- The arithmetic one-stack stream is exactly the semantic mask-plus-cells
trace of length `H + 1 + 6H`. -/
theorem arithmeticStackGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) (k : tm.K) :
    arithmeticStackGateStream tm H start rowBase k =
      let mask := arithmeticStackMaskTrace tm H start rowBase k
      let active : Fin H → CircuitBuilder.Wire := fun i =>
        mask.outputs (Fin.cast (by simp [arithmeticStackMaskWires]) i)
      let blank : Fin H → CircuitBuilder.Wire := fun i =>
        (arithmeticCfgWires tm H rowBase).stackCell k i
          (Fin.last (reachableAlphabet tm k).card)
      let cells := cellValidityGateTrace
        (arithmeticStackCellTraceStart tm H start k) H active blank
      (mask.gates ++ cells.gates).flatMap encodeCircuitGate := by
  unfold arithmeticStackGateStream
  rw [arithmeticStackMaskGateStream_eq_semantic,
    arithmeticStackCellFamilyGateStream_eq_semantic]
  simp

/-- A fixed arithmetic stack stream is the corresponding literal block in the
canonical finite stack order. -/
theorem arithmeticStackGateStream_eq_block
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat)
    (j : Fin (arithmeticStackCount tm)) :
    arithmeticStackGateStream tm H start rowBase
        ((arithmeticStackEquiv tm).symm j) =
      (stackValidityGateBlock (arithmeticStackValidityStart tm H start)
        (arithmeticCfgWires tm H rowBase)
        (fun q => (arithmeticStackEquiv tm).symm q) j).flatMap
          encodeCircuitGate := by
  rw [arithmeticStackGateStream_eq_semantic]
  unfold stackValidityGateBlock arithmeticStackMaskTrace
    arithmeticStackMaskWires arithmeticStackCellTraceStart
    arithmeticStackBlockStart
  rw [arithmeticStackOrdinal_equiv_symm]

/-- Complete encoded stack-validity family in the fixed machine-stack order. -/
noncomputable def arithmeticStackFamilyGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) : List CircuitSym :=
  (List.ofFn fun j : Fin (arithmeticStackCount tm) =>
    arithmeticStackGateStream tm H start rowBase
      ((arithmeticStackEquiv tm).symm j)).flatten

/-- Runtime frame list for all machine stacks in canonical finite order. -/
noncomputable def arithmeticStackFrames
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    List AffineStackFrame :=
  List.ofFn fun j : Fin (arithmeticStackCount tm) =>
    arithmeticStackFrame tm H start rowBase
      ((arithmeticStackEquiv tm).symm j)

/-- Interpreting the fixed-machine stack frames yields exactly the existing
semantic ordered-stack byte stream. -/
theorem arithmeticStackFamilyGateStream_eq_framed
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineStackFamilyGateStream
        (arithmeticStackFrames tm H start rowBase) =
      arithmeticStackFamilyGateStream tm H start rowBase := by
  rw [affineStackFamilyGateStream_eq_flatMap]
  rw [flatMap_eq_map_flatten]
  unfold arithmeticStackFrames arithmeticStackFamilyGateStream
  rw [List.map_ofFn]
  simp [Function.comp_def, arithmeticStackGateStream_eq_framed]

/-- One fixed controller executes the complete fixed-machine stack family,
without halting between masks, cells, or adjacent stacks. -/
noncomputable def arithmeticStackFamilyRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat)
    (output : List CircuitSym) :
    EvalsToInTime (step affineStackRevProgram)
      (affineStackLoopCfg
        (encodeAffineStackFamily
          (arithmeticStackFrames tm H start rowBase)) output)
      (some (haltCfg affineStackRevProgram
        ((arithmeticStackFamilyGateStream tm H start rowBase).reverse ++
          output)))
      (affineStackFamilyRevSteps
        (arithmeticStackFrames tm H start rowBase)) := by
  simpa [arithmeticStackFamilyGateStream_eq_framed] using
    affineStackFamily_run (arithmeticStackFrames tm H start rowBase) output

/-- The complete fixed-machine stack family inherits the generic quadratic
bound in its explicit frame encoding. -/
theorem arithmeticStackFamilyRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineStackFamilyRevSteps
        (arithmeticStackFrames tm H start rowBase) ≤
      400 * (encodeAffineStackFamily
        (arithmeticStackFrames tm H start rowBase)).length ^ 2 + 2 :=
  affineStackFamilyRev_steps_le _

/-- The arithmetic family stream is exactly the semantic ordered-stack trace. -/
theorem arithmeticStackFamilyGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    arithmeticStackFamilyGateStream tm H start rowBase =
      (stackValidityFamilyGateTrace
        (arithmeticStackValidityStart tm H start)
        (arithmeticCfgWires tm H rowBase) (arithmeticStackCount tm)
        (fun j => (arithmeticStackEquiv tm).symm j)).gates.flatMap
          encodeCircuitGate := by
  unfold arithmeticStackFamilyGateStream
  simp_rw [arithmeticStackGateStream_eq_block]
  rw [stackValidityFamilyGateTrace_gates_eq_blocks]
  simpa [Function.comp_def] using flatten_encoded_blocks
    (List.ofFn fun j : Fin (arithmeticStackCount tm) =>
      stackValidityGateBlock (arithmeticStackValidityStart tm H start)
        (arithmeticCfgWires tm H rowBase)
        (fun q => (arithmeticStackEquiv tm).symm q) j)

/-- The complete arithmetic stack-family stream is a literal prefix of the
remaining row-validity stream after halted/none-label agreement. -/
theorem arithmeticStackFamilyGateStream_prefix_postHalted
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    arithmeticStackFamilyGateStream tm H start rowBase <+:
      arithmeticValidityPostHaltedMatchGateStream tm H start rowBase := by
  letI : Fintype tm.K := tm.kFin
  let wires := arithmeticCfgWires tm H rowBase
  let raw := rawOneHotGateTrace start wires
  let halted := CircuitBuilder.boolEqGateTrace
    (start + raw.gates.length) wires.halted
    (wires.label (Fin.last (labelCount tm)))
  let stack := stackValidityFamilyGateTrace
    (start + raw.gates.length + halted.gates.length) wires
    (Fintype.card tm.K) (fun j => (Fintype.equivFin tm.K).symm j)
  let full := canonicalValidityGateTrace start wires
  have hprefix : raw.gates ++ halted.gates ++ stack.gates <+: full.gates := by
    unfold full stack halted raw wires canonicalValidityGateTrace
    simp
  rcases hprefix with ⟨tail, htail⟩
  have hfamily := arithmeticStackFamilyGateStream_eq_semantic
    tm H start rowBase
  have hstackStart : arithmeticStackValidityStart tm H start =
      start + raw.gates.length + halted.gates.length := by
    simp [arithmeticStackValidityStart, arithmeticHaltedMatchStart,
      arithmeticRawOneHotGateCount, raw, halted, wires]
  rw [hstackStart] at hfamily
  change arithmeticStackFamilyGateStream tm H start rowBase =
    stack.gates.flatMap encodeCircuitGate at hfamily
  unfold arithmeticValidityPostHaltedMatchGateStream
  change arithmeticStackFamilyGateStream tm H start rowBase <+:
    (full.gates.drop (raw.gates.length + 5)).flatMap encodeCircuitGate
  rw [hfamily, ← htail]
  rw [show 5 = halted.gates.length by simp [halted]]
  simp [List.flatMap_append]

/-- Ordered output wires consumed by the final conjunction of one arithmetic
row.  This is the exact public constraint order: raw one-hot outputs, halted
agreement, then every stack-cell canonicality output in stack-major order. -/
noncomputable def arithmeticValidityConstraintWires
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    List CircuitBuilder.Wire := by
  letI : Fintype tm.K := tm.kFin
  let wires := arithmeticCfgWires tm H rowBase
  let raw := rawOneHotGateTrace start wires
  let halted := CircuitBuilder.boolEqGateTrace
    (start + raw.gates.length) wires.halted
    (wires.label (Fin.last (labelCount tm)))
  let stack := stackValidityFamilyGateTrace
    (start + raw.gates.length + halted.gates.length) wires
    (Fintype.card tm.K) (fun j => (Fintype.equivFin tm.K).symm j)
  let groupEquiv := cfgOneHotGroupEquivFin tm H
  let rawConstraints : List CircuitBuilder.Wire :=
    List.ofFn fun j : Fin (cfgOneHotGroupCount tm H) =>
      raw.outputs (groupEquiv.symm j)
  let stackConstraints : List CircuitBuilder.Wire :=
    List.ofFn fun p : Fin (Fintype.card tm.K * H) =>
      let q := (finProdFinEquiv
        (m := Fintype.card tm.K) (n := H)).symm p
      stack.outputs q.1 q.2
  exact rawConstraints ++ halted.wire :: stackConstraints

/-- First fresh gate of the final row-validity conjunction, after every
stack mask and cell block. -/
noncomputable def arithmeticValidityFinalStart
    (tm : _root_.Turing.FinTM2) (H start : Nat) : Nat :=
  arithmeticStackValidityStart tm H start +
    arithmeticStackCount tm * (H + 1 + 6 * H)

/-- Exact serialized tail after all stack-validity blocks; semantically this
is the row-validity final conjunction and nothing else. -/
noncomputable def arithmeticValidityFinalConjunctionGateStream
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) : List CircuitSym :=
  (arithmeticValidityPostHaltedMatchGateStream tm H start rowBase).drop
    (arithmeticStackFamilyGateStream tm H start rowBase).length

/-- The formerly opaque post-stack suffix is exactly the encoded tail-first
conjunction over the canonical ordered constraint wires. -/
theorem arithmeticValidityFinalConjunctionGateStream_eq_semantic
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    arithmeticValidityFinalConjunctionGateStream tm H start rowBase =
      (CircuitBuilder.conjunctionGateTrace
        (arithmeticValidityFinalStart tm H start)
        (arithmeticValidityConstraintWires tm H start rowBase)).gates.flatMap
          encodeCircuitGate := by
  letI : Fintype tm.K := tm.kFin
  let wires := arithmeticCfgWires tm H rowBase
  let raw := rawOneHotGateTrace start wires
  let halted := CircuitBuilder.boolEqGateTrace
    (start + raw.gates.length) wires.halted
    (wires.label (Fin.last (labelCount tm)))
  let stack := stackValidityFamilyGateTrace
    (start + raw.gates.length + halted.gates.length) wires
    (Fintype.card tm.K) (fun j => (Fintype.equivFin tm.K).symm j)
  let groupEquiv := cfgOneHotGroupEquivFin tm H
  let rawConstraints : List CircuitBuilder.Wire :=
    List.ofFn fun j : Fin (cfgOneHotGroupCount tm H) =>
      raw.outputs (groupEquiv.symm j)
  let stackConstraints : List CircuitBuilder.Wire :=
    List.ofFn fun p : Fin (Fintype.card tm.K * H) =>
      let q := (finProdFinEquiv
        (m := Fintype.card tm.K) (n := H)).symm p
      stack.outputs q.1 q.2
  let constraints := rawConstraints ++ halted.wire :: stackConstraints
  let final := CircuitBuilder.conjunctionGateTrace
    (start + raw.gates.length + halted.gates.length + stack.gates.length)
    constraints
  have hstack := arithmeticStackFamilyGateStream_eq_semantic
    tm H start rowBase
  have hstackStart : arithmeticStackValidityStart tm H start =
      start + raw.gates.length + halted.gates.length := by
    simp [arithmeticStackValidityStart, arithmeticHaltedMatchStart,
      arithmeticRawOneHotGateCount, raw, halted, wires]
  rw [hstackStart] at hstack
  change arithmeticStackFamilyGateStream tm H start rowBase =
    stack.gates.flatMap encodeCircuitGate at hstack
  have hpost : arithmeticValidityPostHaltedMatchGateStream
      tm H start rowBase =
      stack.gates.flatMap encodeCircuitGate ++
        final.gates.flatMap encodeCircuitGate := by
    unfold arithmeticValidityPostHaltedMatchGateStream
    change ((raw.gates ++ halted.gates ++ stack.gates ++ final.gates).drop
      (raw.gates.length + 5)).flatMap encodeCircuitGate = _
    rw [show 5 = halted.gates.length by simp [halted]]
    simp [List.flatMap_append]
  unfold arithmeticValidityFinalConjunctionGateStream
  rw [hpost, hstack]
  simp only [List.drop_left]
  change final.gates.flatMap encodeCircuitGate =
    (CircuitBuilder.conjunctionGateTrace
      (arithmeticValidityFinalStart tm H start)
      (arithmeticValidityConstraintWires tm H start rowBase)).gates.flatMap
        encodeCircuitGate
  congr 2
  · unfold final
    congr 2
    · exact hstackStart.symm
    · simp [stack, arithmeticStackCount]

/-- Runtime frame for the final tail-first conjunction of all row-validity
constraint outputs. -/
noncomputable def arithmeticValidityFinalConjunctionFrame
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    AffineConjunctionFrame :=
  { start := arithmeticValidityFinalStart tm H start
    wires := arithmeticValidityConstraintWires tm H start rowBase }

/-- Interpreting the arithmetic runtime frame yields byte-for-byte the final
semantic row-validity conjunction stream. -/
theorem arithmeticValidityFinalConjunctionGateStream_eq_framed
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineConjunctionGateStream
        (arithmeticValidityFinalConjunctionFrame tm H start rowBase) =
      arithmeticValidityFinalConjunctionGateStream tm H start rowBase := by
  rw [affineConjunctionGateStream_eq_trace,
    arithmeticValidityFinalConjunctionGateStream_eq_semantic]
  rfl

/-- The fixed conjunction controller executes the complete arithmetic final
constraint fold from its explicit runtime frame. -/
noncomputable def arithmeticValidityFinalConjunctionRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat)
    (output : List CircuitSym) :
    EvalsToInTime (step affineConjunctionRevProgram)
      (affineConjunctionLoopCfg
        (encodeAffineConjunctionFrame
          (arithmeticValidityFinalConjunctionFrame tm H start rowBase))
        output)
      (some (haltCfg affineConjunctionRevProgram
        ((arithmeticValidityFinalConjunctionGateStream
          tm H start rowBase).reverse ++ output)))
      (affineConjunctionRevSteps
        (arithmeticValidityFinalConjunctionFrame tm H start rowBase)) := by
  simpa [arithmeticValidityFinalConjunctionGateStream_eq_framed] using
    affineConjunction_run
      (arithmeticValidityFinalConjunctionFrame tm H start rowBase) output

/-- The arithmetic final conjunction inherits the generic quadratic runtime
bound in its exact delimiter-bearing frame length. -/
theorem arithmeticValidityFinalConjunctionRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineConjunctionRevSteps
        (arithmeticValidityFinalConjunctionFrame tm H start rowBase) ≤
      1000 * (encodeAffineConjunctionFrame
        (arithmeticValidityFinalConjunctionFrame tm H start rowBase)).length ^
          2 + 2 :=
  affineConjunctionRev_steps_le _

/-- Advance the exact row-validity boundary through the entire stack family,
leaving only the final conjunction tail. -/
theorem arithmeticValidityPostHaltedMatch_eq_stack_append_final
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    arithmeticValidityPostHaltedMatchGateStream tm H start rowBase =
      arithmeticStackFamilyGateStream tm H start rowBase ++
        arithmeticValidityFinalConjunctionGateStream tm H start rowBase := by
  rcases arithmeticStackFamilyGateStream_prefix_postHalted
    tm H start rowBase with ⟨tail, htail⟩
  unfold arithmeticValidityFinalConjunctionGateStream
  rw [← htail]
  simp

/-- Exact runtime frame for the complete row-validity suffix after
halted/none-label agreement. -/
noncomputable def arithmeticValidityTailFrame
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    AffineValidityTailFrame :=
  { stackFrames := arithmeticStackFrames tm H start rowBase
    finalFrame :=
      arithmeticValidityFinalConjunctionFrame tm H start rowBase }

/-- Interpreting the linked runtime frame yields byte-for-byte the complete
semantic suffix after halted agreement. -/
theorem arithmeticValidityTailGateStream_eq_postHaltedMatch
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineValidityTailGateStream
        (arithmeticValidityTailFrame tm H start rowBase) =
      arithmeticValidityPostHaltedMatchGateStream tm H start rowBase := by
  rw [arithmeticValidityPostHaltedMatch_eq_stack_append_final]
  unfold arithmeticValidityTailFrame affineValidityTailGateStream
  rw [arithmeticStackFamilyGateStream_eq_framed,
    arithmeticValidityFinalConjunctionGateStream_eq_framed]

/-- One fixed controller executes the entire semantic post-halted suffix with
no halt at the stack/conjunction boundary. -/
noncomputable def arithmeticValidityTailRev_runFrom
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat)
    (output : List CircuitSym) :
    EvalsToInTime (step affineValidityTailRevProgram)
      (affineValidityTailLoopCfg
        (encodeAffineValidityTailFrame
          (arithmeticValidityTailFrame tm H start rowBase)) output)
      (some (haltCfg affineValidityTailRevProgram
        ((arithmeticValidityPostHaltedMatchGateStream
          tm H start rowBase).reverse ++ output)))
      (affineValidityTailRevSteps
        (arithmeticValidityTailFrame tm H start rowBase)) := by
  simpa [arithmeticValidityTailGateStream_eq_postHaltedMatch] using
    affineValidityTail_run
      (arithmeticValidityTailFrame tm H start rowBase) output

/-- The complete arithmetic post-halted suffix inherits the generic quadratic
bound in its exact delimiter-bearing frame. -/
theorem arithmeticValidityTailRev_steps_le
    (tm : _root_.Turing.FinTM2) (H start rowBase : Nat) :
    affineValidityTailRevSteps
        (arithmeticValidityTailFrame tm H start rowBase) ≤
      1400 * (encodeAffineValidityTailFrame
        (arithmeticValidityTailFrame tm H start rowBase)).length ^ 2 + 5 :=
  affineValidityTailRev_steps_le _

end

end CLRS.Chapter34.Turing.CookLevin
Source
https://github.com/tanktechnology/CLRS-Lean

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