# Trying to make sense of the operations in a particular Random Access Machine (RAM)

[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\}$$:

(4.1)

$$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?

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$$.
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.
• 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. Dec 21, 2022 at 8:10
• 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. Dec 22, 2022 at 8:43