Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Multitape Turing machines on arbitrary inputs over {0,1,#}\{0,1,\#\}{0,1,#}

Definition
IntMul_MultitapeWords

by avi · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationturing-machines

This file extends the shared machine model IntMul_MultitapeModel from inputs of the form x#yx\#yx#y to arbitrary words over the input alphabet {0,1,#}\{0,1,\#\}{0,1,#}, so that subroutines such as sorting and matrix transposition can be stated.

A letter is some b (the bit bbb) or none (the separator #\##), written on the tape as the machine's symbols 000, 111 or #\##.

  • Initial configuration on www: state START\mathrm{START}START; the input tape holds ▹ w □□⋯\triangleright\,w\,\square\square\cdots▹w□□⋯; every other tape holds ▹ □□⋯\triangleright\,\square\square\cdots▹□□⋯; all heads are on cell 000.
  • MMM halts with output vvv at step ttt: after exactly ttt steps from that configuration the state is HALT\mathrm{HALT}HALT and the whole output tape is ▹ v □□⋯\triangleright\,v\,\square\square\cdots▹v□□⋯.
  • Encodings: bits(x)\mathrm{bits}(x)bits(x) is a bit string viewed as a word, and joinSep(u1,…,um)=u1#u2#⋯#um\mathrm{joinSep}(u_1,\dots,u_m)=u_1\#u_2\#\cdots\#u_mjoinSep(u1​,…,um​)=u1​#u2​#⋯#um​ (empty for m=0m=0m=0).
Definition code
import Mathlib
import Definitions.Def_IntMul_MultitapeModel

/-!
# Multitape machines on general inputs over `{0, 1, #}`

Extends the shared model `IntMul_MultitapeModel` (Montanaro, *Computational Complexity*, §3,
§3.4) from inputs `x#y` to arbitrary words over the input alphabet `{0, 1, #}`, so that
subroutines such as sorting and matrix transposition can be stated. A letter is an
`Option Bool`: `some b` is the bit `b` and `none` is the separator `#`.
-/

namespace IntMul

namespace MultitapeTM

variable (M : MultitapeTM)

/-- The tape symbol of a letter of `{0, 1, #}`. -/
def letterSym : Option Bool → M.Sym
  | none => M.sep
  | some b => M.bitSym b

/-- The initial configuration on input `w`: state `START`; the input tape holds `▷ w □ □ …`;
every other tape holds `▷ □ □ …`; every head is on cell `0`. -/
def initCfgW (w : List (Option Bool)) : M.Cfg where
  state := M.qStart
  cells := fun i => if i = M.inTape then M.tapeOf (w.map M.letterSym) else M.tapeOf []
  head := fun _ => 0

/-- On input `w`, after `t` steps the machine is in state `HALT` and the output tape holds
exactly `▷ v □ □ …`. -/
def HaltsWithOutputW (w : List (Option Bool)) (t : ℕ) (v : List (Option Bool)) : Prop :=
  (M.step^[t] (M.initCfgW w)).state = M.qHalt ∧
    (M.step^[t] (M.initCfgW w)).cells M.outTape = M.tapeOf (v.map M.letterSym)

end MultitapeTM

/-- A bit string as a word over `{0, 1, #}`. -/
def bits (x : List Bool) : List (Option Bool) := x.map some

/-- The words `u₁ # u₂ # ⋯ # u_m` (the empty list gives the empty word). -/
def joinSep (us : List (List (Option Bool))) : List (Option Bool) :=
  List.intercalate [none] us

end IntMul
Source
A. Montanaro, Computational Complexity, lecture notes (Cambridge Part III, 2012), §3, §3.4, §4; extends the published definition IntMul_MultitapeModel to inputs other than x#y.
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Definitions letterSym, initCfgW, HaltsWithOutputW, bits, joinSep (extension of the multitape model to words over {0,1,#}\{0,1,\#\}{0,1,#}).

Underlying model (from the imported base file). A machine MMM consists of a finite alphabet Σ\SigmaΣ containing five pairwise distinct symbols — blank □\square□, start marker ▹\triangleright▹, bit symbols 0,1\mathtt 0,\mathtt 10,1, separator #\## — and possibly further symbols; a finite state set KKK with start state qstartq_{\mathrm{start}}qstart​ and halting state qhalt≠qstartq_{\mathrm{halt}} \neq q_{\mathrm{start}}qhalt​=qstart​; a number of tapes k≥2k \ge 2k≥2 (tape 000 = input tape, tape 111 = output tape, the other k−2k-2k−2 are work tapes), each tape having cells indexed by 0,1,2,…0,1,2,\dots0,1,2,…; and a transition function δ:K×Σk→K×(Σ×{←,−,→})k\delta : K \times \Sigma^k \to K \times (\Sigma \times \{\leftarrow, -, \rightarrow\})^kδ:K×Σk→K×(Σ×{←,−,→})k. The constraints on δ\deltaδ are: on a tape whose scanned symbol is ▹\triangleright▹, it writes ▹\triangleright▹ back and does not move left; on a tape whose scanned symbol is not ▹\triangleright▹, it never writes ▹\triangleright▹; δ(qhalt,a)=(qhalt,(ai,−)i)\delta(q_{\mathrm{halt}}, a) = (q_{\mathrm{halt}}, (a_i, -)_i)δ(qhalt​,a)=(qhalt​,(ai​,−)i​) (halting state is a fixed point); and on tape 000 it always writes back the scanned symbol (input tape read-only; the head may still move). One step overwrites the scanned cell of each tape iii with the written symbol σi\sigma_iσi​, moves head iii by −1,0,+1-1, 0, +1−1,0,+1 (left moves are truncated at 000, but are never issued from a ▹\triangleright▹ cell), and changes the state. For a word uuu over Σ\SigmaΣ, the tape contents "▹u□□⋯\triangleright u \square\square\cdots▹u□□⋯" means: cell 000 holds ▹\triangleright▹, cells 1,…,∣u∣1,\dots,|u|1,…,∣u∣ hold the letters of uuu in order, and every cell beyond ∣u∣|u|∣u∣ holds □\square□. A bit bbb is encoded as 1\mathtt 11 if bbb is true and 0\mathtt 00 otherwise.

This file. Letters of the input/output alphabet are elements of {0,1}∪{#}\{0,1\} \cup \{\#\}{0,1}∪{#} (formally "some bit" or "none", with "none" meaning #\##).

  • letterSymM\mathrm{letterSym}_MletterSymM​: maps the separator letter to the machine symbol #\## and a bit bbb to 0\mathtt 00 or 1\mathtt 11 as above.
  • initCfgWM(w)\mathrm{initCfgW}_M(w)initCfgWM​(w), for any finite word www over {0,1,#}\{0,1,\#\}{0,1,#} (including the empty word and words with consecutive or leading/trailing #\##): state qstartq_{\mathrm{start}}qstart​; tape 000 holds ▹ w □□⋯\triangleright\, w\, \square\square\cdots▹w□□⋯ (letters translated by letterSym\mathrm{letterSym}letterSym); every other tape holds ▹□□⋯\triangleright \square\square\cdots▹□□⋯; all heads at cell 000.
  • HaltsWithOutputWM(w,t,v)\mathrm{HaltsWithOutputW}_M(w, t, v)HaltsWithOutputWM​(w,t,v), for words w,vw, vw,v over {0,1,#}\{0,1,\#\}{0,1,#} and t∈Nt \in \mathbb Nt∈N: after exactly ttt steps from initCfgWM(w)\mathrm{initCfgW}_M(w)initCfgWM​(w), the state is qhaltq_{\mathrm{halt}}qhalt​ and the entire output tape (tape 111) equals ▹ v □□⋯\triangleright\, v\, \square\square\cdots▹v□□⋯ — i.e. cells 1..∣v∣1..|v|1..∣v∣ hold exactly the symbols of vvv and every later cell is blank (no leftover symbols, including extra alphabet symbols, may remain). Head positions and work-tape and input-tape contents are unconstrained. Because qhaltq_{\mathrm{halt}}qhalt​ is a fixed point of the dynamics, this holding for some t≤Tt \le Tt≤T is equivalent to "halts within TTT steps with output vvv"; the predicate is never true at t=0t = 0t=0 since qstart≠qhaltq_{\mathrm{start}} \ne q_{\mathrm{halt}}qstart​=qhalt​.
  • bits(x)\mathrm{bits}(x)bits(x): the bit string xxx viewed letter-by-letter as a word over {0,1,#}\{0,1,\#\}{0,1,#} (contains no #\##).
  • joinSep(u1,…,um)=u1#u2#⋯#um\mathrm{joinSep}(u_1,\dots,u_m) = u_1 \# u_2 \# \cdots \# u_mjoinSep(u1​,…,um​)=u1​#u2​#⋯#um​ (single separators between consecutive words, none at the ends). Edge cases: the empty list gives the empty word; a one-element list (u1)(u_1)(u1​) gives u1u_1u1​. In particular joinSep()=joinSep(ε)=ε\mathrm{joinSep}() = \mathrm{joinSep}(\varepsilon) = \varepsilonjoinSep()=joinSep(ε)=ε, so joinSep\mathrm{joinSep}joinSep is not injective on lists in general (it is injective on lists of a fixed known length whose entries contain no #\##); empty entries produce adjacent separators, e.g. joinSep(ε,ε)=#\mathrm{joinSep}(\varepsilon,\varepsilon) = \#joinSep(ε,ε)=#.

These are definitions only; nothing is asserted.

Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by avi · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by mikedeng1 · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

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