Version history

Submission versions

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

  1. lax-67draft

    The Word RAM

  2. lax-13current versionviewing

    The Word RAM

    GitHub sourceShown on this page

Lax13.RamComputes

Computing a function within a time bound

concepts/Lax13/RamComputes.lean · lax-13

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) steps 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 Lax13.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)* steps 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 number of steps is the machine's own step count, so a time bound is
    19a statement about the *program*: nothing is annotated onto the program
    20and then trusted. Only inputs in `D` are constrained; a program is free
    21to do anything at all on malformed input, which is what a statement
    22about an algorithm on encoded objects should say.
    23
    24The bound is stated elementarily — an explicit `T` that the step count
    25does not exceed — rather than through asymptotic notation. Asymptotics
    26would require a filter on inputs and would obscure, rather than clarify,
    27a statement that quantifies over encodings of every graph; a linear
    28bound is spelled out at the point of use as `c * (x.length + 1)` with an
    29explicit constant, a fixed-parameter bound as
    30`c * 2 ^ k * (x.length + 1)` with the parameter dependence written in,
    31the `+ 1` making both meaningful for the empty input as well.
    32
    33The word length `w` is an explicit argument, and statements built on
    34this notion quantify it visibly, in the order
    35`∃ p, ∀ …, ∀ w, (word-length hypothesis) → ComputesInTime w p D f T`.
    36The program is quantified *before* the word length: one program that
    37works at every sufficiently large word length, so that `w` cannot
    38smuggle advice into the machine — a program chosen after `w` could hide
    39an arbitrary amount of information in its literals. This is the same
    40uniformity discipline the quantifier order enforces for the parameter of
    41a fixed-parameter bound.
    42
    43Word-length hypotheses are written as explicit inequalities against
    44`2 ^ w` — `c * (x.length + 1) ≤ 2 ^ w`, or "every entry of `x` is less
    45than `2 ^ w`" — never through logarithms. This keeps the no-asymptotics
    46style of the surrounding statements and says exactly what a proof needs:
    47that the quantities the program manipulates fit into a word. Where
    48honesty requires it, the same fitting conditions appear in the
    49admissible set `D` itself, alongside the well-formedness conditions of
    50the encoding, since the machine reduces oversized input entries modulo
    51`2 ^ w` rather than rejecting them.
    52
    53Only the timed notion is defined: every statement built on this machine
    54carries a bound, and plain computability is the special case in which
    55`T` is unconstrained.
    56-/
    57
    58namespace Lax13.RamComputes
    59
    60open Lax13.Ram
    61
    62/-- At word length `w`, on every admissible input `x`, the program halts
    63within `T x` steps with output `f x`. -/
    64def ComputesInTime (w : ℕ) (p : Program) (D : Set (List ℕ))
    65 (f : List ℕ → List ℕ) (T : List ℕ → ℕ) : Prop :=
    66 ∀ x ∈ D, ∃ t ≤ T x, RunsTo w p x (f x) t
    67
    68end Lax13.RamComputes
    69

    Formalization notes

    The number of steps is the machine's own step count, 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…