One-instruction set computer

A one-instruction set computer (OISC), sometimes referred to as an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instructionobviating the need for a machine language opcode.

Machine architecture

In a Turing-complete model, each memory location can store an arbitrary integer, anddepending on the mode, there may be arbitrarily many locations. The instructions themselves reside in memory as a sequence of such integers.

There exists a class of universal computers with a single instruction based on bit manipulation such as bit copying or bit inversion. Since their memory model is finite, as is the memory structure used in real computers, those bit manipulation machines are equivalent to real computers rather than to Turing machines.

Currently known OISCs can be roughly separated into three broad categories:

Bit-manipulating machines
Transport triggered architecture machines
Arithmetic-based Turing-complete machines

Bit-manipulating machines

Bit-manipulating machines are the simplest class.

FlipJump

The FlipJump machine has 1 instruction, a;b - flips the bit a, then jumps to b. This is the most primitive OISC, but it's still useful. It can successfully do math/logic calculations, branching, pointers, and calling functions with the help of its standard library.

BitBitJump

A bit copying machine,

decrement (DJN, Decrement and branch (Jump) if Nonzero)
increment (P1eq, Plus 1 and branch if equal to another value)
subtraction (subleq, subtract and branch if less than or equal to zero)
positive subtraction when possible, else branch (Arithmetic machine)

Instruction types

Common choices for the single instruction are:

Subtract and branch if less than or equal to zero
Subtract and branch if negative
Subtract if positive else branch
Reverse subtract and skip if borrow
Move (used as part of a transport triggered architecture)

Subtract and branch if non zero (SBNZ a, b, c, destination)
Cryptoleq (heterogeneous encrypted and unencrypted computation)

Only one of these instructions is used in a given implementation. Hence, there is no need for an opcode to identify which instruction to execute; the choice of instruction is inherent in the design of the machine, and an OISC is typically named after the instruction it uses (e.g., an SBN OISC,

A 32-bit Subleq computer with a graphic display and a keyboard called Izhora has been constructed by Yoel Matveyev as a large cellular automaton pattern.

Compilation

There is a compiler called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into code.

Alternatively there is a self hosting Forth implementation written by Richard James Howe that runs on top of a Subleq VM and is capable of interactive programming of the Subleq machine

Subtract and branch if negative

The instruction ("subtract and branch if negative"), also called , is defined similarly to :</blockquote>

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 <syntaxhighlight lang="nasm" inline>melzak X, Y, Z, n, y</syntaxhighlight>

if (Mem[X] < Mem[Y])

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.

;

:<syntaxhighlight lang="nasm">

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:

</syntaxhighlight>

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 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.

External links

Subleq on the esoteric programming languages wiki – interpreters, compilers, examples and derivative languages
by Christopher Domas
Laboratory subleq computer – FPGA implementation using VHDL
The Retrocomputing Museum – SBN emulator and sample programs
Laboratory SBN computer – implemented with 7400 series integrated circuits
RSSB on the esoteric programming languages wiki – interpreters and examples
Dr. Dobb's 32-bit OISC implementation – transport triggered architecture (TTA) on an FPGA using Verilog
Introduction to the MAXQ Architecture – includes transfer map diagram
OISC-Emulator – graphical version
TrapCC (recent Intel x86 MMUs are actually Turing-complete OISCs.)
Izhora – Yoel Matveyev's Subleq computer built as a cellular automation
SBN simulator – simulator and design inspired by CARDboard Illustrative Aid to Computation
One-bit Computing at 60 Hertz – intermediate between a computer and a state machine
The NOR Machineinfo on building a CPU with only one Instruction
SUBLEQ eFORTH A complete Forth interpreter running on the SUBLEQ OISC.
CryptoleqCryptoleq resources repository
CAAMPComputer Architecture A Minimalist Perspective
SICO – Single Instruction COmputer: a variant of SUBLEQ using unsigned integers