Arbitrary memory emulation

Arbitrary memory emulation is a form of memory which, given a value that can be infinite in size without precision loss, allows for arbitrary memory in the event that such is not possible normally. AME can be used to emulate data structures which hold values sequentially, like stacks, tapes, or arrays.

Structure

Let $A$ be the value which will be used for AME. We define a positive integer $S$ greater than 1 which will denote the maximum size of each "cell" in memory, where a cell can have an integer value of $[0,S)$. The index of each cell is denoted as $i$. The relative position of each cell in memory, denoted by $x$, is $S^{i}$, where dividing $A$ by $x$ results in the cell's value in memory, and multiplying any value $v$ by $x$ results in its relative value. Each cell is $S$ times higher than the previous one.

For any given memory structure $M$ with cells $[0,S)$, $A$ is equivalent to $\sum _{i=0}^{|M|-1}M_{i}S^{i}$.

Operations

Operation	Equation
$A_{\text{length}}$	$\lceil \log _{S}(A+1)\rceil$ Note that this algorithm is unreliable if $A$ stores any trailing zeroes. It is more reliable to manually track this value by incrementing or decrementing $A_{\text{length}}$ as values are added or removed.
$A_{\text{read}}(i)$	$\lfloor {\frac {A}{S^{i}}}\ \mathrm {mod} \ S\rfloor$
$A_{\text{write}}(i,v)$	$A=A-A_{\text{read}}(i)\cdot S^{i}+vS^{i}$
$A_{\text{pushBottom}}(v)$	$A=AS+v$
$A_{\text{pushTop}}(v)$	$A=A+vS^{A_{\text{length}}}$
$A_{\text{popBottom}}()$	$A=\lfloor {\frac {A}{S}}\rfloor$
$A_{\text{popTop}}()$	$A=A-A_{\text{read}}(A_{\text{length}}-1)$

Turing-completeness

A typical requirement for Turing-completeness is that the language has access to unbounded memory, regardless of the size of each cell. AME "flips" this case, where values of infinite size can be used for computational power, regardless of how many memory addresses there actually are. However, this requires that the language is able to handle values of infinite size without precision loss, and the language has the necessary space in order to compute and thereafter process and transform the memory.

Usage

• AME is used in Iterate to simulate Bitwise Cyclic Tag with a queue.
• AME is used in Laconic and NQL programs to emulate stacks using natural numbers.