Deterministic multitape Turing machines and running time
Lax119563.DeterministicTime · concepts/Lax119563/DeterministicTime.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
We use deterministic multitape Turing machines with a finite number of tapes, symbols and states, in which every transition reads the scanned symbols, writes one symbol per tape, and moves each head by at most one cell. The cells of each tape are indexed by the integers; initially all heads are at position zero, the first tape (tape ) contains the binary input at positions , and all other cells are blank. Each transition, including the halting transition, takes one step, and halting returns a bit.
- A machine halts within steps if it has returned its bit after steps.
- A machine decides a property of the input within steps if it halts within steps and returns exactly when the property holds. It accepts if it halts on and returns .
- A machine computes from within steps if on input it halts within steps and, at that point, tape contains exactly , laid out as an input would be: at positions and blanks elsewhere.
- A language is decidable in time if some deterministic machine and constant are such that decides within steps, for every .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Algebra.Order.Floor.Semiring |
| 2 | import Mathlib.Algebra.Order.Archimedean.Real.Basic |
| 3 | import Lax489179.TuringMachine |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Deterministic multitape Turing machines and running time |
| 8 | type: definition |
| 9 | --- |
| 10 | We use deterministic multitape Turing machines with a finite number of tapes, symbols and |
| 11 | states, in which every transition reads the scanned symbols, writes one symbol per tape, and |
| 12 | moves each head by at most one cell. The cells of each tape are indexed by the integers; initially all heads |
| 13 | are at position zero, the first tape (tape ) contains the binary input at positions |
| 14 | , and all other cells are blank. Each transition, including the halting |
| 15 | transition, takes one step, and halting returns a bit. |
| 16 | |
| 17 | * A machine *halts within steps* if it has returned its bit after steps. |
| 18 | * A machine *decides* a property of the input *within steps* if it halts within steps |
| 19 | and returns exactly when the property holds. It *accepts* if it halts on and |
| 20 | returns . |
| 21 | * A machine *computes from within steps* if on input it halts within |
| 22 | steps and, at that point, tape contains exactly , laid out as an input would be: |
| 23 | at positions and blanks elsewhere. |
| 24 | * A language is decidable in time if some |
| 25 | deterministic machine and constant are such that decides |
| 26 | within steps, for every . |
| 27 | |
| 28 | # Implementation notes |
| 29 | |
| 30 | The machine model is the one of `Lax489179.TuringMachine`, restricted to deterministic |
| 31 | machines, whose transitions ignore the random bit. Their runs are evaluated with the |
| 32 | constant random bit `false`. Taking a step from a halted configuration does not change it, so |
| 33 | "halts within steps" means that the answer is present after steps. |
| 34 | |
| 35 | `Lax489179.TuringMachine.DecidesWithin` is the bounded-error notion of deciding for randomized |
| 36 | machines; for deterministic machines it agrees with `DecidesExactlyWithin` |
| 37 | (`Lax489179.DeterministicSemantics.turing_exact`). |
| 38 | |
| 39 | # Choice of machine model |
| 40 | |
| 41 | The time hierarchy theorem is the place where the exact exponent of the main lower |
| 42 | bound enters: Theorem `runtime_lower_bound` rules out running time , |
| 43 | and that exponent depends on the machine model. Polynomially equivalent models are therefore |
| 44 | not interchangeable here. The available Turing machine notions compare as follows. |
| 45 | |
| 46 | * **Mathlib, single-tape machines** (`Turing.TM0`, `Turing.TM1`). These are one-tape models. |
| 47 | A single-tape machine needs steps for tasks that a two-tape machine does in |
| 48 | linear time, such as recognizing palindromes or copying its input. Our reduction |
| 49 | (built from `packed_representation` and `matrix_compiler`) runs in quasi-linear time only on several tapes, and the |
| 50 | sharp hierarchy for every real |
| 51 | is a multitape statement. |
| 52 | * **Mathlib, multi-stack machines** (`Turing.FinTM2` with `TM2OutputsInTime`, |
| 53 | `TM2ComputableInTime` and `TM2ComputableInPolyTime`). A multitape machine and a multi-stack |
| 54 | machine simulate each other with constant-factor overhead (one tape is two stacks), so |
| 55 | this model would be adequate in principle. It has drawbacks for this statement: |
| 56 | * one step executes a whole statement tree (several pushes, pops and branches); |
| 57 | * only the input stack is required to have a finite alphabet; |
| 58 | * a machine outputs a list, and only once all other stacks are empty and the internal |
| 59 | state is reset, so there is no native notion of deciding with a Boolean answer; |
| 60 | * mathlib has no time classes for a fixed exponent, and no proof that the model is |
| 61 | equivalent to multitape Turing machines. |
| 62 | |
| 63 | Hence would have to be defined here anyway, and the theorem, which is |
| 64 | stated in the literature for multitape machines, would transfer to this model only through |
| 65 | a simulation. |
| 66 | * **Complexity classes in the archive.** The registered classes on bit strings, such as |
| 67 | `Lax434930.PolynomialTime.P` and `Lax429075.Reductions.ManyOne` (built on mathlib's |
| 68 | `FinTM2` in polynomial time), `Lax759944.TuringPolytime` (the same, with equivalence to |
| 69 | word RAMs), and `Lax434930.ExponentialTime.EXPTIME` (a single-tape machine), only speak |
| 70 | about polynomial or exponential time up to a polynomial. They cannot separate |
| 71 | from . `Lax251941` models single-tape machines as string |
| 72 | rewriting, a representation meant for undecidability. |
| 73 | * **The fine-grained multitape model** `Lax489179.TuringMachine` (used here). It is the |
| 74 | textbook deterministic multitape Turing machine: |
| 75 | * a fixed finite number of tapes, symbols and states; |
| 76 | * each transition reads the scanned symbols, writes one symbol per tape and moves each head |
| 77 | by at most one cell, and costs exactly one step, including the halting transition, so no |
| 78 | uncharged computation happens inside a transition; |
| 79 | * the input is laid out on tape , and halting returns a bit. |
| 80 | |
| 81 | This is the model in which Hartmanis–Stearns and Hennie–Stearns state the hierarchy, and in |
| 82 | which the paper states its reduction and its lower bound, so the statement says exactly |
| 83 | what the literature proves. It is the registered model of the fine-grained hypotheses |
| 84 | (SETH, ETH, 3SUM, APSP), so the lower bound lives in the same model as those conditional |
| 85 | statements. We restrict it to deterministic machines (`Deterministic`), whose transitions |
| 86 | ignore the random bit. |
| 87 | |
| 88 | Neither mathlib nor the archive provides machine constructions for `Lax489179`, so those |
| 89 | needed here (composition, rewinding, the compiled reduction programs, and a universal machine |
| 90 | for the diagonalization) are carried out directly in this model in the proofs. The |
| 91 | translations to the archive's single-tape and multi-stack models, used for the |
| 92 | -hardness of WL Distinguishing, are `Lax119563.MachineTranslations`. |
| 93 | -/ |
| 94 | |
| 95 | open Lax489179.TuringMachine |
| 96 | |
| 97 | namespace Lax119563.DeterministicTime |
| 98 | |
| 99 | /-- The configuration of `M` after `t` steps on input `x`. -/ |
| 100 | def runOn (M : Machine) (x : List Bool) (t : ℕ) : Config M := |
| 101 | run M t (fun _ => false) (init M x) |
| 102 | |
| 103 | /-- `M` halts on input `x` within `t` steps: its answer is present after `t` steps. -/ |
| 104 | def HaltsWithin (M : Machine) (x : List Bool) (t : ℕ) : Prop := |
| 105 | (runOn M x t).answer.isSome |
| 106 | |
| 107 | /-- `M` decides `P` on input `x` within `t` steps: it halts within `t` steps and returns |
| 108 | `true` exactly when `P` holds. -/ |
| 109 | def DecidesExactlyWithin (M : Machine) (x : List Bool) (P : Prop) (t : ℕ) : Prop := |
| 110 | ∃ b, (runOn M x t).answer = some b ∧ (b = true ↔ P) |
| 111 | |
| 112 | /-- `M` accepts `x`: it halts on `x` and returns `true`. -/ |
| 113 | def Accepts (M : Machine) (x : List Bool) : Prop := |
| 114 | ∃ t, (runOn M x t).answer = some true |
| 115 | |
| 116 | /-- `M` computes `y` from `x` within `t` steps: it halts within `t` steps, and then tape `0` |
| 117 | holds `y` in the layout of an input. -/ |
| 118 | def ComputesWithin (M : Machine) (x y : List Bool) (t : ℕ) : Prop := |
| 119 | HaltsWithin M x t ∧ (runOn M x t).tape 0 = (init M y).tape 0 |
| 120 | |
| 121 | /-- The language `L` is decidable in time `O(f(n))` by a deterministic multitape Turing |
| 122 | machine. -/ |
| 123 | def DecidableInTime (L : Set (List Bool)) (f : ℕ → ℝ) : Prop := |
| 124 | ∃ M : Machine, Deterministic M ∧ ∃ C : ℕ, |
| 125 | ∀ x : List Bool, DecidesExactlyWithin M x (x ∈ L) ⌊C * f x.length + C⌋₊ |
| 126 | |
| 127 | end Lax119563.DeterministicTime |
| 128 |
Implementation notes
The machine model is the one of , restricted to deterministic machines, whose transitions ignore the random bit. Their runs are evaluated with the constant random bit . Taking a step from a halted configuration does not change it, so "halts within steps" means that the answer is present after steps.
is the bounded-error notion of deciding for randomized machines; for deterministic machines it agrees with ().
Choice of machine model
The time hierarchy theorem is the place where the exact exponent of the main lower bound enters: Theorem rules out running time , and that exponent depends on the machine model. Polynomially equivalent models are therefore not interchangeable here. The available Turing machine notions compare as follows.
Mathlib, single-tape machines (, ). These are one-tape models. A single-tape machine needs steps for tasks that a two-tape machine does in linear time, such as recognizing palindromes or copying its input. Our reduction (built from and ) runs in quasi-linear time only on several tapes, and the sharp hierarchy for every real is a multitape statement.
Mathlib, multi-stack machines ( with , and ). A multitape machine and a multi-stack machine simulate each other with constant-factor overhead (one tape is two stacks), so this model would be adequate in principle. It has drawbacks for this statement:
- one step executes a whole statement tree (several pushes, pops and branches);
- only the input stack is required to have a finite alphabet;
- a machine outputs a list, and only once all other stacks are empty and the internal state is reset, so there is no native notion of deciding with a Boolean answer;
- mathlib has no time classes for a fixed exponent, and no proof that the model is equivalent to multitape Turing machines.
Hence would have to be defined here anyway, and the theorem, which is stated in the literature for multitape machines, would transfer to this model only through a simulation.
Complexity classes in the archive. The registered classes on bit strings, such as and (built on mathlib's in polynomial time), (the same, with equivalence to word RAMs), and (a single-tape machine), only speak about polynomial or exponential time up to a polynomial. They cannot separate from . models single-tape machines as string rewriting, a representation meant for undecidability.
The fine-grained multitape model (used here). It is the textbook deterministic multitape Turing machine:
- a fixed finite number of tapes, symbols and states;
- each transition reads the scanned symbols, writes one symbol per tape and moves each head by at most one cell, and costs exactly one step, including the halting transition, so no uncharged computation happens inside a transition;
- the input is laid out on tape , and halting returns a bit.
This is the model in which Hartmanis–Stearns and Hennie–Stearns state the hierarchy, and in which the paper states its reduction and its lower bound, so the statement says exactly what the literature proves. It is the registered model of the fine-grained hypotheses (SETH, ETH, 3SUM, APSP), so the lower bound lives in the same model as those conditional statements. We restrict it to deterministic machines (), whose transitions ignore the random bit.
Neither mathlib nor the archive provides machine constructions for , so those needed here (composition, rewinding, the compiled reduction programs, and a universal machine for the diagonalization) are carried out directly in this model in the proofs. The translations to the archive's single-tape and multi-stack models, used for the -hardness of WL Distinguishing, are .
Builds on
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments