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 model of computation whose state includes addressed numeric registers and a current program position.^[1]^[2] A finite program reads, changes, or tests register values; each instruction advances control or transfers it conditionally.^[1]^[2] A specified halting and output convention turns a run into a computed result.^[1]^[2] The model is a family, so neither indirect addressing nor a particular arithmetic repertoire belongs to every member. This entry synthesizes the shared structure of the Shepherdson–Sturgis unlimited-register machine (URM) and the Cook–Reckhow random-access machine (RAM) as a bounded genus.^[1]^[2]

The URM has a denumerable supply of natural-number registers, but each fixed finite program refers to only finitely many.^[1] Its operations include increment, decrement when defined, clear, copy and conditional control transfer; a decrement of zero is undefined in this specification.^[1] It halts on reaching a line beyond the program.^[1] In the authors' function-computation convention, defined inputs yield a final result in a designated register.^[1] The RAM instead has an unbounded indexed sequence of signed-integer registers, direct and indirect access, explicit READ/PRINT instructions, and a charge function for execution time.^[2] These are two different specifications of the same store–program–control pattern.

A register machine is an abstract machine. A physical processor happens to contain registers, but a collection of hardware cells alone supplies neither the formal instruction semantics nor a declared result convention. Conversely, an abstract machine can use a tape or stack without being a register machine. The indexed numeric store is the relevant difference, not the broad claim that the machine can calculate.

Structural Signature¶

Sig role-phrases: indexed numeric store → finite instruction program and control position → register operations and conditional tests → halting and output interpretation; optional resource-cost rule.

Addressed numeric store. Registers have distinguishable addresses and hold numeric state. The URM's values are natural numbers; the RAM's are signed integers.^[1]^[2] Removing the addressed numeric store changes the carrier, even if a tape model computes the same function.
Finite executable program and control position. Each examined model has a finite instruction program and a current line to execute.^[1]^[2] The available store may be unbounded although the written program is finite.^[1]^[2] Without executable control, the register array is data rather than a machine model.
Register operations and conditional transfer. Instructions change or inspect values, and tests can redirect execution.^[1]^[2] The repertoire varies: the URM uses directly named registers, while the RAM also reads addresses computed from register contents.^[1]^[2] Removing all operations leaves the store inert; removing conditional control leaves the computation-and-branching relation described here. Neither change by itself proves anything about the power of every alternative instruction set.
Halting and result convention. A computation must say when a run ends and what counts as its answer. The URM's designated output register differs from the RAM's PRINT tape; their halt rules also differ.^[1]^[2] The common role is an interpretation of a terminating state or output event, not a shared output device.
Optional cost convention. A computability question can ask whether a result is produced. A time-complexity question additionally needs a charge for instructions and number sizes. Cook and Reckhow compare constant and logarithmic charges.^[2] The choice affects time analysis without changing the RAM's underlying input/output rule.

What It Is Not¶

The name does not require that only finitely many register addresses exist. The URM has denumerably many available addresses but finitely many mentioned by one fixed program, and the RAM's indirect operations can reach unbounded addresses as inputs vary.^[1]^[2] Confusing the finiteness of a written program with finiteness of its potential store changes the model.

A register machine is also not synonymous with the RAM. Indirect addressing is central to Cook and Reckhow's specification but absent from the directly addressed URM case. Nor is it synonymous with every counter machine, which has a more restricted operation and access scheme. A bare CPU register, a numbered array without transition rules, and a tape-only Turing machine fail the bounded carrier-plus-program test.

Computational universality must be proved for a stated instruction repertoire. Shepherdson and Sturgis compare adequate minimal systems, but their results do not license the claim that any arbitrary set of register instructions computes all partial recursive functions.^[1] Their single-register word encoding is a distinct carrier result, not evidence that the indexed numeric-store genus can be identified with every one-register device. A stored-program RASP also needs its own source and typing treatment; it is not silently absorbed into the two fixed-program cases here.

Scope of Application¶

The model is useful in computability theory when an argument needs a finite, explicit program whose transitions can be simulated or encoded, and in algorithm and complexity analysis when the chosen register and cost conventions support a resource bound. Shepherdson and Sturgis construct routines for partial recursive functions on their URM; Cook and Reckhow specify a RAM and distinguish constant from logarithmic execution charges.^[1]^[2] A proof must name the particular machine variant before transferring a theorem about it.

