Packed implicit parity systems for deterministic computations
Lax119563.PackedRepresentation · concepts/Lax119563/PackedRepresentation.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let be a deterministic multitape Turing machine, an input with , and a time horizon with and . For put
There is an implicit parity system with coordinate blocks over and locations and schemas that reaches a conflict if and only if accepts within steps. Its binary encoding can be constructed in time by a deterministic multitape Turing machine. The polynomial exponent is absolute, and the constants may depend on .
The system arises from a recursive simulation of deterministic computations due to Koucký (Shalunov, Appendix B): each recursive call simulates a time interval on a window of the tapes, the calls of one depth share their locations, and the addresses, packed into the data blocks, encode the call path and the position in the window.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Nat.Log |
| 2 | import Lax119563.BinaryEncodings |
| 3 | import Lax119563.DeterministicTime |
| 4 | import Lax119563.ImplicitParitySystems |
| 5 | import Lax119563.ImplicitSystemEncodings |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Packed implicit parity systems for deterministic computations |
| 10 | type: theorem |
| 11 | --- |
| 12 | Let be a deterministic multitape Turing machine, an input with |
| 13 | , and a time horizon with and . For |
| 14 | put |
| 15 | |
| 16 | |
| 17 | There is an implicit parity system with coordinate blocks over |
| 18 | and locations and schemas that reaches a conflict if and only if |
| 19 | accepts within steps. Its binary encoding can be constructed in time |
| 20 | by a deterministic multitape Turing machine. The polynomial exponent is |
| 21 | absolute, and the constants may depend on . |
| 22 | |
| 23 | The system arises from a recursive simulation of deterministic computations due to Koucký |
| 24 | (Shalunov, Appendix B): each |
| 25 | recursive call simulates a time interval on a window of the tapes, the calls of one depth |
| 26 | share their locations, and the addresses, packed into the data blocks, encode the call |
| 27 | path and the position in the window. |
| 28 | |
| 29 | # Implementation notes |
| 30 | * The system is a function `sys x h s` of the input, the horizon exponent and the number of |
| 31 | data blocks, with blocks of width = `packedWidth |x| h s`. |
| 32 | * The paper simulates exactly steps. Here the equivalence is stated for machines that |
| 33 | halt on within steps, the only case used: then the system reaches a conflict iff |
| 34 | accepts . |
| 35 | * One deterministic machine, depending on only, computes the encoding of the |
| 36 | system from the code of the list followed by , within steps, |
| 37 | where is absolute. |
| 38 | -/ |
| 39 | |
| 40 | open Lax119563.BinaryEncodings Lax119563.DeterministicTime |
| 41 | Lax119563.ImplicitParitySystems Lax119563.ImplicitSystemEncodings |
| 42 | open Lax489179.TuringMachine (Machine Deterministic) |
| 43 | |
| 44 | namespace Lax119563.PackedRepresentation |
| 45 | |
| 46 | /-- The block width `ℓ = max(⌈log₂(n + 2)⌉, ⌈(h + 2)/s⌉)`. -/ |
| 47 | def packedWidth (n h s : ℕ) : ℕ := max (Nat.clog 2 (n + 2)) ((h + 1 + s) / s) |
| 48 | |
| 49 | /-- **Packed representation.** For a deterministic machine `M` there are implicit parity |
| 50 | systems `sys x h s` with `s + 1` blocks of width `packedWidth |x| h s` and `O((h+1)^2)` |
| 51 | locations and schemas that reach a conflict iff `M` accepts `x` (if `M` halts on `x` within |
| 52 | `2^h` steps), and one machine computes their encodings in time `s 2^ℓ (h+1)^{O(1)}`. -/ |
| 53 | axiom packed_representation : ∃ c : ℕ, ∀ M : Machine, Deterministic M → |
| 54 | ∃ sys : (x : List Bool) → (h s : ℕ) → |
| 55 | ImplicitParitySystem (s + 1) (packedWidth x.length h s), |
| 56 | ∃ C : ℕ, |
| 57 | (∀ (x : List Bool) (h s : ℕ), 2 ≤ x.length → 2 ≤ h → x.length ≤ 2 ^ h → 2 ≤ s → |
| 58 | s ≤ h + 2 → |
| 59 | (HaltsWithin M x (2 ^ h) → |
| 60 | ((sys x h s).conflictRound < ⊤ ↔ Accepts M x)) ∧ |
| 61 | (sys x h s).numLocations ≤ C * (h + 1) ^ 2 ∧ |
| 62 | (sys x h s).schemas.length ≤ C * (h + 1) ^ 2) ∧ |
| 63 | ∃ R : Machine, Deterministic R ∧ |
| 64 | ∀ (x : List Bool) (h s : ℕ), 2 ≤ x.length → 2 ≤ h → x.length ≤ 2 ^ h → 2 ≤ s → |
| 65 | s ≤ h + 2 → |
| 66 | ComputesWithin R (encodeNats [h, s] ++ x) (encodeSystem (sys x h s)) |
| 67 | (C * s * 2 ^ packedWidth x.length h s * (h + 1) ^ c) |
| 68 | |
| 69 | end Lax119563.PackedRepresentation |
| 70 |
Implementation notes
- The system is a function of the input, the horizon exponent and the number of data blocks, with blocks of width = .
- The paper simulates exactly steps. Here the equivalence is stated for machines that halt on within steps, the only case used: then the system reaches a conflict iff accepts .
- One deterministic machine, depending on only, computes the encoding of the system from the code of the list followed by , within steps, where is absolute.
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