Arbitrary memory emulation

Arbitrary memory emulation is a method of encoding 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 flat data structures like stacks, tapes, and arrays, and with modifications can encode more complex structures.

Structure

Additive AME

Let $A$ be the value which will be used for aAME. 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} , is Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S^{i}} , where dividing $A$ by $x$ results in the cell's value in memory, and multiplying any value Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v} by $x$ results in its relative value. Each cell is $S$ times higher than the previous one.

For any given memory structure Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M} with cells $[0,S)$ , $A$ is equivalent to Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sum _{i=0}^{|M|-1}M_{i}S^{i}} .

$S=100$
Array	$1$	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 15}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 32}
Relative position	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 100^{0}=1}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 100^{1}=100}	$100^{2}=10000$	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 100^{3}=1000000}
Relative value	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1\cdot 1=1}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 100\cdot 3=300}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 10000\cdot 15=150000}	$1000000\cdot 32=32000000$
Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A=1+300+150000+32000000=32150301}

Multiplicative AME

Let $A$ be the value which will be used for mAME. For each integer Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (-\infty ,\infty )} in memory with index $i$ , its relative value corresponds to the $i$ -th prime raised to its own value.

For any given memory structure Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M} with integers Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (-\infty ,\infty )} , $A$ is equivalent to $\prod _{i=0}^{|M|-1}\mathbb {P} _{i+1}^{M_{i}}$ .

Array	$1$	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 15}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 32}
Prime	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {P} _{1}=2}	$\mathbb {P} _{2}=3$	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {P} _{3}=5}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {P} _{4}=7}
Relative value	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{1}=2}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3^{3}=27}	Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 5^{1}5=30517578125}	$7^{3}2=1104427674243920646305299201$
Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A=1104427674243920676822877355}

Operations

Operation	Equation (aAME)	Equation (mAME)
$A_{\text{length}}$	$\left\lceil \log _{S}(A+1)\right\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.	Such a function is not possible to construct in mAME. Manual tracking is required instead.
$A_{\text{read}}(i)$	$\left\lfloor {\frac {A}{S^{i}}}\ \mathrm {mod} \ S\right\rfloor$	$\nu _{\mathbb {P} _{i+1}}(A)$
$A_{\text{write}}(i,v)$	$A=A-A_{\text{read}}(i)\cdot S^{i}+vS^{i}$	$A={\frac {A}{\mathbb {P} _{i+1}^{A_{\text{read}}(i)}}}\cdot \mathbb {P} _{i+1}^{v}$
$A_{\text{pushBottom}}(v)$	$A=AS+v$	$A=2^{v}+\prod _{i=0}^{A_{\text{length}}-1}\mathbb {P} _{i+2}^{A_{\text{read}}(i)}$
$A_{\text{pushTop}}(v)$	$A=A+vS^{A_{\text{length}}}$	$A=A+\mathbb {P} _{A_{\text{length}}}^{v}$
$A_{\text{popBottom}}()$	$A=\left\lfloor {\frac {A}{S}}\right\rfloor$	$A=\prod _{i=1}^{A_{\text{length}}-1}\mathbb {P} _{i}^{A_{\text{read}}(i)}$
$A_{\text{popTop}}()$	$A=A-A_{\text{read}}(A_{\text{length}}-1)S^{A_{\text{length}}-1}$	$A={\frac {A}{\mathbb {P} _{A_{\text{length}}}^{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.

In order for a target language to implement AME of either form, it must be able to calculate multiplication, division, and perform some sort of equality check against zero.

Variations

Payload-flag model (aAME)

A variation used by Funciton assigns a fixed length to each cell, reserving the last bit to continue the value into the next cell, allowing an unbounded size for each cell.^{[note 1]}

Each cell is split into a payload of size $P$ and a flag of size $F$ , both greater than one. The size of the flag determines how many unique states it has (e.g. $F=2$ for two distinct states). The true size of each cell, holding both the payload and flag, is $PF$ . To extract the payload and flag from a cell, the formulae $P_{\text{value}}=v\ \mathrm {mod} \ P$ and $F_{\text{value}}=\left\lfloor {\frac {v}{P}}\right\rfloor$ are used respectively.

For a simple example, and to match Funciton's case, take cells where $P=10$ and $F=2$ . When $F_{\text{value}}=1$ , the cell is denoted as having a value greater than $P$ , and the next few cells contain the entire amount. Given this, it can be calculated that any value $n$ will have to span $\left\lceil \log _{P}{n}\right\rceil$ cells, and the value of each cell $v_{i}$ is $\left\lfloor {\frac {n\ \mathrm {mod} \ P^{i+1}}{P^{i}}}\right\rfloor$ , adding an additional $P$ if $v_{i}$ is not the last cell.

$P=10;F=2;S=20$
Array	$5$	$13$		$24$		$119$
Size	$\left\lceil \log _{10}{5}\right\rceil =1$	$\left\lceil \log _{10}{13}\right\rceil =2$		$\left\lceil \log _{10}{24}\right\rceil =2$		$\left\lceil \log _{10}{119}\right\rceil =3$
Split form	$5$	$13\ \mathrm {mod} \ 10+10=13$	$\left\lfloor {\frac {13\ \mathrm {mod} \ 100}{10}}\right\rfloor =1$	$24\ \mathrm {mod} \ 10+10=14$	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left\lfloor \frac{24 \ \mathrm{mod} \ 100}{10} \right\rfloor = 2}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 119 \ \mathrm{mod} \ 10 + 10 = 19}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left\lfloor \frac{119 \ \mathrm{mod} \ 100}{10} \right\rfloor + 10 = 11}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left\lfloor \frac{119 \ \mathrm{mod} \ 1000}{100} \right\rfloor = 1}
Relative value	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^0 \cdot 5 = 5}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^1 \cdot 13 = 260}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^2 \cdot 1 = 400}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^3 \cdot 14 = 112000}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^4 \cdot 2 = 320000}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^5 \cdot 19 = 60800000}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^6 \cdot 11 = 704000000}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 20^7 \cdot 1 = 1280000000}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A = 2045232665}