Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Alphabet-compatible same-tape compiler for global-marker routines and interior banks

Definition
IntMul_TaggedAlphabetLift

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

algorithmsfixed-tape-routinginteger-multiplicationturing-machines

For any finite multitape machine M, a finite compiler embeds its ordinary alphabet into the tagged alphabet used by interior work banks. The global start marker maps to the distinguished outer marker, while all other symbols are tagged. The compiled transition retains the same states and number of tapes, decodes scanned symbols, executes one native transition, and protects the global marker. Exact step simulation, standard initial configurations, input retention, and output preservation are separate theorem obligations.

Definition code
import Definitions.Def_IntMul_BankedSimulation
namespace IntMul.AlphabetLift
noncomputable def encode (M : MultitapeTM) (s : M.Sym) : Option M.Sym := by
  classical
  exact if s=M.startSym then none else some s
noncomputable def transition (M : MultitapeTM) (q : M.K) (a : Fin M.k → Option M.Sym) :
    M.K × (Fin M.k → Option M.Sym × Move) :=
  let r := M.δ q (fun i => BankedSimulation.decode M (a i))
  (r.1,fun i => BankedSimulation.protect M (a i) (r.2 i).1 (r.2 i).2)
noncomputable abbrev machine (M : MultitapeTM) : MultitapeTM where
  Sym := Option M.Sym
  blank := some M.blank
  startSym := none
  zero := some M.zero
  one := some M.one
  sep := some M.sep
  syms_distinct := (BankedSimulation.machine M).syms_distinct
  K := M.K
  qStart := M.qStart
  qHalt := M.qHalt
  start_ne_halt := M.start_ne_halt
  k := M.k
  two_le_k := M.two_le_k
  δ := transition M
  start_preserved := by
    intro q a i hi
    simp only [transition];rw [hi];simp only [BankedSimulation.protect]
    split <;> simp_all
  start_only_at_start := by
    intro q a i hi
    simp only [transition]
    cases hs : a i with
    | none => exact False.elim (hi hs)
    | some s => simp [BankedSimulation.protect]
  halt_fixed := by
    intro a
    simp only [transition,M.halt_fixed]
    congr 1;funext i;cases a i <;> rfl
  input_readonly := by
    intro q a
    change (BankedSimulation.protect M (a M.inTape)
      ((M.δ q (fun i => BankedSimulation.decode M (a i))).2 M.inTape).1 _).1=a M.inTape
    simp only [MultitapeTM.inTape]
    rw [M.input_readonly]
    cases ha : a ⟨0,by have := M.two_le_k;omega⟩ <;> simp [ha,BankedSimulation.decode,BankedSimulation.protect]
noncomputable def embed (M : MultitapeTM) (c : M.Cfg) : (machine M).Cfg where
  state := c.state
  cells := fun i p => encode M (c.cells i p)
  head := c.head
end IntMul.AlphabetLift
Source
Original alphabet-compatible literal finite transition compiler. 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