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

The Word RAM

lax-13·formalized by Jan Dreier·Claude Fable 5 (Anthropic)·registered·created 2026-08-02·GitHub @92ae2d6·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    The word RAM is the machine the modern analysis of algorithms is stated on. It is a random access machine in the register-transfer format of Cook and Reckhow — a memory of cells addressed by number and no other storage, an instruction that sets one cell from one or two others, indirect addressing through a cell holding an address, an input and an output tape, jumps against zero — with its numbers bounded rather than its instruction set: cells hold ww-bit words, and multiplication, division, shifts and the bitwise operations each cost one time unit because on words each of them is one instruction of a real machine. This submission fixes the archive's canonical encoding of that model. It carries two definitions and no proof obligations: the machine, whose semantics is parameterized by the word length and obeys one uniform truncation rule — every value the machine produces and every address it uses is taken modulo 2w2 ^ w — and the predicate saying that a program computes a function of words within a time bound on a set of admissible inputs, the running time being the machine's own step count rather than an annotation carried alongside the program. Neither is a claim, so neither is stated as one; the review question is faithfulness of the model, and the formalization notes give the word model and its sources, the truncation rule and what follows from it, the constant-cost derivations of the remaining standard operations — disjunction, exclusive or, the right shift, the remainder and the comparisons — and the machine's halting behaviour and time measure.

    Statements about algorithms are then made downstream, over these two concepts, in a fixed shape: one program is quantified before the word length, so that a claim is about a single program uniform in ww and no advice can be smuggled in, and the hypotheses on the word length are explicit inequalities against 2w2 ^ w rather than logarithms. The proof package discharges nothing — there is nothing to discharge — and instead carries a reusable verified pipeline for the submissions that will: a structured while-language with named scalars and arrays whose big-step semantics counts the statements it executes, a compiler into machine code, a simulation theorem bounding the machine's step count by a constant multiple of that cost provided every intermediate value fits into a word, and a reasoning layer of Hoare-style rules with a cost potential and compositional value bounds. The word length enters that pipeline exactly once, at its boundary, so an algorithm is verified on clean unbounded natural-number semantics and lands as a running-time claim about this machine. The refinement framework built on that pipeline — the port of the Isabelle NREST/Autoref/Sepref stack through which algorithms verified against abstract specifications descend to this machine — is the separate submission A Refinement Framework for the Word RAM, which requires this proof package.

    Concepts

    defdefinition

    Concept map

    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    No proofs in this submission.

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    @misc{lax-13,
      author = {Jan Dreier and Claude Fable 5 (Anthropic)},
      title = {The Word RAM},
      year = {2026},
      howpublished = {Lax Archive, lax-13},
      url = {https://laxarchive.org/lax-13/},
    }

    References

    1. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
    2. Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences 7(4):354–375, 1973. doi:10.1016/S0022-0000(73)80029-7
    3. Torben Hagerup. Sorting and searching on the word RAM. In STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science 1373:366–398, 1998. doi:10.1007/BFb0028575
    4. Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences 47(3):424–436, 1993. doi:10.1016/0022-0000(93)90040-4
    5. Peter van Emde Boas. Machine models and simulations. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity 1–66, 1990.

    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…