Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Complete physical parameter and zero-carry setup from original multiplication input

Definition
IntMul_InputCarrySetup

by raresbuhai · Oct 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsfixed-tape-routinginteger-multiplicationturing-machines

A fixed eighteen-tape finite controller starts on the original input x#y with genuinely blank work tapes and all heads at cell zero. It computes canonical binary width, block-size, and precision descriptors; physically prepares precision countdown/template banks 13 and 14 from the retained precision word; writes the complete zero carry into bank 12; and rewinds all parameter and carry heads to their specified positions. The original input remains read-only and global output remains empty. Correctness, sufficient carry precision, exact final frame and a linear actual-transition clock are separate theorem obligations.

Definition code
import Definitions.Def_IntMul_InputArithmeticDescriptors
import Definitions.Def_IntMul_CarryInitialization
set_option maxHeartbeats 1000000
namespace IntMul.InputCarrySetup
open TapeCopy (Sym)
abbrev State := Option (InputArithmeticDescriptors.machine.K ⊕ CarryInitialization.machine.K)
def parameterState (q : InputArithmeticDescriptors.machine.K) : State :=
  match q with | none => none | some p => some (.inl (some p))
def carryState (q : CarryInitialization.machine.K) : State :=
  match q with | none => none | some p => some (.inr (some p))
def nativeTape (j : Fin 16) : Fin 18 :=
  if j.val=3 then 13 else if j.val=4 then 14 else if j.val=13 then 3 else if j.val=14 then 4
  else if j.val=15 then 17 else ⟨j.val,by omega⟩
def innerTape (i : Fin 18) (h : i.val≠15 ∧ i.val≠16) : Fin 16 :=
  if i.val=3 then 13 else if i.val=4 then 14 else if i.val=13 then 3 else if i.val=14 then 4
  else if h17 : i.val=17 then 15 else ⟨i.val,by have := i.isLt;rcases h with ⟨h15,h16⟩;omega⟩
def carryAction (a : Fin 18 → Sym) (r : Fin 16 → Sym × Move) (i : Fin 18) : Sym × Move :=
  if h : i.val≠15 ∧ i.val≠16 then r (innerTape i h) else (a i,.stay)
private theorem native_inner (i : Fin 18) (h : i.val≠15 ∧ i.val≠16) :
    nativeTape (innerTape i h)=i := by
  fin_cases i
  all_goals first | (exact False.elim (h.1 rfl)) | (exact False.elim (h.2 rfl)) | rfl
noncomputable def transition (q : State) (a : Fin 18 → Sym) : State × (Fin 18 → Sym × Move) :=
  match q with
  | none => (none,fun i => (a i,.stay))
  | some (.inl q) => let r := InputArithmeticDescriptors.machine.δ q a;(parameterState r.1,r.2)
  | some (.inr q) => let r := CarryInitialization.machine.δ q (fun j => a (nativeTape j));
      (carryState r.1,carryAction a r.2)
private theorem transition_start (q : State) (a : Fin 18 → Sym) (i : Fin 18) (hi : a i=Sym.start) :
    ((transition q a).2 i).1=Sym.start ∧ ((transition q a).2 i).2≠Move.left := by
  cases q with
  | none =>
      change a i=Sym.start ∧ Move.stay≠Move.left
      exact ⟨hi,by decide⟩
  | some q =>
      cases q with
      | inl q => exact InputArithmeticDescriptors.machine.start_preserved q a i hi
      | inr q =>
          change (carryAction a (CarryInitialization.machine.δ q (fun j => a (nativeTape j))).2 i).1=Sym.start ∧
            (carryAction a (CarryInitialization.machine.δ q (fun j => a (nativeTape j))).2 i).2≠Move.left
          by_cases h : i.val≠15 ∧ i.val≠16
          · simp only [carryAction,dif_pos h]
            have hr : a (nativeTape (innerTape i h))=Sym.start := by rw [native_inner];exact hi
            exact CarryInitialization.machine.start_preserved q (fun j => a (nativeTape j)) (innerTape i h) hr
          · simp only [carryAction,dif_neg h]
            exact ⟨hi,by decide⟩