The scope also includes comparisons between formal machine models: which data is stored in which addressed cell, which instruction can reach it, what terminates a run, and how its output is read. A high-level algorithm written in ordinary prose is not itself a register-machine program until these conventions are supplied. A hardware implementation may realize one, but the formal model abstracts from device-specific circuit details.

Clarity¶

The model separates three quantities that everyday language often blends: available registers, registers named in a finite program, and registers visited during a run. In the URM, the available supply is denumerable while a fixed program names finitely many. In the RAM, indirect addressing allows a fixed program to visit a number of registers that grows with the input.^[1]^[2] Stating which quantity is bounded prevents a false “finite memory” inference.

It also separates the rule for computation from the rule for measuring a computation. An instruction sequence can have the same input–output behavior under different time charges. Cook and Reckhow's logarithmic charge reflects the size of manipulated integers, while unit charge takes each instruction as constant.^[2]

Manages Complexity¶

Addressed cells and a small instruction vocabulary make a machine state decomposable: one can describe control location, relevant register contents, and the transition effected by one instruction. This supports local simulation arguments. Shepherdson and Sturgis deliberately use a flexible initial machine and then restrict operations to compare computational adequacy; the decomposition makes those reductions explicit.^[1]

The abstraction also exposes hidden assumptions in fast RAM reasoning. A program that uses indirect access can name an address stored as data, but a complexity claim still depends on how costly that address and the manipulated values are. Declaring the cost function turns an otherwise ambiguous performance statement into a model-relative one.^[2]

Abstract Reasoning¶

A register-machine run can be treated as a sequence of configurations. Each configuration pairs a control position with a valuation of the registers relevant to the run; an instruction gives a transition to the next configuration or a halting event. This formulation permits proofs by simulation: show how a routine preserves an intended invariant, maps inputs to the output convention, and terminates under the stated condition. The two source specifications supply the concrete operations; the configuration language here is an analytic restatement.^[1]^[2]

To transfer a theorem between variants, specify an encoding and show that each source step or routine has a target simulation. Computability equivalence is weaker than a time-preserving simulation: the latter also has to account for the size and cost of represented values. A claim of universal power or of a polynomial time bound therefore belongs to a named repertoire and charge convention, not to the label “register machine” alone.

Knowledge Transfer¶

The transferable method is to define the carrier, instructions, branch semantics, halt, and output before comparing computational behavior. That method applies when reading different formal models, even if a new model uses a different physical or logical carrier. The register-machine identity itself remains tied to indexed numeric cells. A tape model can share simulation techniques without becoming a register machine.

Within this family, the same method shows why a natural-number counter model and an integer-valued indirect-address RAM can be compared without being conflated. The shared roles support the comparison; their different address rules, input/output conventions and cost assumptions explain why a proof for one does not automatically establish a theorem about the other.

Examples¶

Canonical: Shepherdson–Sturgis URM¶

Begin with a finite numbered program and natural-number values in named registers from a denumerable supply.^[1] The current line executes an increment, a decrement if defined, a clear, a copy or a conditional transfer; decrement of zero is undefined.^[1] The machine halts when it reaches the nonexistent next line after the program.^[1] For a function computation, initial contents of selected registers are the arguments; on defined inputs, a designated register contains the result at halt.^[1] These directly named-register operations need no computed indirect address.^[1] The source-worked case has an unbounded available register supply despite a finite written program.

Mapped back: numeric addressed store → finite numbered program/control → direct register operations and tests → exit from the program → designated-register result.

Applied: Cook–Reckhow RAM for complexity analysis¶

Begin with a finite program, an infinite indexed sequence of integer-valued registers initialized to zero, and READ instructions for an input sequence.^[2] An indirect instruction can use a stored integer as a register address; a conditional transfer redirects control.^[2] PRINT writes output.^[2] The run halts on transfer to a nonexistent line or a negative indirect address.^[2] Choose the paper's logarithmic \(l(n)\) charge for this example, so integer size enters its running-time accounting.^[2] The paper also treats constant charge as a separate option.^[2]

Mapped back: integer addressed store → finite program/control → direct and indirect operations and branch → specified halt → READ/PRINT interpretation; logarithmic charge is an added analytic parameter.

Structural Tensions¶

