Definition: Unit-Cost Random Access Machine

A Unit-Cost Random Access Machine (Unit-Cost \(R A M \)) is a model of computation with the following properties:

\((i)\) \(R A M \) contains finitely many registers \(r_1,\ldots,r_n\).

\((ii)\) Each register \(r_i\) can store exactly one1 natural number. \((iii)\) At the beginning of computation, each register contains an initial number, generally it is the number \(0\).

\((iv)\) The \(R A M\) machine contains either a \(L O O P\) program , or a \(W H I L E\) program, or a \(G O T O \) program.

  1. Theorem: Simulating LOOP Programs Using WHILE Programs
  2. Theorem: Simulating WHILE Programs Using GOTO Programs (and vice versa)
  3. Definition: LOOP Command, LOOP Program
  4. Definition: WHILE Command, WHILE Program
  5. Definition: GOTO Command, GOTO Program, Index
  6. Definition: LOOP-Computable Functions
  7. Definition: WHILE-Computable Functions
  8. Definition: GOTO-Computable Functions

Algorithms: 1 2 3 4 5 6 7 8
Definitions: 9 10 11 12 13 14

Thank you to the contributors under CC BY-SA 4.0!




  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition


  1. Note: Since the natural number can be arbitrarily big, we refer to the machine as unit-cost, since each register can store a natural number (at the same cost), no matter how big it is.