Abstract
This entry formalises nondeterministic multitape Turing machines in Isabelle/HOL, depending only on HOL-Library.
A machine's transition is a relation rather than a function: it may allow several moves at each step, so a machine can follow many different computations on one input (the machine is nondeterministic), and it accepts when at least one computation reaches an accepting state. Deterministic machines, which have a single move everywhere, are the special case. The number of tapes is ordinary data rather than fixed in the machine's type, so a single theorem can speak about machines with any number of tapes.
Each tape carries a marker at its left end, and the model allows a machine to move that marker to the right, discarding a stretch of tape it can never return to. We prove that this relocation preserves the accepted language: a run before the move reaches an accepting state exactly when the matching run after it does.
On top of the model, the entry provides the constructions that developments built on it share: facts about runs, renaming a machine's states and alphabet, widening and exchanging tapes, running a machine as one factor of a composite, restoring the endmarker discipline, exact unary clocks, and the product of a machine with a clock that stops it.
The formalisation adapts Dalvit and Thiemann's multitape Turing machine development, the AFP entry Multitape_To_Singletape_TM. Beyond the tape count, it differs in making a machine an ordinary value that theorems can range over, rather than a fixed locale context. Its names differ from theirs (ktm for mttm, move for dir, and so on), so a theory can import both entries.
The Claude family of AI models, via Claude Code, was used for proof engineering; OpenAI Codex was used in collecting the constructions over the model.
License
Note
Generative AI was used for proof engineering and to write descriptions of the results, together with human design, steering, and review.
History
- November 10, 2026
- Removed the theory Multitape_Enum_Type (enum_on_typedef).
- October 28, 2026
- Added theories of constructions shared by the entries built on the substrate: facts about runs, relabelling, tape embedding, endmarker normalisation, exact unary clocks and a machine/clock product, a binary codec, and enum instances for finite index types. Renamed the model so that it can be imported beside Multitape_To_Singletape_TM (mttm becomes ktm, dir becomes move, the mt_ prefix becomes ktc_). Removed lemmas that duplicated HOL or each other. Updated abstract.
Topics
Session Multitape_TM_Substrate
- Multitape_Substrate_Core
- Multitape_Substrate
- Multitape_Origin_Float
- Multitape_Finite_Control
- Multitape_Finite_Patch
- Multitape_Time_Convention
- Multitape_Run_Facts
- Multitape_Relabelling
- Multitape_Embedding
- Multitape_Endmarker_Normal
- Multitape_Clock_Interface
- Multitape_Clock_Product
- Multitape_One_Tape_Clocks
- Multitape_Binary_Codec