Version history

Submission versions

  1. lax-808846current versionviewing

    The Word RAM

    GitHub sourceShown on this page
  2. lax-67

    The Word RAM

  3. lax-13

    The Word RAM

The Word RAM

lax-808846·formalized by Jan Dreier · Claude Fable 5 (Anthropic)·registered·created ·GitHub @9394e53·Lean v4.33.0 epoch · mathlib db584cd6d46c·

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

    This submission defines a word RAM and computation within an explicit instruction bound on a stated domain of inputs. Writable memory has 2w2 ^ w cells holding ww-bit words and starts at zero. The read-only input is a finite array supplied at initialization, with constant-time indexed access and length metadata, a sequential read operation, and an explicit end-of-input test. Zero remains ordinary input data. Output is append-only, and correctness constrains the complete output list.

    Arithmetic values, input values and lengths, input indices, and data-memory addresses are reduced modulo 2w2 ^ w. Program labels and the program counter are unrestricted natural numbers. Time charges one unit per executed instruction, including explicit halthalt and exhausted readread; falling outside the program costs no nonexistent instruction. The formalization notes state fitting conditions, the input-access convention, the additive linear cost of loading sequential input when comparing models, and the distinction from Cook and Reckhow's terminated input encoding. The proof package provides compiler transfer theorems, a verified execution driver, and semantic regression proofs for raw-list length parity, constant-time indexed input access, and exact termination costs.

    In the paper

    • page 1 of the paper of lax-117284, Fair Repetitive Interval Scheduling
    • page 2 of the paper of lax-345332, NP-Hardness of (3,4)-SAT and [2,3]-Bounded 3-SAT
    • page 6 of the paper of lax-391470, Scheduling with Two Non-Unit Job Lengths Is NP-Complete
    • page 1 of the paper of lax-496464, Just-in-Time Scheduling in Two-Stage Flexible Flow Shops
    • page 1 of the paper of lax-888481, Interval Scheduling with Eligible Machine Sets

    Concepts

    Concept map
    2 concepts
    100%
    DefinitionThis submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    No proofs in this submission.

    Related submissions

    Submission map

    100%
    Linear Programming: Duality, Certificates,and Polynomial-Time OptimizationAlgorithmic Experiments on a RandomAccess MachineFair Repetitive Interval SchedulingFirst-Order Model Checking on MonadicallyDependent Graph ClassesNear-Linear Time Computation of WelzlOrders on Graphs with Linear NeighborhoodComplexityApproximation algorithmsWelzl Orders of CographsConstructing Welzl Orders: Algorithm andCorrectnessAn Introduction to LaxQPTAS for Max Weight Independent Set inGraphs with Strongly Edge-SublinearSeparatorsAlgorithmic Experiments on a RandomAccess MachineFirst-Order Model Checking on NowhereDense Graph Classes in Almost Linear TimeGraph Classes and Width ParametersNP-Hardness of (3,4)-SAT and [2,3]-Bounded3-SATScheduling with Two Non-Unit Job LengthsIs NP-CompleteScheduling problems assembled fromconstraint modulesMulticommodity Flow–Cut Theorems ofLeighton and RaoRefined Near-Linear Computation of WelzlOrdersTight Inapproximability of Max IndependentSet in Triangle-Free GraphsInterval Scheduling with Eligible MachineSetsETH, SETH, Weighted APSP, and 3SUMJust-in-Time Scheduling in Two-StageFlexible Flow ShopsCertified structural representations of finitedataTight Inapproximability of Max IndependentSet in Triangle-Free GraphsA Refinement Framework for the Word RAMFinding Tree Decompositions of SmallTreewidthComputability and polynomial-timeequivalence of Turing machines and wordRAMsProof network stress testThe Word RAMGraph Parameters and Functional RelationsMSO and tree automata on finite rankedtreesInterval Scheduling with Eligible MachineSetsExplicit Subcubic Expanders and LinearTreewidth
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

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

    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.

    Discussion

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

    Loading discussion…