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 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 S} .
2. The position of any byte where 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 its index in memory (starting at 0), its position as a number will be 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 S^x} .
   • For any byte's 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 v} , it's actual value will be 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 v * S^x} . For example, if v was 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 S} was 8 and 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} was 5, byte 5's contribution to the number (or it's actual value) will be 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 5 * 8^5} , or 163840.
3. Every byte of memory is always 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 S} higher than the previous one, and conversely every byte of memory is always 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 S} below the previous one.
   • More generally, for any given byte, and their indexes 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} and 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 y} , the position of byte 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} will always be 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 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 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 n * 2^i} to the total, where 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 n} is the value and 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 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 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{T}{S^n}}\right\rfloor\ \mathrm{mod}\ S} , where 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 T} is the memory as the total from earlier, 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 S} is the byte size, and 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 n} is the index.

Any memory byte can be written to through the algorithm 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 T = T - \mathrm{read}(n) S^n + vS^n} , where 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 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.