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

Packed implicit parity systems for deterministic computations

Lax119563.PackedRepresentation · concepts/Lax119563/PackedRepresentation.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

    Let M\mathcal M be a deterministic multitape Turing machine, x∈{0,1}nx \in \{0, 1\}^n an input with n≥2n \geq 2, and T=2hT = 2^h a time horizon with h≥2h \geq 2 and n≤Tn \leq T. For 2≤s≤h+22 \leq s \leq h + 2 put

    ℓ=max⁡{⌈log⁡2(n+2)⌉,⌈h+2s⌉},Q=2ℓ.\ell = \max\left\{\lceil \log_2 (n + 2) \rceil, \left\lceil \frac{h + 2}{s} \right\rceil\right\}, \qquad Q = 2^\ell.

    There is an implicit parity system with k=s+1k = s + 1 coordinate blocks over F2ℓ\mathbb F_2^\ell and OM((h+1)2)O_{\mathcal M}((h + 1)^2) locations and schemas that reaches a conflict if and only if M\mathcal M accepts xx within TT steps. Its binary encoding can be constructed in time sQ(h+1)O(1)s Q (h + 1)^{O(1)} by a deterministic multitape Turing machine. The polynomial exponent is absolute, and the constants may depend on M\mathcal M.

    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 ss data blocks, encode the call path and the position in the window.

    Concept map
    9 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Data.Nat.Log
    2import Lax119563.BinaryEncodings
    3import Lax119563.DeterministicTime
    4import Lax119563.ImplicitParitySystems
    5import Lax119563.ImplicitSystemEncodings
    6
    7/-!
    8---
    9title: Packed implicit parity systems for deterministic computations
    10type: theorem
    11---
    12Let M\mathcal M be a deterministic multitape Turing machine, x∈{0,1}nx \in \{0, 1\}^n an input with
    13n≥2n \geq 2, and T=2hT = 2^h a time horizon with h≥2h \geq 2 and n≤Tn \leq T. For
    142≤s≤h+22 \leq s \leq h + 2 put
    15ℓ=max⁡{⌈log⁡2(n+2)⌉,⌈h+2s⌉},Q=2ℓ.\ell = \max\left\{\lceil \log_2 (n + 2) \rceil, \left\lceil \frac{h + 2}{s} \right\rceil\right\}, \qquad Q = 2^\ell.
    16
    17There is an implicit parity system with k=s+1k = s + 1 coordinate blocks over F2ℓ\mathbb F_2^\ell
    18and OM((h+1)2)O_{\mathcal M}((h + 1)^2) locations and schemas that reaches a conflict if and only if
    19M\mathcal M accepts xx within TT steps. Its binary encoding can be constructed in time
    20sQ(h+1)O(1)s Q (h + 1)^{O(1)} by a deterministic multitape Turing machine. The polynomial exponent is
    21absolute, and the constants may depend on M\mathcal M.
    22
    23The system arises from a recursive simulation of deterministic computations due to Koucký
    24(Shalunov, Appendix B): each
    25recursive call simulates a time interval on a window of the tapes, the calls of one depth
    26share their locations, and the addresses, packed into the ss data blocks, encode the call
    27path 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 k=s+1k = s + 1 blocks of width ℓ\ell = `packedWidth |x| h s`.
    32* The paper simulates exactly TT steps. Here the equivalence is stated for machines that
    33 halt on xx within TT steps, the only case used: then the system reaches a conflict iff
    34 M\mathcal M accepts xx.
    35* One deterministic machine, depending on M\mathcal M only, computes the encoding of the
    36 system from the code of the list h,sh, s followed by xx, within CsQ(h+1)cC s Q (h + 1)^c steps,
    37 where cc is absolute.
    38-/
    39
    40open Lax119563.BinaryEncodings Lax119563.DeterministicTime
    41 Lax119563.ImplicitParitySystems Lax119563.ImplicitSystemEncodings
    42open Lax489179.TuringMachine (Machine Deterministic)
    43
    44namespace Lax119563.PackedRepresentation
    45
    46/-- The block width `ℓ = max(⌈log₂(n + 2)⌉, ⌈(h + 2)/s⌉)`. -/
    47def 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
    50systems `sys x h s` with `s + 1` blocks of width `packedWidth |x| h s` and `O((h+1)^2)`
    51locations 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)}`. -/
    53axiom 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
    69end Lax119563.PackedRepresentation
    70
    Show Proof

    Implementation notes

    • The system is a function sysxhssys x h s of the input, the horizon exponent and the number of data blocks, with k=s+1k = s + 1 blocks of width ℓ\ell = packedWidth∣x∣hspackedWidth |x| h s.
    • The paper simulates exactly TT steps. Here the equivalence is stated for machines that halt on xx within TT steps, the only case used: then the system reaches a conflict iff M\mathcal M accepts xx.
    • One deterministic machine, depending on M\mathcal M only, computes the encoding of the system from the code of the list h,sh, s followed by xx, within CsQ(h+1)cC s Q (h + 1)^c steps, where cc is absolute.

    Discussion

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

    Loading discussion…