Bit-manipulating machines

Bit-manipulating machines are the simplest class.

Transport triggered architecture

Transport triggered architecture (TTA) is a design in which computation is a side effect of data transport. Usually, some memory registers (triggering ports) within common address space perform an assigned operation when the instruction references them. For example, in an OISC using a single memory-to-memory copy instruction, this is done by triggering ports that perform arithmetic and instruction pointer jumps when written to.

Arithmetic-based Turing-complete machines

Arithmetic-based Turing-complete machines use an arithmetic operation and a conditional jump. Like the two previous universal computers, this class is also Turing-complete. The instruction operates on integers which may also be addresses in memory.

Currently there are several known OISCs of this class, based on different arithmetic operations:

• addition (addleq, add and branch if less than or equal to zero)^[6]
• decrement (DJN, Decrement and branch (Jump) if Nonzero)^[7]
• increment (P1eq, Plus 1 and branch if equal to another value)^[8]
• subtraction (subleq, subtract and branch if less than or equal to zero)^[9][10]
• positive subtraction when possible, else branch (Arithmetic machine)^[11]

Subtract and branch if not equal to zero

The SBNZ a, b, c, d instruction ("subtract and branch if not equal to zero") subtracts the contents at address a from the contents at address b, stores the result at address c, and then, if the result is not 0, transfers control to address d (if the result is equal to zero, execution proceeds to the next instruction in sequence).^[3]

Subtract and branch if less than or equal to zero

The subleq instruction ("subtract and branch if less than or equal to zero") subtracts the contents at address a from the contents at address b, stores the result at address b, and then, if the result is not positive, transfers control to address c (if the result is positive, execution proceeds to the next instruction in sequence).^[3]: 4–7 Pseudocode:

Instruction subleq a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] ≤ 0)
        goto c

Conditional branching can be suppressed by setting the third operand equal to the address of the next instruction in sequence. If the third operand is not written, this suppression is implied.

A variant is also possible with two operands and an internal accumulator, where the accumulator is subtracted from the memory location specified by the first operand. The result is stored in both the accumulator and the memory location, and the second operand specifies the branch address:

Instruction subleq2 a, b
    Mem[a] = Mem[a] - ACCUM
    ACCUM = Mem[a]
    if (Mem[a] ≤ 0)
        goto b

Although this uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations.

 int memory[], program_counter, a, b, c
 program_counter = 0
 while (program_counter >= 0):
     a = memory[program_counter]
     b = memory[program_counter+1]
     c = memory[program_counter+2]
     if (a < 0 or b < 0):
         program_counter = -1
     else:
         memory[b] = memory[b] - memory[a]
         if (memory[b] > 0):
             program_counter += 3
         else:
             program_counter = c

Subtract and branch if negative

The subneg instruction ("subtract and branch if negative"), also called SBN, is defined similarly to subleq:^{[2]: 41, 51–52}

Instruction subneg a, b, c
    Mem[b] = Mem[b] - Mem[a]
    if (Mem[b] < 0)
        goto c

Conditional branching can be suppressed by setting the third operand equal to the address of the next instruction in sequence. If the third operand is not written, this suppression is implied.

Instruction subneg s, m, r, j
    (* subtrahend, minuend, result and jump addresses *)
    Mem[r] = Mem[m] - Mem[s]
    if (Mem[r] < 0)
        goto j

Arithmetic machine

In an attempt to make Turing machine more intuitive, Z. A. Melzak consider the task of computing with positive numbers. The machine has an infinite abacus, an infinite number of counters (pebbles, tally sticks) initially at a special location S. The machine is able to do one operation:

Take from location X as many counters as there are in location Y and transfer them to location Z and proceed to instruction y.

If this operation is not possible because there is not enough counters in Y, then leave the abacus as it is and proceed to instruction n. ^[17]

In order to keep all numbers positive and mimic a human operator computing on a real world abacus, the test is performed before any subtraction. Pseudocode:

Instruction melzak X, Y, Z, n, y
    if (Mem[Y] < Mem[X])
        goto n
    Mem[X] -= Mem[Y]
    Mem[Z] += Mem[Y]
    goto y

After giving a few programs: multiplication, gcd, computing the n-th prime number, representation in base b of an arbitrary number, sorting in order of magnitude, Melzak shows explicitly how to simulate an arbitrary Turing machine on his arithmetic machine.

MUL p, q

multiply:
  melzak P, ONE, S, stop                ; Move 1 counter from P to S. If not possible, move to stop.
  melzak S, Q, ANS, multiply, multiply  ; Move q counters from S to ANS. Move to the first instruction.
