Version history

Submission versions

Newest first. “Current version” is the latest registered successor; drafts are identified separately.

  1. lax-67viewingdraft

    The Word RAM

    GitHub sourceShown on this page
  2. lax-13current version

    The Word RAM

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

Lax67.RamComputes

Computing a function within a time bound

concepts/Lax67/RamComputes.lean · lax-67

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

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    A word RAM program computes a function of words within a time bound T on a set D of admissible inputs if, started on any input x in D at word length w, it halts after at most T(x) instructions having written the value of the function at x to its output tape. The bound is a function of the input, so that bounds like "linear in the length of the input" are stated by instantiating T.

    Lean source view on GitHub

    1import Lax67.Ram
    2import Mathlib.Data.Set.Basic
    3
    4/-!
    5---
    6title: Computing a function within a time bound
    7type: definition
    8---
    9A word RAM program computes a function of words within a time bound *T*
    10on a set *D* of admissible inputs if, started on any input *x* in *D* at
    11word length *w*, it halts after at most *T(x)* instructions having written the
    12value of the function at *x* to its output tape. The bound is a function
    13of the input, so that bounds like "linear in the length of the input"
    14are stated by instantiating *T*.
    15
    16# Formalization notes
    17
    18The count includes explicit `halt` and exhausted `read`, but charges
    19nothing for an out-of-range program counter. Input is the supplied raw
    20list: there is no implicit header or marker. EOF testing and indexed
    21read-only input access, with original length metadata, are available
    22at unit cost, as specified in `Ram`. No initial input-loading scan is
    23charged. The complete append-only output must equal the function value.
    24
    25The number of instructions comes from the machine semantics, so a time bound is
    26a statement about the *program*: nothing is annotated onto the program
    27and then trusted. Only inputs in `D` are constrained; a program is free
    28to do anything at all on malformed input, which is what a statement
    29about an algorithm on encoded objects should say.
    30
    31The bound is stated elementarily — an explicit `T` that the step count
    32does not exceed — rather than through asymptotic notation. Asymptotics
    33would require a filter on inputs and would obscure, rather than clarify,
    34a statement that quantifies over encodings of every graph; a linear
    35bound is spelled out at the point of use as `c * (x.length + 1)` with an
    36explicit constant, a fixed-parameter bound as
    37`c * 2 ^ k * (x.length + 1)` with the parameter dependence written in,
    38the `+ 1` making both meaningful for the empty input as well.
    39
    40The word length `w` is an explicit argument, and statements built on
    41this notion quantify it visibly, in the order
    42`∃ p, ∀ …, ∀ w, (word-length hypothesis) → ComputesInTime w p D f T`.
    43The program is quantified *before* the word length: one program that
    44works at every sufficiently large word length, so that `w` cannot
    45smuggle advice into the machine — a program chosen after `w` could hide
    46an arbitrary amount of information in its literals. This is the same
    47uniformity discipline the quantifier order enforces for the parameter of
    48a fixed-parameter bound.
    49
    50Word-length hypotheses are written as explicit inequalities against
    51`2 ^ w` — `c * (x.length + 1) ≤ 2 ^ w`, or "every entry of `x` is less
    52than `2 ^ w`" — never through logarithms. This keeps the no-asymptotics
    53style of the surrounding statements and says exactly what a proof needs:
    54that the quantities the program manipulates fit into a word. Where
    55honesty requires it, the same fitting conditions appear in the
    56admissible set `D` itself, alongside the well-formedness conditions of
    57the encoding, since the machine reduces oversized input entries modulo
    58`2 ^ w` rather than rejecting them.
    59
    60Only the timed notion is defined: every statement built on this machine
    61carries a bound, and plain computability is the special case in which
    62`T` is unconstrained.
    63-/
    64
    65namespace Lax67.RamComputes
    66
    67open Lax67.Ram
    68
    69/-- At word length `w`, on every admissible input `x`, the program halts
    70within `T x` executed instructions with output `f x`. -/
    71def ComputesInTime (w : ℕ) (p : Program) (D : Set (List ℕ))
    72 (f : List ℕ → List ℕ) (T : List ℕ → ℕ) : Prop :=
    73 ∀ x ∈ D, ∃ t ≤ T x, RunsTo w p x (f x) t
    74
    75end Lax67.RamComputes
    76

    Formalization notes

    The count includes explicit halthalt and exhausted readread, but charges nothing for an out-of-range program counter. Input is the supplied raw list: there is no implicit header or marker. EOF testing and indexed read-only input access, with original length metadata, are available at unit cost, as specified in RamRam. No initial input-loading scan is charged. The complete append-only output must equal the function value.

    The number of instructions comes from the machine semantics, so a time bound is a statement about the program: nothing is annotated onto the program and then trusted. Only inputs in DD are constrained; a program is free to do anything at all on malformed input, which is what a statement about an algorithm on encoded objects should say.

    The bound is stated elementarily — an explicit TT that the step count does not exceed — rather than through asymptotic notation. Asymptotics would require a filter on inputs and would obscure, rather than clarify, a statement that quantifies over encodings of every graph; a linear bound is spelled out at the point of use as c(x.length+1)c * (x.length + 1) with an explicit constant, a fixed-parameter bound as c2k(x.length+1)c * 2 ^ k * (x.length + 1) with the parameter dependence written in, the +1+ 1 making both meaningful for the empty input as well.

    The word length ww is an explicit argument, and statements built on this notion quantify it visibly, in the order p,,w,(wordlengthhypothesis)ComputesInTimewpDfT∃ p, ∀ …, ∀ w, (word-length hypothesis) → ComputesInTime w p D f T. The program is quantified before the word length: one program that works at every sufficiently large word length, so that ww cannot smuggle advice into the machine — a program chosen after ww could hide an arbitrary amount of information in its literals. This is the same uniformity discipline the quantifier order enforces for the parameter of a fixed-parameter bound.

    Word-length hypotheses are written as explicit inequalities against 2w2 ^ wc(x.length+1)2wc * (x.length + 1) ≤ 2 ^ w, or "every entry of xx is less than 2w2 ^ w" — never through logarithms. This keeps the no-asymptotics style of the surrounding statements and says exactly what a proof needs: that the quantities the program manipulates fit into a word. Where honesty requires it, the same fitting conditions appear in the admissible set DD itself, alongside the well-formedness conditions of the encoding, since the machine reduces oversized input entries modulo 2w2 ^ w rather than rejecting them.

    Only the timed notion is defined: every statement built on this machine carries a bound, and plain computability is the special case in which TT is unconstrained.

    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…