private theorem transition_no_new_start (q : State) (a : Fin 18 → Sym) (i : Fin 18) (hi : a i≠Sym.start) :
    ((transition q a).2 i).1≠Sym.start := by
  cases q with
  | none => exact hi
  | some q =>
      cases q with
      | inl q => exact InputArithmeticDescriptors.machine.start_only_at_start q a i hi
      | inr q =>
          change (carryAction a (CarryInitialization.machine.δ q (fun j => a (nativeTape j))).2 i).1≠Sym.start
          by_cases h : i.val≠15 ∧ i.val≠16
          · simp only [carryAction,dif_pos h]
            have hr : a (nativeTape (innerTape i h))≠Sym.start := by rw [native_inner];exact hi
            exact CarryInitialization.machine.start_only_at_start q (fun j => a (nativeTape j)) (innerTape i h) hr
          · simpa only [carryAction,dif_neg h] using hi

private theorem transition_input (q : State) (a : Fin 18 → Sym) : ((transition q a).2 0).1=a 0 := by
  cases q with
  | none => rfl
  | some q =>
      cases q with
      | inl q => exact InputArithmeticDescriptors.machine.input_readonly q a
      | inr q => exact CarryInitialization.machine.input_readonly q (fun j => a (nativeTape j))

noncomputable abbrev subroutine : MultitapeTM where
  Sym := Sym
  blank := .blank
  startSym := .start
  zero := .zero
  one := .one
  sep := .sep
  syms_distinct := by decide
  K := State
  instFintypeK := by
    letI : Fintype InputArithmeticDescriptors.machine.K := InputArithmeticDescriptors.machine.instFintypeK
    letI : Fintype CarryInitialization.machine.K := CarryInitialization.machine.instFintypeK
    change Fintype (Option (InputArithmeticDescriptors.machine.K ⊕ CarryInitialization.machine.K))
    infer_instance
  qStart := parameterState InputArithmeticDescriptors.machine.qStart
  qHalt := none
  start_ne_halt := by exact Option.some_ne_none _
  k := 18
  two_le_k := by decide
  δ := transition
  start_preserved := transition_start
  start_only_at_start := transition_no_new_start
  halt_fixed := by intro a;rfl
  input_readonly := transition_input

noncomputable def dispatch (carry : Bool) (_a : Fin 18 → Sym) : Option (Bool × State) :=
  if carry then none else some (true,carryState CarryInitialization.machine.qStart)
noncomputable abbrev machine : MultitapeTM := FiniteCaller.machine subroutine Bool false dispatch
noncomputable def parameterView (c : InputArithmeticDescriptors.machine.Cfg) : subroutine.Cfg where
  state := parameterState c.state
  cells := c.cells
  head := c.head
noncomputable def carryBase (x y : List Bool) : CarryInitialization.machine.Cfg where
  state := CarryInitialization.machine.qHalt
  cells := fun j => (InputArithmeticDescriptors.finalFrame x y).cells (nativeTape j)
  head := fun j => (InputArithmeticDescriptors.finalFrame x y).head (nativeTape j)
noncomputable def carryView (x y : List Bool) (c : CarryInitialization.machine.Cfg) : subroutine.Cfg where
  state := carryState c.state
  cells := fun i => if h : i.val≠15 ∧ i.val≠16 then c.cells (innerTape i h)
    else (InputArithmeticDescriptors.finalFrame x y).cells i
  head := fun i => if h : i.val≠15 ∧ i.val≠16 then c.head (innerTape i h)
    else (InputArithmeticDescriptors.finalFrame x y).head i
noncomputable def finalFrame (x y : List Bool) : machine.Cfg where
  state := machine.qHalt
  cells := (carryView x y (CarryInitialization.finalFrame (carryBase x y)
    (InputArithmeticDescriptors.precisionWord x y))).cells
  head := (carryView x y (CarryInitialization.finalFrame (carryBase x y)
    (InputArithmeticDescriptors.precisionWord x y))).head
end IntMul.InputCarrySetup

#print axioms IntMul.InputCarrySetup.subroutine
Source
Original complete physical input-to-parameter-and-carry preparation controller. Written by Codex.

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