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