Arbitrary memory emulation

Note: This assumes that numbers are integers that aren't bound to a maximum and can have infinite precision up to infinity.

General idea

Given access to a single number, arbitrary memory is able to be properly emulated given simple algorithms. The idea is that:

1. Each memory slot never exceeds some given "byte" value, like 255. In more regular terms, a byte of memory is at most 255.
   • Unlike traditional memory, this byte size can be any arbitrary number, like 10, given the math is handled correctly. We'll call this value $S$.
2. The position of any byte where $x$ is its index in memory (starting at 0), its position as a number will be $S^{x}$.
   • For any byte's value $v$, it's actual value will be $v*S^{x}$. For example, if v was 5, $S$ was 8 and $x$ was 5, byte 5's contribution to the number (or it's actual value) will be $5*8^{5}$, or 163840.
3. Every byte of memory is always $S$ higher than the previous one, and conversely every byte of memory is always $S$ below the previous one.
   • More generally, for any given byte, and their indexes $x$ and $y$, the position of byte $X$ will always be $S^{|x-y|}$

For example, we'll use a byte size of 2 and memory of [1, 1, 0, 1, 0, 0, 0, 1].

1. Start with a total of 0.
2. Go through each value in memory and add $n*2^{i}$ to the total, where $n$ is the value and $i$ is the index.
3. Our memory is encoded as 139.

As a second example: with a byte size of 10 and memory of [9, 5, 1, 2, 4, 3, 8], our memory (or total) is 8342159.

Or, with a byte size of 256 and a memory of [75, 113, 92, 3, 0, 66, 17, 214]: 15425182766544482635.

Reading and writing

Reading and writing from memory can be done through simple algorithms.

Any memory byte can be read through the algorithm $\left\lfloor {\frac {T}{S^{n}}}\right\rfloor \ \mathrm {mod} \ S$, where $T$ is the memory as the total from earlier, $S$ is the byte size, and $n$ is the index.

Any memory byte can be written to through the algorithm $T=T-\mathrm {read} (n)S^{n}+vS^{n}$, where $v$ is the value to set to.

Turing-completeness

In most cases, a language is considered Turing-complete if it can access an unbounded amount of memory—typically through structures like a tape or a pair of stacks, where it doesn’t matter how small each memory cell is, as long as there are infinitely many.

AME inverts this idea. Instead of requiring unbounded memory space, it relies on unbounded cell capacity. If even a single memory cell can store values of unlimited size, and the language allows the necessary arithmetic operations, then this can be sufficient for Turing-completeness regardless of how many cells exist.

This assumes, however, that the language can perform mathematical operations (like exponentiation, division, and modulo) directly on the unbounded value without relying on additional memory. In many languages, such operations are not possible without access to more than one cell.

Usage

AME was used to prove Iterate Turing-complete via emulation of arrays to simulate BCT.