Register Machine¶

A formal computation model that executes a finite instruction program over addressed numeric registers, with register operations, conditional control, and an explicit result convention.

Version: v1 · 2026-10-25 · History
Domain-specific #: 14434
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Models of Computation → Computer Science & Software Engineering

Core Idea¶

A register machine is a formal way to describe a computation.^[1]^[2] It has numbered places to store numbers, a finite program, and a rule for which instruction runs next.^[1]^[2] Instructions can change a register, test it, or branch to another instruction.^[1]^[2] A complete machine specification also says when a run stops and how its answer is read.^[1]^[2]

The name covers more than one exact machine. Shepherdson and Sturgis describe an unlimited-register machine (URM) with natural-number values and directly named registers.^[1] Cook and Reckhow describe a random-access machine (RAM) with signed-integer registers, indirect addressing, and explicit input and output instructions.^[1]^[2] These differences matter when a proof depends on a particular instruction set or time charge.

Scope of Application¶

Use the model when a computability proof needs a precise program and step rule, or when a complexity argument needs to count the cost of steps. The available register supply can be unbounded even though the written program is finite.^[1]^[2] In the URM, a fixed program names finitely many of its denumerably many possible registers.^[1] In the RAM, indirect addressing can reach further addresses during a run.^[1]^[2]

Clarity¶

Keep four questions separate: What values can registers hold? Which instructions exist? What ends the run? Where is the result? The URM's result is read from a designated register at halt; the RAM can PRINT output.^[1]^[2] An ordinary processor register, without a formal program and result rule, does not answer these questions.

Manages Complexity¶

The model reduces an execution to a sequence of explicit configurations: current instruction plus register contents. One can inspect a branch, simulate a routine, or prove what it computes. A separate cost convention then lets a complexity argument account for large numbers. Cook and Reckhow compare constant and logarithmic charges; changing the charge can change the reported time without changing what the program outputs.^[2]

Abstract Reasoning¶

To compare two programs or machine families, first fix their allowed instructions, addressing, halt rule, and output rule. Then ask whether one simulates the other. Shared register storage alone does not establish identical computational power or running time. Shepherdson and Sturgis prove results for specified adequate instruction systems, not for every imaginable set of register operations.^[1]

Knowledge Transfer¶

The useful habit is to state the carrier, operations, control, halt, and output before drawing conclusions about an algorithm. That habit transfers to other formal computation models. A tape machine can use similar proof methods but remains a different kind of carrier, so it is not a register machine merely by analogy.

Examples¶

URM. A finite numbered program acts on natural-number registers.^[1] Its source-defined operations include increment, defined decrement, clear, copy, and conditional transfer.^[1] Reaching the line after the program halts the run; the designated register supplies a function result.^[1] Mapped back: addressed numeric store → finite instruction program → register operations and branch → halt → designated output.

RAM. Cook and Reckhow's machine has integer-valued indexed registers, READ and PRINT, and instructions that may address a register indirectly.^[2] The model also specifies charges for time analysis.^[2] Mapped back: addressed numeric store → finite program and control → direct or indirect operations → specified halt and output; cost is an additional analytic rule.

Relationships to Other Abstractions¶

Current abstraction Register Machine Domain-specific

Parents (1) — outgoing typed relations

Register Machine is a kind of Abstract Machine Domain-specific

A register machine is an abstract machine whose formally specified configurations include indexed numeric register values and a program-control position.

Hierarchy paths (2) — routes to 2 parentless roots

Register Machine → is a kind of Abstract Machine → includes Formal System → presupposes Formalization → presupposes Representation → presupposes Abstraction

Show alternative path (1)

Neighborhood in Abstraction Space¶

Register Machine sits in a moderately populated region (56^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Processor Architecture & Instruction Sets (9 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With¶

A Random-Access Machine is one more specific member, not the whole register-machine family. An Abstract Machine is broader: it may use tapes or stacks instead of indexed numeric registers. A stored-program RASP needs separate treatment because how it represents a program differs from the fixed-program cases here. The bounded Register Machine identity has one strict parent edge to Abstract Machine; this does not add edges to the existing counter-machine or RAM entries.

References¶

[1] J. C. Shepherdson and H. E. Sturgis, “Computability of Recursive Functions,” Journal of the ACM 10, no. 2 (1963): 217–255, especially §2, printed pp. 219–220; §3, p. 222; and Appendix A, pp. 244–246. Original full text: https://www.cs.cmu.edu/~cdm/resources/ShepherdsonSturgis1963.pdf registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[2] Stephen A. Cook and Robert A. Reckhow, “Time Bounded Random Access Machines,” Journal of Computer and System Sciences 7, no. 4 (1973): 354–375, especially §1 and Table I, pp. 354–356. Author-hosted original full text: https://www.cs.utoronto.ca/~sacook/homepage/rams.pdf registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k