Computing a function within a time bound

Lax808846.RamComputes · concepts/Lax808846/RamComputes.lean · lax-808846

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.

    Natural Language Statement

    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.

    Concept map
    2 concepts; 23 descendants hidden
    100%
    Proven claimOpen claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax808846.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 Lax808846.RamComputes
    66
    67open Lax808846.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 Lax808846.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.

    Discussion

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

    Loading discussion…