Register programs and RAM programs with unbounded natural-number memory

A register-memory state is a function $R:\mathbb{N}\to \mathbb{N}$ with finite support, so only finitely many registers hold nonzero values (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, The natural numbers $\mathbb{N}$ (von Neumann)).

A register program is a finite instruction list with a program counter, acting on such states by instructions of the following kinds:

• assignment of constants or copies, such as $R_i:=0$ and $R_i:=R_j$;
• successor and predecessor-type updates, such as $R_i:=R_j+1$ and $R_i:=\max (R_j-1,0)$;
• conditional branches testing whether a named register is zero;
• halting instructions for accept, reject, or output.

A RAM program is such a program together with indirect-addressing instructions $R_i:=R_{R_j},R_{R_i}:=R_j,$ so the content of one register may be used as the address of another. On this page, the phrase RAM/register program refers to this unbounded-memory model; a pure register program is the special case without indirect addressing.

For binary input $w=b_0\cdots b_{\mathrm{\ell }-1}$, the standard initial memory layout is $R(0)=\mathrm{\ell },R(i+1)=b_i(0\le i<\mathrm{\ell }),R(j)=0(j>\mathrm{\ell })\mathrm{.}$ A halting memory state outputs the binary word $u=c_0\cdots c_{m-1}$ when $R(0)=m,R(i+1)=c_i(0\le i<m),R(j)=0(j>m)\mathrm{.}$

• The memory is unbounded because there are countably many possible register addresses, but every individual configuration uses only finitely many nonzero entries.

• This item fixes a computability model, not a complexity convention. No unit-cost or logarithmic-cost claim is built into the definition.