Flump

Flump is a Turing-complete OISC whose memory is an unbounded bitstring, and whose single instruction operates on one bit at a time. Flump was created by user "r.e.s." in 2009.

Memory

A flump machine uses a bitstring memory composed of the concatenation of 3(n+1) variable-length cells, where n is any fixed positive integer. Each cell is a finite-but-unbounded bitstring of the form '01..1' (that is, 0 followed by a nonnegative number of 1s), and the value of a cell is the (possibly zero) number of 1s in it. The cells are grouped into n+1 non-overlapping triplets, each triplet consisting of three consecutive cells. Any bit in memory is addressed by specifying a cell number i (≥ 0) together with the bit's offset j (≥ 0) relative to the leading 0 in that cell. Memory thus appears as follows:

                                     program                                          data
         ------------------------------------------------------------------    -------------------
memory  (01..1  01..1  01..1)(01..1  01..1  01..1) ... (01..1  01..1  01..1)  (01..1  01..1  01..1)
cell#    0      1      2      3      4      5           3n-3   3n-2   3n-1     3n     3n+1   3n+2
offsets  012..  012..  012..  012..  012..  012..  ...  012..  012..  012..    012..  012..  012..

The notation (i,j,k) will be used for a triplet whose cell values are as indicated, i.e. the bitstring 01..101..101..1, with the indicated number of 1s in each cell.

Programs and Data

In a flump machine with n+1 triplets, the leftmost n triplets comprise a program, each triplet being interpreted as a flump instruction. The remaining rightmost triplet contains data, initialised to the values (0,0,x), where the rightmost cell contains the program's input. When and if the program halts, the rightmost cell contains the program's output.

A triplet is executed when and if control is passed to its first cell during program execution. Flow of control is sequential starting at cell 0, and execution halts when and if control is passed to any cell outside the program (viz., to any cell# ≥ 3n).

The flump instruction

The flump instruction (i,j,k) is defined as follows:

flup the bit at offset j in cell i;
if the resulting value of cell i is zero then jump to cell k.  

The flup operation on a bit is defined as follows:

flup(1) = ε  (if it's a 1 then delete it)
flup(0) = 01 (if it's a 0 then insert 1 after it) 

("Flump" is a portmanteau of "flup" and "jump".)

Turing completeness

The two basic instructions of a Turing-complete Minsky machine with three registers can easily be simulated in flump using the following program fragments, where [i] denotes the value of any cell i.

increment [i]:  

(i,0,0)

if [i] = 0 then jump to cell k else decrement [i]:

(i,0,0)(i,1,k)(i,1,m)  

where cell m is the cell immediately after this program fragment 
and cell k is any cell not in this program fragment

The Minsky machine's three registers are directly simulated by flump's triplet of data cells.

Note that flump would be Turing-complete even if the offset were restricted to the two values 0 and 1, since those are the only offsets required in the above simulation. It's also notable that in the simulation the offset never exceeds the number of 1s in the cell (which would reference a bit outside the cell; that is, (i,1,k) never occurs when cell i has value 0.

Variants

By changing flump's halting criterion, other Turing-complete versions of flump may use an unbounded number of cells.

For example, with a criterion to stop execution when and if control passes to a triplet with offset value other than 0 or 1, the program segment of memory could be defined as extending from cell 0 rightward up to the first such "halting triplet", which would be the standard way of ending a program. The data segment could then be defined as all (unboundedly many) cells to the right of the program segment, starting with one or more data cells for input and output; all non-input data cells would be called into existence (having value 0) at the time they are first referenced during program execution. (Alternatively, the data segment could be said to have infinitely many cells, all of which are initialised at startup.)