RAM0

RAM0 is a computational model, created by Schönhage in 1990. It's notable for consisting of just a few basic commands that always do the same thing and take no parameters, plus flow control, as is used in many esoteric programming languages. However, its memory storage is based on an addressable RAM, rather than a tape (as is used by many imperative tarpits, such as P'').

Data storage

RAM0 has three places in which it can store data: an unbounded RAM (i.e. addressable memory) for which each cell can store unbounded nonnegative integers; and two registers, called n and z, which each store unbounded nonnegative integers. (It's simplest to assume that this memory is initially zero, although the language's computational class does not change even if the program can make no assumptions about the initial memory state.)

Commands and a suggested syntax

RAM0 has seven commands. Six have a single-letter name (and thus are most naturally represented by that letter in a program):

• Z: set z to 0
• A: increment z
• N: copy z to n, leaving z unchanged
• C: execute the next command only if z is nonzero
• L: read memory at address z, storing the result in z
• S: store the value z in memory at address n

The remaining command is a "goto" command, like in BASIC; this is the only command that takes an argument. As a computational model, RAM0 is not concerned with how this command is represented syntactically; however, a sensible option is for a decimal number i to represent a goto command that unconditionally jumps to the ith command in the program (using whitespace to separate two consecutive goto commands, and counting the first command as 1).

Comments are a detail of syntax irrelevant to computation, and thus do not appear when RAM0 is viewed as a model. Viewed as a language, it seems most consistent with similar esoteric programming languages for RAM0 to ignore anything it doesn't understand, allowing characters other than ZANCLS and digits to be used to write comments.

Computational class

It's clear that RAM0's control flow can create an arbitrary state machine (you can use fixed memory addresses as Boolean flags), so the only issue is reading and writing unbounded storage. The simplest way to do this is to use specific pairs of RAM cells as counters, with the difference between them storing the value of the counter; this is obviously trivial to increment and decrement. Testing a counter for zero (i.e. testing the two halves of the counter for equality) is harder, but if you start the cells' values sufficiently high that they do not correspond to any memory address used to store a counter, you can simply write a 0 to the address stored in the first half of the counter, a 1 to the address stored in the second half of the counter, and then read from the address stored in the first half; this will read a 1 only if the two counters are equal (because the second write will have overwritten the first). This can implement a Minsky machine, proving the language Turing complete (even if the initial contents of memory are unknown).

An alternative, and perhaps surprising, way to prove RAM0 Turing complete is to note that it's fairly trivial to compile Three Star Programmer without I/O into it: a Three Star Programmer command i translates to the run-length-decoding of Z(A)*iLLNLAS, with a 1 added at the end of the program (to put it into an infinite loop, matching the infinite loop around the Three Star Programmer program). Along similar lines, the I/D machine can also be directly compiled into RAM0.

This compilation does not use the C command, demonstrating that the language is Turing complete even without control flow (although Three Star Programmer has not been formally proven Turing complete, the I/D machine has been). It is also possible to remove the need to use the Z command, via replacing each A with AA and each Z with AL; with all values and memory indexes doubled, all odd-indexed RAM cells must contain zero, and therefore we can load the zeroes in them as a method of zeroing z. This leads to a tarpit consisting of only ANLS and an implicit infinite loop around the program.

Implementations

A Python interpreter by User:Bangyen.