Multitape Turing machines on arbitrary inputs over
DefinitionIntMul_MultitapeWordsThis file extends the shared machine model IntMul_MultitapeModel from inputs of the form to arbitrary words over the input alphabet , so that subroutines such as sorting and matrix transposition can be stated.
A letter is some b (the bit ) or none (the separator ), written on the tape as the machine's symbols , or .
- Initial configuration on : state ; the input tape holds ; every other tape holds ; all heads are on cell .
- halts with output at step : after exactly steps from that configuration the state is and the whole output tape is .
- Encodings: is a bit string viewed as a word, and (empty for ).
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
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 ).
Underlying model (from the imported base file). A machine consists of a finite alphabet containing five pairwise distinct symbols — blank , start marker , bit symbols , separator — and possibly further symbols; a finite state set with start state and halting state ; a number of tapes (tape = input tape, tape = output tape, the other are work tapes), each tape having cells indexed by ; and a transition function . The constraints on are: on a tape whose scanned symbol is , it writes back and does not move left; on a tape whose scanned symbol is not , it never writes ; (halting state is a fixed point); and on tape 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 with the written symbol , moves head by (left moves are truncated at , but are never issued from a cell), and changes the state. For a word over , the tape contents "" means: cell holds , cells hold the letters of in order, and every cell beyond holds . A bit is encoded as if is true and otherwise.
This file. Letters of the input/output alphabet are elements of (formally "some bit" or "none", with "none" meaning ).
- : maps the separator letter to the machine symbol and a bit to or as above.
- , for any finite word over (including the empty word and words with consecutive or leading/trailing ): state ; tape holds (letters translated by ); every other tape holds ; all heads at cell .
- , for words over and : after exactly steps from , the state is and the entire output tape (tape ) equals — i.e. cells hold exactly the symbols of 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 is a fixed point of the dynamics, this holding for some is equivalent to "halts within steps with output "; the predicate is never true at since .
- : the bit string viewed letter-by-letter as a word over (contains no ).
- (single separators between consecutive words, none at the ends). Edge cases: the empty list gives the empty word; a one-element list gives . In particular , so 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. .
These are definitions only; nothing is asserted.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.