Translations between machine models
Lax119563.MachineTranslations · concepts/Lax119563/MachineTranslations.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Our reductions are deterministic multitape Turing machines, while the archive's standard classes and polynomial-time many-one reductions are defined with single-tape and multi-stack machines. Two simulations translate between them.
- Single-tape machines. A single-tape machine halting within steps on an input of length is simulated by a deterministic multitape machine in steps, with the same answer.
- 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
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Computability.TuringMachine.Computable |
| 2 | import Lax434930.ExponentialTime |
| 3 | import Lax119563.BinaryEncodings |
| 4 | import Lax119563.DeterministicTime |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Translations between machine models |
| 9 | type: theorem |
| 10 | --- |
| 11 | Our reductions are deterministic multitape Turing machines, while the archive's standard |
| 12 | classes and polynomial-time many-one reductions are defined with |
| 13 | single-tape and multi-stack machines. Two simulations translate between them. |
| 14 | 1. **Single-tape machines.** A single-tape machine halting within steps on an input of |
| 15 | length is simulated by a deterministic multitape machine in steps, with the |
| 16 | same answer. |
| 17 | 2. **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 | |
| 28 | open Lax119563.DeterministicTime |
| 29 | open Lax489179.TuringMachine (Machine Deterministic) |
| 30 | open Lax434930.MachineModels Turing |
| 31 | |
| 32 | namespace Lax119563.MachineTranslations |
| 33 | |
| 34 | /-- **Single-tape machines** are simulated by deterministic multitape machines with linear |
| 35 | overhead: 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. -/ |
| 37 | axiom 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 |
| 45 | machine in polynomial time is computable in polynomial time by a multi-stack machine. -/ |
| 46 | axiom 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 | |
| 50 | end Lax119563.MachineTranslations |
| 51 |
Implementation notes
- The single-tape machines are , the model of the archive's , with halting and answer as in its definition.
- The multi-stack machines are mathlib's in polynomial time, , on with the identity encoding, as in the archive's many-one reductions .
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments