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
Concept map
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
Cite this
@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 = {draft},
}
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.
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