The deterministic time hierarchy theorem
Lax119563.TimeHierarchy · concepts/Lax119563/TimeHierarchy.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Hartmanis and Stearns; Hennie and Stearns: for every integer and every real , there is a language with
i.e., is decided by a deterministic multitape Turing machine in time , but by no deterministic multitape Turing machine in time .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 2 | import Lax119563.DeterministicTime |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The deterministic time hierarchy theorem |
| 7 | type: theorem |
| 8 | --- |
| 9 | Hartmanis and Stearns; Hennie and Stearns: for every integer and every real |
| 10 | , there is a language with |
| 11 | |
| 12 | i.e., is decided by a deterministic multitape Turing machine in time , |
| 13 | but by no deterministic multitape Turing machine in time . |
| 14 | |
| 15 | # Implementation notes |
| 16 | |
| 17 | The machine model is that of `Lax119563.DeterministicTime`; see there for why the exact |
| 18 | exponent of the main lower bound enters here and for the choice of the model. |
| 19 | -/ |
| 20 | |
| 21 | open Lax119563.DeterministicTime |
| 22 | |
| 23 | namespace Lax119563.TimeHierarchy |
| 24 | |
| 25 | /-- **The deterministic time hierarchy theorem** for polynomial time bounds. -/ |
| 26 | axiom time_hierarchy (s : ℕ) (hs : 1 ≤ s) (a : ℝ) (ha : a < s) : |
| 27 | ∃ L : Set (List Bool), |
| 28 | DecidableInTime L (fun n => (n : ℝ) ^ s) ∧ ¬ DecidableInTime L (fun n => (n : ℝ) ^ a) |
| 29 | |
| 30 | end Lax119563.TimeHierarchy |
| 31 |
Implementation notes
The machine model is that of ; see there for why the exact exponent of the main lower bound enters here and for the choice of the model.
Builds on
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