Addition and subtraction of -bit integers in time on a multitape Turing machine
ProvedIntMul.TM.add_sub_linearAddition and subtraction in linear time. Both of the following hold.
- Addition. There are a deterministic multitape Turing machine and a constant such that for every and all , on input the machine halts within steps with output
the exact sum written with bits, most significant first.
- Subtraction. There are a deterministic multitape Turing machine and a constant such that for every and all , on input the machine halts within steps with the -bit output
that is, a sign bit followed by the -bit magnitude of the difference (zero has sign ).
These are the linear-time integer operations quoted in §2.1 of Harvey–van der Hoeven ("we may compute and in time "), here for operands of equal bit length , in sign-and-magnitude form.
Formalization Note The machine model is the shared IntMul_MultitapeModel with input . The bounds hold for every , including (input ); nothing is required on inputs with . The two parts may use different machines.
import Mathlib import Definitions.Def_IntMul_MultitapeModel
namespace IntMul.TM
theorem add_sub_linear :
(∃ M : MultitapeTM, ∃ c : ℝ, 0 < c ∧ ∀ x y : List Bool, x.length = y.length →
∃ t : ℕ, (t : ℝ) ≤ c * (x.length + 1) ∧
M.HaltsWithOutput x y t (bin (x.length + 1) (val x + val y))) ∧
(∃ M : MultitapeTM, ∃ c : ℝ, 0 < c ∧ ∀ x y : List Bool, x.length = y.length →
∃ t : ℕ, (t : ℝ) ≤ c * (x.length + 1) ∧
M.HaltsWithOutput x y t
(decide (val x < val y) ::
bin x.length (if val y ≤ val x then val x - val y else val y - val x))) := by sorry
end IntMul.TMRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Theorem IntMul.TM.add_sub_linear (no hypotheses; a conjunction of two independent existence claims).
Machine model. A machine is a deterministic -tape Turing machine with (chosen by the machine) over a finite alphabet containing five pairwise distinct symbols: blank , start symbol , bit symbols , , and separator . It has a finite state set with start state and halting state , and a total transition function . The following constraints apply: on a cell holding the machine rewrites and does not move left; is never written on a cell not holding it; , so once in the configuration is frozen; tape (the input tape) is read-only. Tapes are indexed by cells . Tape is the output tape, and the rest are work tapes. In one step every tape's scanned cell is overwritten and its head moves as dictates. On input with , the initial configuration has state , input tape (bits written as the symbols ), every other tape , and all heads on cell . means that after exactly steps from this configuration the state is and the whole output tape equals , i.e. cell is , cells hold the bits of , and every later cell is blank. Because freezes the configuration, "there is such a " is the same as "halts with output within steps".
Encodings. For a bit string , (most significant bit first; leading zeros allowed; ), so . For , is the length- bit string whose -th entry () is bit number of (most significant first). It always has length exactly , and equals the true -bit representation of when (otherwise the high bits are silently dropped).
Conjunct 1 (addition). There exist a machine and a real constant (both fixed before, and independent of, the inputs) such that for all bit strings with there is with
Since , the output is always the exact -bit binary sum (no truncation), of fixed length .
Conjunct 2 (subtraction with sign). There exist a machine and a real constant (again fixed before the inputs, and possibly different from , ) such that for all bit strings with there is with and halts at step with output the length- string
The subtraction is natural-number (truncated) subtraction, but in each branch the minuend is at least the subtrahend, so no truncation occurs and . The sign bit and the branch agree: exactly in the second branch. Since , is the exact -bit representation of . So the output is a sign bit ( means , i.e. is negative) followed by the -bit magnitude of the difference; zero is always encoded with sign .
Edge cases. The case is included: then , the input tape is , conjunct 1 requires output (one bit) and conjunct 2 requires output (sign bit only, empty magnitude), each within (resp. ) steps. If or, more generally, , conjunct 2's output is followed by zeros. Inputs with are not covered: nothing is asserted about the machines' behaviour on them (they need not halt). Nothing is asserted about inputs not of the form . The time bound holds for every (there is no threshold ), and the constant is uniform over all inputs. The hypothesis is satisfiable for every , so neither conjunct is vacuous. In both conjuncts the required output is a well-defined string of fixed length carrying the exact value. Each required output is a total function of , so neither conjunct is unsatisfiable on its face. The output tape must contain exactly that string and blanks after it. Work tapes and the final head positions are unconstrained.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.