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

Translations between machine models

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

proven

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

    Theorem

    Our reductions are deterministic multitape Turing machines, while the archive's standard classes EXPTIME\mathsf{EXPTIME} and polynomial-time many-one reductions are defined with single-tape and multi-stack machines. Two simulations translate between them.

    1. Single-tape machines. A single-tape machine halting within TT steps on an input of length nn is simulated by a deterministic multitape machine in O(T+n)O(T + n) steps, with the same answer.
    2. Multi-stack machines. A function computed by a deterministic multitape machine in polynomial time is computable in polynomial time by a multi-stack machine.
    Concept map
    9 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Computability.TuringMachine.Computable
    2import Lax434930.ExponentialTime
    3import Lax119563.BinaryEncodings
    4import Lax119563.DeterministicTime
    5
    6/-!
    7---
    8title: Translations between machine models
    9type: theorem
    10---
    11Our reductions are deterministic multitape Turing machines, while the archive's standard
    12classes EXPTIME\mathsf{EXPTIME} and polynomial-time many-one reductions are defined with
    13single-tape and multi-stack machines. Two simulations translate between them.
    141. **Single-tape machines.** A single-tape machine halting within TT steps on an input of
    15 length nn is simulated by a deterministic multitape machine in O(T+n)O(T + n) steps, with the
    16 same answer.
    172. **Multi-stack machines.** A function computed by a deterministic multitape machine in
    18 polynomial time is computable in polynomial time by a multi-stack machine.
    19
    20# Implementation notes
    21* The single-tape machines are `Lax434930.MachineModels.SingleTape`, the model of the
    22 archive's `EXPTIME`, with halting and answer as in its definition.
    23* The multi-stack machines are mathlib's `Turing.FinTM2` in polynomial time,
    24 `Turing.TM2ComputableInPolyTime`, on `List Bool` with the identity encoding, as in the
    25 archive's many-one reductions `Lax429075.Reductions.ManyOne`.
    26-/
    27
    28open Lax119563.DeterministicTime
    29open Lax489179.TuringMachine (Machine Deterministic)
    30open Lax434930.MachineModels Turing
    31
    32namespace Lax119563.MachineTranslations
    33
    34/-- **Single-tape machines** are simulated by deterministic multitape machines with linear
    35overhead: if the single-tape machine `M₀` halts on `w` within `T` steps in the configuration
    36`c`, then `M` decides within `C (T + |w| + 1)` steps whether `M₀` accepts. -/
    37axiom singleTape_simulation (M₀ : SingleTape) :
    38 ∃ M : Machine, Deterministic M ∧ ∃ C : ℕ, ∀ (w : List Bool) (T : ℕ) (c : TM0.Cfg M₀.Γ M₀.Q),
    39 Nonempty (StateTransition.EvalsToInTime (TM0.step M₀.transition)
    40 (TM0.init (w.map M₀.input)) (some c) T) →
    41 TM0.step M₀.transition c = none →
    42 DecidesExactlyWithin M w (M₀.accept c.q = true) (C * (T + w.length + 1))
    43
    44/-- **Multi-stack machines.** A function on bit strings computed by a deterministic multitape
    45machine in polynomial time is computable in polynomial time by a multi-stack machine. -/
    46axiom tm2_of_polyTime {f : List Bool → List Bool} (R : Machine) (hR : Deterministic R)
    47 (C d : ℕ) (hf : ∀ x, ComputesWithin R x (f x) (C * (x.length + 1) ^ d)) :
    48 Nonempty (TM2ComputableInPolyTime id id f)
    49
    50end Lax119563.MachineTranslations
    51
    Show ProofShow Proof

    Implementation notes

    • The single-tape machines are Lax434930.MachineModels.SingleTapeLax434930.MachineModels.SingleTape, the model of the archive's EXPTIMEEXPTIME, with halting and answer as in its definition.
    • The multi-stack machines are mathlib's Turing.FinTM2Turing.FinTM2 in polynomial time, Turing.TM2ComputableInPolyTimeTuring.TM2ComputableInPolyTime, on ListBoolList Bool with the identity encoding, as in the archive's many-one reductions Lax429075.Reductions.ManyOneLax429075.Reductions.ManyOne.

    Discussion

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

    Loading discussion…