◀ ▲ ▶Branches / Theoretical-computer-science / Computability / Definition: Unit-Cost Random Access Machine

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 one¹ 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.

Table of Contents

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

Mentioned in:

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!

Github:

References

Bibliography

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

Footnotes