Small primitive repertoire versus simple programs. Shepherdson and Sturgis show that adequate instruction systems can be reduced; the source does not by itself quantify the cost of every reduction.^[1] A smaller repertoire may require longer or less transparent simulations. Diagnostic: Which operations are primitive and which are implemented by routines?
Unbounded integer values versus realistic time charging. Arbitrarily large values simplify a formal store, while a unit charge can hide the work of representing them on bounded-word hardware.^[2] A logarithmic charge changes the time account without changing the transition's computed result. Diagnostic: What is \(l(n)\) for values used by this program?
Shared machine roles versus variant-specific theorems. The URM and RAM fit one structural description, yet indirect access, I/O and resource assumptions differ. A broad definition helps comparison only if it retains those differences where a theorem depends on them. Diagnostic: Which exact machine specification does the proof invoke?
Autonomous model versus reduction to abstract machine. “Abstract machine” captures formal configurations and transitions; the register-machine entry adds a numbered numeric-store carrier and a recognizable instruction family. The broader abstraction explains the genus without replacing these diagnostics. Diagnostic: Could the example use only tape or stack state and still pass the proposed register test?

Structural–Framed Character¶

The entry lies toward the structural end of the structural–framed spectrum, while retaining a domain-bound formal-computation identity. Its vocabulary partly travels: finite rules, state transitions and result interpretation apply outside theoretical computer science, but indexed numeric registers and instruction-level simulation do not travel without changing the test. It carries little evaluative weight: a machine specification describes what is computed and, under a cost model, how much a run costs; it does not declare that result good or bad. The entry is not constituted by a human institution or legal practice, although researchers choose conventions for instruction sets and charges. Human practice matters in specifying and proving the model, but the machine's formal execution is defined without a human operator at each step. Importing the name into a business ledger would be analogy; recognizing a URM or RAM from its specified registers, program, branching and result convention is literal classification.

The portable skeleton is the act of giving an exact rule-governed representation of state and transitions; that work belongs to the Prime Formalization in the verified Abstract Machine → Formal System → Formalization ancestor path. The register-machine entry additionally fixes an addressed numeric carrier and computation conventions. Its character: mostly structural within formal computation, with a narrow domain-specific carrier and semantics that prevent the named entry from becoming a cross-domain Prime.

Structural Core vs. Domain Accent¶

The skeletal relation is a finite rule system transforming a represented state under explicit control. Formalization is the live Prime that carries this portable exact-specification work through the proposed Abstract Machine and Formal System ancestor path; its edge closure is verified in the current graph. The machine-specific addition is an addressed numeric register carrier, instructions acting on that carrier, conditional control, and a halting/output interpretation. The URM and RAM use different values, addressing rules and resource charges while preserving these shared roles.^[1]^[2]

The domain accent is constitutive rather than decorative: a “register” here is a formally indexed numeric cell in a computational configuration. A business register can also hold values, but without executable instruction semantics and a result convention it fails the positive test. The name therefore does not clear the Prime bar merely because generic state and rules occur in many domains. The broader Prime explains why formal rules travel; this entry gives the narrower machine identity that lets a computability or complexity argument be checked.

This entry is a kind of Abstract Machine.

The typed parent is Abstract Machine, a broader domain-specific model with formal configurations and transitions that may use tape, stack or other carriers. A register machine specializes it with indexed numeric registers. The current-catalog typed graph check finds one strict subsumption edge from Register Machine to Abstract Machine and no new cycle.

The entry is related to the Prime Formalization because it makes execution rules explicit, and to Representation because a configuration encodes control and values. These are explanatory connections, not additional DAG edges. A register machine is not a kind of Random-Access Machine: the URM case lacks the latter's indirect addressing. Existing counter-machine and RAM entries remain separate narrower neighbor identities unless their own edges receive review.

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¶

Random-Access Machine. That is a member specification with indirect addressing and a declared instruction/cost scheme; it cannot stand for the entire family.^[2]
Counter-machine model. It highlights a restricted directly addressed counter/control repertoire; its existing article is a catalog neighbor, not source evidence for this new article.
Turing machine. It can compute many of the same functions, but a tape and moving head are a different state carrier.
Processor registers. Physical hardware may implement computations, but register cells alone do not define a formal program, control and result convention.
Stored-program RASP. Its program representation requires a separate variant analysis; it is outside the two fixed-program cases used to establish this bounded entry.

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 ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27

[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 ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27