Random-Access Machine¶
Analyze algorithms on an abstract sequential computer with numbered registers and indirect addressing, making instruction set, word size, and operation-cost assumptions explicit.
Core Idea¶
A Random-Access Machine (RAM) is an abstract sequential model of computation with an unbounded collection of numbered registers, a finite program, and instructions that can access a register directly by an address in the instruction or indirectly by an address stored in another register. It idealizes the addressable-memory organization of conventional computers while remaining precise enough for proofs about algorithms and complexity.
The locked identity is finite control and instruction sequence + indexed register store + register contents drawn from a declared number or word domain + direct access + indirect addressing + deterministic instruction transition + input/output convention + explicit operation-cost measure. Indirect addressing is the decisive difference from a bare counter machine: a computed integer can designate which register an instruction reads or writes.
Scope of Application¶
RAM models are used in algorithm design, computational complexity, data-structure analysis, and machine-model comparison. They offer a closer match to conventional imperative programs than a single-tape Turing Machine because arrays and indexed storage are primitive. Cook and Reckhow used the model to establish simulation bounds between time-bounded RAMs and Turing machines and to formulate time hierarchy results.
Variants support different purposes. A unit-cost RAM is convenient for counting high-level operations when word sizes remain controlled. A logarithmic-cost RAM charges in relation to operand representation length and prevents arbitrary-precision arithmetic from being treated as free.
Clarity¶
“Random access” means access time is not proportional to the numerical distance between addresses. It does not mean stochastic choice. Register 10 and register one million are selected by the address mechanism rather than by walking through every intervening cell.
The model must declare its cost convention. Under unit cost, an addition may cost one step regardless of operand length. Under logarithmic cost, larger values cost more to manipulate.
Manages Complexity¶
The RAM abstraction makes familiar program operations available without committing to a physical processor. An array lookup becomes indirect register access. A loop becomes conditional jump and program-counter change. Data-structure algorithms can therefore be analyzed at a level that exposes key operations while suppressing transistor, cache, and operating-system detail.
Abstract Reasoning¶
- If a register contains address j, an indirect load can read register j without sequentially traversing lower addresses. 2. If a program uses only direct addresses appearing in its finite text, it cannot exploit the full unbounded store in an input-dependent way. 3. If an arbitrary-length multiplication costs one unit, a nominal step may perform work whose bit complexity grows with the input. 4.
Knowledge Transfer¶
The RAM abstraction transfers literally across algorithm and data-structure analyses that share its addressable-register contract. Variants can be compared by explicitly translating instructions and costs. It does not transfer literally to biological memory, organizational access, or physical storage latency.
The portable residue belongs to Representation, State Transition, Addressing, Indirection, Algorithm, and Cost Model. A warehouse locator system can use indirection, but it is not a Random-Access Machine without formal registers, instructions, configurations, and computation semantics.
Relationships to Other Abstractions¶
Current abstraction Random-Access Machine Domain-specific
Parents (1) — more general patterns this builds on
-
Random-Access Machine is a kind of Representation Prime
the machine stands in for a class of sequential computers and exposes only chosen resources.
Hierarchy path (1) — routes to 1 parentless root
- Random-Access Machine → Representation → Abstraction
Neighborhood in Abstraction Space¶
Random-Access Machine sits in a sparse region of the domain-specific corpus (94th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Blum–Shub–Smale Machine — 0.80
- Branch Table — 0.78
- Ludics — 0.77
- Turing Machine — 0.76
- Far Pointer — 0.76
Computed from structural-signature embeddings · 2026-09-08