stop:

where the memory location P is p, Q is q, ONE is 1, ANS is initially 0 and at the end pq, and S is a large number.

He mentions that it can easily be shown using the elements of recursive functions that every number calculable on the arithmetic machine is computable. A proof of which was given by Lambek^[18] on an equivalent two instruction machine : X+ (increment X) and X− else T (decrement X if it not empty, else jump to T).

Reverse subtract and skip if borrow

In a reverse subtract and skip if borrow (RSSB) instruction, the accumulator is subtracted from the memory location and the next instruction is skipped if there was a borrow (memory location was smaller than the accumulator). The result is stored in both the accumulator and the memory location. The program counter is mapped to memory location 0. The accumulator is mapped to memory location 1.^[2]

Instruction rssb x
    ACCUM = Mem[x] - ACCUM
    Mem[x] = ACCUM
    if (ACCUM < 0)
        goto PC + 2

# First, move z to the destination location x.
  RSSB temp # Three instructions required to clear acc, temp [See Note 1]
  RSSB temp
  RSSB temp
  RSSB x    # Two instructions clear acc, x, since acc is already clear
  RSSB x
  RSSB y    # Load y into acc: no borrow
  RSSB temp # Store -y into acc, temp: always borrow and skip
  RSSB temp # Skipped
  RSSB x    # Store y into x, acc
# Second, perform the operation.
  RSSB temp # Three instructions required to clear acc, temp
  RSSB temp
  RSSB temp
  RSSB z    # Load z
  RSSB x    # x = y - z [See Note 2]

Transport triggered architecture

A transport triggered architecture uses only the move instruction, hence it was originally called a "move machine". This instruction moves the contents of one memory location to another memory location combining with the current content of the new location:^{[2]: 42 [19]}

Instruction movx a, b (also written a -> b)
    OP = GetOperation(Mem[b])
    Mem[b] := OP(Mem[a], Mem[b])

The operation performed is defined by the destination memory cell. Some cells are specialized in addition, some other in multiplication, etc. So memory cells are not simple store but coupled with an arithmetic logic unit (ALU) setup to perform only one sort of operation with the current value of the cell. Some of the cells are control flow instructions to alter the program execution with jumps, conditional execution, subroutines, if-then-else, for-loop, etc...

A commercial transport triggered architecture microcontroller has been produced called MAXQ, which hides the apparent inconvenience of an OISC by using a "transfer map" that represents all possible destinations for the move instructions.^[20]

Cryptoleq

Cryptoleq processor made at NYU Abu Dhabi

Cryptoleq^[21] is a language consisting of one eponymous instruction, is capable of performing general-purpose computation on encrypted programs and is a close relative to Subleq. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations O₁ and O₂ on three values A, B, and C:

Instruction cryptoleq a, b, c
    Mem[b] = O1(Mem[a], Mem[b])
    if O2(Mem[b]) ≤ 0
        IP = c
    else
        IP = IP + 3

where a, b and c are addressed by the instruction pointer, IP, with the value of IP addressing a, IP + 1 point to b and IP + 2 to c.

In Cryptoleq operations O₁ and O₂ are defined as follows:

${\displaystyle {\begin{array}{lcl}O_{1}(x,y)&=&x_{N^{2}}^{-1}y\,{\bmod {\,}}N^{2}\end{array}}}$

${\displaystyle {\begin{array}{lcl}O_{2}(x)&=&\left\lfloor {\frac {x-1}{N}}\right\rfloor \end{array}}}$

The main difference with Subleq is that in Subleq, O₁(x,y) simply subtracts y from x and O₂(x) equals to x. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of O₂ corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. Cryptoleq though, implements fully homomorphic calculations and since the model is be able to do multiplications. Multiplication on an encrypted domain is assisted by a unique function G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the O₂ operation:

${\displaystyle G(x,y)={\begin{cases}{\tilde {0}},&{\text{if }}O_{2}({\bar {x}}){\text{ }}\leq 0\\{\tilde {y}},&{\text{otherwise}}\end{cases}}}$

where ${\displaystyle {\tilde {y}}}$ is the re-encrypted value of y and ${\displaystyle {\tilde {0}}}$ is encrypted zero. x is the encrypted value of a variable, let it be m, and ${\displaystyle {\bar {x}}}$ equals ${\displaystyle Nm+1}$.

The multiplication algorithm is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches. Cryptoleq encryption is based on Paillier cryptosystem.