Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax195003.WordRamRandomness

Randomized computation on the word RAM

concepts/Lax195003/WordRamRandomness.lean · lax-195003

definition

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.

    Concept map

    Open claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    A randomized word-RAM computation is a deterministic word-RAM program whose ordinary input is followed by a finite tape of independent uniform random bits. Given a rational threshold q, it succeeds with probability at least q within time T if every random tape makes the program halt within T steps, and at least a q fraction of the equally likely bit strings make it halt with an accepted output.

    Lean source view on GitHub

    1import Lax67.Ram
    2import Mathlib.Data.Rat.Cast.Order
    3import Mathlib.Data.Set.Card
    4
    5/-!
    6---
    7title: Randomized computation on the word RAM
    8type: definition
    9---
    10A randomized word-RAM computation is a deterministic word-RAM program whose
    11ordinary input is followed by a finite tape of independent uniform random
    12bits. Given a rational threshold *q*, it succeeds with probability at least
    13*q* within time *T* if every random tape makes the program halt within *T*
    14steps, and at least a *q* fraction of the equally likely bit strings make it
    15halt with an accepted output.
    16
    17# Formalization notes
    18
    19The machine itself is exactly the word RAM of Lax67; randomness is input, not
    20a new primitive instruction. A random tape of length `r` is a function
    21`Fin r → Bool`, encoded in index order by the words zero and one. There are
    22exactly `2 ^ r` such tapes. For a rational success threshold `q`, the
    23inequality `q · 2^r ≤ |good tapes|` states the probability bound without
    24introducing a measure-theoretic representation of a finite experiment. The
    25Welzl-order theorem instantiates `q` with `2/3`.
    26
    27The definition separates total running time from success: every tape must
    28halt within the bound, while a bad tape may return any output. The accepting
    29condition is a relation on output words because a search algorithm may return
    30any one of many correct witnesses. Supplying more bits than a program reads
    31does not alter the success fraction—each used prefix has equally many
    32extensions—so a theorem may use its time bound itself as a uniform tape
    33length without exposing an implementation-specific random-bit count.
    34-/
    35
    36namespace Lax195003.WordRamRandomness
    37
    38open Lax67.Ram
    39
    40/-- A bit tape as a word list, in index order, with `false` encoded by zero
    41and `true` by one. -/
    42def bitTape {r : ℕ} (ρ : Fin r → Bool) : List ℕ :=
    43 List.ofFn (fun i : Fin r => if ρ i then 1 else 0)
    44
    45/-- The program halts within `T` steps on every `r`-bit tape, and on at least
    46a `successProbability` fraction of those tapes its output satisfies `Accept`. -/
    47noncomputable def SucceedsWithProbabilityAtLeastInTime
    48 (successProbability : ℚ) (w : ℕ) (p : Program)
    49 (input : List ℕ) (r T : ℕ)
    50 (Accept : List ℕ → Prop) : Prop :=
    51 (∀ ρ : Fin r → Bool, ∃ y : List ℕ, ∃ t ≤ T,
    52 RunsTo w p (input ++ bitTape ρ) y t) ∧
    53 successProbability * (2 ^ r : ℚ) ≤
    54 ({ρ : Fin r → Bool | ∃ y : List ℕ, ∃ t ≤ T,
    55 RunsTo w p (input ++ bitTape ρ) y t ∧ Accept y}.ncard : ℚ)
    56
    57end Lax195003.WordRamRandomness
    58

    Formalization notes

    The machine itself is exactly the word RAM of Lax67; randomness is input, not a new primitive instruction. A random tape of length rr is a function FinrBoolFin r → Bool, encoded in index order by the words zero and one. There are exactly 2r2 ^ r such tapes. For a rational success threshold qq, the inequality q2rgoodtapesq · 2^r ≤ |good tapes| states the probability bound without introducing a measure-theoretic representation of a finite experiment. The Welzl-order theorem instantiates qq with 2/32/3.

    The definition separates total running time from success: every tape must halt within the bound, while a bad tape may return any output. The accepting condition is a relation on output words because a search algorithm may return any one of many correct witnesses. Supplying more bits than a program reads does not alter the success fraction—each used prefix has equally many extensions—so a theorem may use its time bound itself as a uniform tape length without exposing an implementation-specific random-bit count.

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…