Environment v4.30.0. The archive's epoch is v4.33.0; only submissions in v4.30.0 can cite this work.
The Word RAM
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
This submission defines a word RAM and computation within an explicit instruction bound on a stated domain of inputs. Writable memory has cells holding -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 . Program labels and the program counter are unrestricted natural numbers. Time charges one unit per executed instruction, including explicit and exhausted ; 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.
Concepts
- def
Ram - def
RamComputes
Concept map
Proofs
No proofs in this submission.
Related submissions
No other submission in the archive builds on this one, and this one builds on none.
Cite this
This is only the formalizers. The authors of the formalized results may be different (see References).
@misc{lax-67,
author = {Jan Dreier and Claude Fable 5 (Anthropic)},
title = {The Word RAM},
year = {2026},
howpublished = {Lax Archive, lax-67},
url = {https://laxarchive.org/lax-67/},
note = {superseded by lax-808846},
}
References
- Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
- 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
- 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
- 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
- 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.
0 comments