[I couldn't find the right tag for this post]

Following is the description of some random access machine

We use the algorithmic model of the random access machine, sometimes ab- breviated to RAM. It operates on entries that are 0, 1 strings, representing abstract objects (like vertices of a graph) or rational numbers. An instruc- tion can read several (but a fixed number of) entries simultaneously, perform arithmetic operations on them, and store the answers in array positions pre- scribed by the instruction2. The array positions that should be read and written, are given in locations prescribed by the instruction. We give a more precise description. The random access machine has a finite set of variables $z_0, . . . , z_k$ and one array, $f$ say, of length depending on the input. Each array entry is a $0, 1$ string. They can be interpreted as rationals, in some binary encoding, but can also have a different meaning. Initially, $z_0, . . . , z_k$ are set to $0$, and $f$ contains the input. Each instruction is a finite sequence of resettings of one the following types, for $i, j, h ∈ \{1, . . . , k\}$:


$z_i := f (z_j )$;

$f (z_j ) := z_i$;

$z_i := z_j + z_h$;

$z_i := z_j − z_h$;

$z_i := z_j z_h$;

$z_i := z_j /z_h$;

$z_i := z_i + 1$;

$z_i := 1$ if $z_j > 0$ and $z_i := 0$ otherwise.

These include the elementary arithmetic operations: addition, subtraction, multiplication, division, comparison. (One may derive other arithmetic op- erations from this like rounding and taking logarithm or square root, by performing $O(σ + | log ε|)$ elementary arithmetic operations, where σ is the size of the rational number and $ε$ is the required precision.) The instructions are numbered $0, 1, . > . . , t$, and $z1$ is the number of the instruction to be executed. $If z1 > t$ we stop and return the contents of the array $f$ as output.

I know nothing about random access machines and in particular I don't understand what the operations $z_i := f (z_j )$; $f (z_j ) := z_i$; are. Does it mean we take the element at the $z_j$-th index of the array $f$? How are these two operations used in practice in an algorithm?


1 Answer 1


There exists a wide variety of RAM models that are, to some extent, equivalent. Here, it seems that the operation $f(z_i)=z_j$ means settings the value of the cell at index $z_i$ in the array $f$ to the value of $z_j$ and conversely $z_i=f(z_i)$ means loading the value of the cell $z_i$ in the array $f$ into the variable $z_i$.

I am not sure I understand your question about how to use this in practice? Here the model is quite simplistic but it does look like an assembly language. Maybe you want to look into compilation to understand how to turn a high level language into such a low level language?

To develop on my remark about assembly (if you are used to assembly) you can consider that the $z_1 \dots z_k$ represent the registers while the array $f$ models the RAM memory and $z_1$ can be used to jump to any point in the program.

  • $\begingroup$ I think this answers my question, thank you very much. I just thought that $z_1,\ldots, z_k$ beeing the registers is kind of weird since $z_i=f(z_j)$ means that $z_i$ is the register but $z_j$ is the index of the register in the RAM. Don't you think it is weird too? Also I thought a program returns some result and in this case it returns the full RAM, which gets me a bit confused. $\endgroup$
    – roi_saumon
    Dec 21, 2022 at 8:10
  • $\begingroup$ If you consider a standard programming language, when you have variables $a,b,c$ and an array $f$, you do write stuff like $f[a] = b$ and $a=f]b]$. Here it might feel weird because you have parenthesis instead of brackets but otherwise it can be read as a standard program. $\endgroup$
    – Louis
    Dec 22, 2022 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.