While this submission is a draft, it cannot be used by other submissions.

Deterministic multitape Turing machines and running time

Lax119563.DeterministicTime · concepts/Lax119563/DeterministicTime.lean · lax-119563

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 00) contains the binary input xx at positions 0,…,∣x∣−10, \dots, |x| - 1, and all other cells are blank. Each transition, including the halting transition, takes one step, and halting returns a bit.

    • A machine halts within tt steps if it has returned its bit after tt steps.
    • A machine decides a property of the input within tt steps if it halts within tt steps and returns 11 exactly when the property holds. It accepts xx if it halts on xx and returns 11.
    • A machine computes yy from xx within tt steps if on input xx it halts within tt steps and, at that point, tape 00 contains exactly yy, laid out as an input would be: yy at positions 0,…,∣y∣−10, \dots, |y| - 1 and blanks elsewhere.
    • A language L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* is decidable in time O(f(n))O(f(n)) if some deterministic machine MM and constant CC are such that MM decides x∈Lx \in \mathcal L within Cf(∣x∣)+CC f(|x|) + C steps, for every xx.
    Concept map
    3 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Algebra.Order.Floor.Semiring
    2import Mathlib.Algebra.Order.Archimedean.Real.Basic
    3import Lax489179.TuringMachine
    4
    5/-!
    6---
    7title: Deterministic multitape Turing machines and running time
    8type: definition
    9---
    10We use deterministic multitape Turing machines with a finite number of tapes, symbols and
    11states, in which every transition reads the scanned symbols, writes one symbol per tape, and
    12moves each head by at most one cell. The cells of each tape are indexed by the integers; initially all heads
    13are at position zero, the first tape (tape 00) contains the binary input xx at positions
    140,…,∣x∣−10, \dots, |x| - 1, and all other cells are blank. Each transition, including the halting
    15transition, takes one step, and halting returns a bit.
    16
    17* A machine *halts within tt steps* if it has returned its bit after tt steps.
    18* A machine *decides* a property of the input *within tt steps* if it halts within tt steps
    19 and returns 11 exactly when the property holds. It *accepts* xx if it halts on xx and
    20 returns 11.
    21* A machine *computes yy from xx within tt steps* if on input xx it halts within tt
    22 steps and, at that point, tape 00 contains exactly yy, laid out as an input would be:
    23 yy at positions 0,…,∣y∣−10, \dots, |y| - 1 and blanks elsewhere.
    24* A language L⊆{0,1}∗\mathcal L \subseteq \{0, 1\}^* is decidable in time O(f(n))O(f(n)) if some
    25 deterministic machine MM and constant CC are such that MM decides x∈Lx \in \mathcal L
    26 within Cf(∣x∣)+CC f(|x|) + C steps, for every xx.
    27
    28# Implementation notes
    29
    30The machine model is the one of `Lax489179.TuringMachine`, restricted to deterministic
    31machines, whose transitions ignore the random bit. Their runs are evaluated with the
    32constant random bit `false`. Taking a step from a halted configuration does not change it, so
    33"halts within tt steps" means that the answer is present after tt steps.
    34
    35`Lax489179.TuringMachine.DecidesWithin` is the bounded-error notion of deciding for randomized
    36machines; for deterministic machines it agrees with `DecidesExactlyWithin`
    37(`Lax489179.DeterministicSemantics.turing_exact`).
    38
    39# Choice of machine model
    40
    41The time hierarchy theorem is the place where the exact exponent of the main lower
    42bound enters: Theorem `runtime_lower_bound` rules out running time O(Nk−1−ε)O(N^{k-1-\varepsilon}),
    43and that exponent depends on the machine model. Polynomially equivalent models are therefore
    44not 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 Ω(n2)\Omega(n^2) 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 O(nlog⁡cn)O(n \log^c n) only on several tapes, and the
    50 sharp hierarchy DTIME(na)⊊DTIME(ns)\mathsf{DTIME}(n^a) \subsetneq \mathsf{DTIME}(n^s) for every real
    51 a<sa < s 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 DTIME(ns)\mathsf{DTIME}(n^s) 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 nk−1−εn^{k-1-\varepsilon} from nk−1n^{k-1}. `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 00, 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
    88Neither mathlib nor the archive provides machine constructions for `Lax489179`, so those
    89needed here (composition, rewinding, the compiled reduction programs, and a universal machine
    90for the diagonalization) are carried out directly in this model in the proofs. The
    91translations to the archive's single-tape and multi-stack models, used for the
    92EXPTIME\mathsf{EXPTIME}-hardness of WL Distinguishing, are `Lax119563.MachineTranslations`.
    93-/
    94
    95open Lax489179.TuringMachine
    96
    97namespace Lax119563.DeterministicTime
    98
    99/-- The configuration of `M` after `t` steps on input `x`. -/
    100def 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. -/
    104def 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. -/
    109def 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`. -/
    113def 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`
    117holds `y` in the layout of an input. -/
    118def 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
    122machine. -/
    123def 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
    127end Lax119563.DeterministicTime
    128

    Implementation notes

    The machine model is the one of Lax489179.TuringMachineLax489179.TuringMachine, restricted to deterministic machines, whose transitions ignore the random bit. Their runs are evaluated with the constant random bit falsefalse. Taking a step from a halted configuration does not change it, so "halts within tt steps" means that the answer is present after tt steps.

    Lax489179.TuringMachine.DecidesWithinLax489179.TuringMachine.DecidesWithin is the bounded-error notion of deciding for randomized machines; for deterministic machines it agrees with DecidesExactlyWithinDecidesExactlyWithin (Lax489179.DeterministicSemantics.turingexactLax489179.DeterministicSemantics.turing_exact).

    Choice of machine model

    The time hierarchy theorem is the place where the exact exponent of the main lower bound enters: Theorem runtimelowerboundruntime_lower_bound rules out running time O(Nk−1−ε)O(N^{k-1-\varepsilon}), 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 (Turing.TM0Turing.TM0, Turing.TM1Turing.TM1). These are one-tape models. A single-tape machine needs Ω(n2)\Omega(n^2) steps for tasks that a two-tape machine does in linear time, such as recognizing palindromes or copying its input. Our reduction (built from packedrepresentationpacked_representation and matrixcompilermatrix_compiler) runs in quasi-linear time O(nlog⁡cn)O(n \log^c n) only on several tapes, and the sharp hierarchy DTIME(na)⊊DTIME(ns)\mathsf{DTIME}(n^a) \subsetneq \mathsf{DTIME}(n^s) for every real a<sa < s is a multitape statement.

    • Mathlib, multi-stack machines (Turing.FinTM2Turing.FinTM2 with TM2OutputsInTimeTM2OutputsInTime, TM2ComputableInTimeTM2ComputableInTime and TM2ComputableInPolyTimeTM2ComputableInPolyTime). 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 DTIME(ns)\mathsf{DTIME}(n^s) 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 Lax434930.PolynomialTime.PLax434930.PolynomialTime.P and Lax429075.Reductions.ManyOneLax429075.Reductions.ManyOne (built on mathlib's FinTM2FinTM2 in polynomial time), Lax759944.TuringPolytimeLax759944.TuringPolytime (the same, with equivalence to word RAMs), and Lax434930.ExponentialTime.EXPTIMELax434930.ExponentialTime.EXPTIME (a single-tape machine), only speak about polynomial or exponential time up to a polynomial. They cannot separate nk−1−εn^{k-1-\varepsilon} from nk−1n^{k-1}. Lax251941Lax251941 models single-tape machines as string rewriting, a representation meant for undecidability.

    • The fine-grained multitape model Lax489179.TuringMachineLax489179.TuringMachine (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 00, 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 (DeterministicDeterministic), whose transitions ignore the random bit.

    Neither mathlib nor the archive provides machine constructions for Lax489179Lax489179, 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 EXPTIME\mathsf{EXPTIME}-hardness of WL Distinguishing, are Lax119563.MachineTranslationsLax119563.MachineTranslations.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…