Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Actual zero-carry initialization from binary countdown templates with a linear clock

Proved
IntMul.CountedZero.generate_zero_word

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

algorithmsfixed-tape-routinginteger-multiplicationturing-machines

Let lll be any finite binary word and put N=val⁡(l)+1N=\operatorname{val}(l)+1N=val(l)+1. A fixed four-tape machine starts with an empty output at its marker and two physically prepared copies of the marked countdown word lll. The original input cells and head come from an arbitrary caller frame. Without a supplied zero payload, it globally halts in its exact final frame within

6N+4∣l∣+36N+4|l|+36N+4∣l∣+3

actual transitions, with output exactly bin⁡N(0)\operatorname{bin}_N(0)binN​(0) and the output cursor at N+1N+1N+1. Both countdown and saved template are fully restored, with heads at their original descriptor-end cursors. Original input cells and head are retained. Empty descriptor words and leading zeros are allowed. Descriptor preparation and physical return of the generated word to another bank remain separate caller stages.

Preamble
import Definitions.Def_IntMul_CountedStream
import Mathlib.Tactic
import Definitions.Def_IntMul_CountedZero
import Mathlib.Data.List.GetD

open IntMul IntMul.CountedZero

Formal statement
theorem IntMul.CountedZero.generate_zero_word (base : machine.Cfg) (z : List Bool) :
    ∃ t : ℕ, t≤ 6*(val z+1)+4*z.length+3 ∧
      machine.step^[t] (initialFrame base z)=finalFrame base z ∧
      (machine.step^[t] (initialFrame base z)).cells machine.inTape=base.cells machine.inTape ∧
      (machine.step^[t] (initialFrame base z)).head machine.inTape=base.head machine.inTape ∧
      (machine.step^[t] (initialFrame base z)).cells machine.outTape=
        machine.tapeOf ((bin (val z+1) 0).map machine.bitSym) ∧
      (machine.step^[t] (initialFrame base z)).state=machine.qHalt ∧
      (machine.step^[t] (initialFrame base z)).head machine.outTape=val z+2 := by sorry
Source
Original complete physical binary-counted zero-word generator and exact retained frame. 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