One instruction set computer
A one instruction set computer (OISC), sometimes called an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode.^{[1]}^{[2]}^{[3]} With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.^{[2]}^{:55} OISCs have been recommended as aids in teaching computer architecture^{[1]}^{:327}^{[2]}^{:2} and have been used as computational models in structural computing research.^{[3]}
Contents
 1 Machine architecture
 2 Instruction types
 3 See also
 4 References
 5 External links
Machine architecture
In a Turingcomplete model, each memory location can store an arbitrary integer, and – depending on the model^{[clarification needed]} – 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.^{[4]}
Currently known OISCs can be roughly separated into three broad categories:
 Bitmanipulating machines
 Transport triggered architecture machines
 Arithmeticbased Turingcomplete machines
Bitmanipulating machines
Bitmanipulating machines are the simplest class.^{[clarification needed]}
BitBitJump
A bit copying machine, called BitBitJump, copies one bit in memory and passes the execution unconditionally to the address specified by one of the operands of the instruction. This process turns out to be capable of universal computation (i.e. being able to execute any algorithm and to interpret any other universal machine) because copying bits can conditionally modify the code that will be subsequently executed.
Toga computer
Another machine, called the Toga computer, inverts a bit and passes the execution conditionally depending on the result of inversion.
This section needs expansion. You can help by adding to it. (December 2016)

Multibit copying machine
Yet another bit operating machine,^{[which?]} similar to BitBitJump, copies several bits at the same time. The problem of computational universality is solved in this case by keeping predefined jump tables in the memory.^{[clarification needed]}
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 memorytomemory copy instruction, this is done by triggering ports that perform arithmetic and instruction pointer jumps when written to.
Arithmeticbased Turingcomplete machines
Arithmeticbased Turingcomplete machines use an arithmetic operation and a conditional jump. Like the two previous universal computers, this class is also Turingcomplete. 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)^{[5]}
 decrement (DJN, decrement and branch (jump) if nonzero)^{[6]}
 increment (P1eq, plus 1 and branch if equal to another value)^{[7]}
 subtraction (subleq, subtract and branch if less than or equal)^{[8]}^{[9]}
 subtraction when possible (Arithmetic machine)^{[10]}
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,^{[2]}^{:41} the SUBLEQ language,^{[3]}^{:4} etc.). Each of the above instructions can be used to construct a Turingcomplete OISC.
This article presents only subtractionbased instructions among those that are not transport triggered. However, it is possible to construct Turing complete machines using an instruction based on other arithmetic operations, e.g., addition. For example, one variation known as DLN (Decrement and jump if not zero) has only two operands and uses decrement as the base operation. For more information see Subleq derivative languages [1].
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}
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:
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.
Synthesized instructions
It is possible to synthesize many types of higherorder instructions using only the subleq instruction.^{[3]}^{:9–10}
Unconditional branch:
 JMP c
subleq Z, Z, c
Addition can be performed by repeated subtraction, with no conditional branching; e.g., the following instructions result in the content at location a being added to the content at location b:
 ADD a, b
subleq a, Z subleq Z, b subleq Z, Z
The first instruction subtracts the content at location a from the content at location Z (which is 0) and stores the result (which is the negative of the content at a) in location Z. The second instruction subtracts this result from b, storing in b this difference (which is now the sum of the contents originally at a and b); the third instruction restores the value 0 to Z.
A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location b getting replaced by the content at location a, again assuming the content at location Z is maintained as 0:
 MOV a, b
subleq b, b subleq a, Z subleq Z, b subleq Z, Z
Any desired arithmetic test can be built. For example, a branchifzero condition can be assembled from the following instructions:
 BEQ b, c
subleq b, Z, L1 subleq Z, Z, OUT L1: subleq Z, Z subleq Z, b, c OUT: ...
Subleq2 can also be used to synthesize higherorder instructions, although it generally requires more operations for a given task. For example, no fewer than 10 subleq2 instructions are required to flip all the bits in a given byte:
 NOT a
subleq2 tmp ; tmp = 0 (tmp = temporary register) subleq2 tmp subleq2 minus_one ; acc = 1 subleq2 a ; a' = a + 1 subleq2 Z ; Z =  a  1 subleq2 tmp ; tmp = a + 1 subleq2 a ; a' = 0 subleq2 tmp ; load tmp into acc subleq2 a ; a' =  a  1 ( = ~a ) subleq2 Z ; set Z back to 0
Emulation
The following program (written in pseudocode) emulates the execution of a subleqbased OISC:
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
This program assumes that memory[] is indexed by nonnegative integers. Consequently, for a subleq instruction (a, b, c), the program interprets a < 0, b < 0, or an executed branch to c < 0 as a halting condition. Similar interpreters written in a subleqbased language (i.e., selfinterpreters, which may use selfmodifying code as allowed by the nature of the subleq instruction) can be found in the external links below.
Compilation
There is a compiler called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into subleq code.^{[11]}
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}
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.
Synthesized instructions
It is possible to synthesize many types of higherorder instructions using only the subneg instruction. For simplicity, only one synthesized instruction is shown here to illustrate the difference between subleq and subneg.
Unconditional branch:^{[2]}^{:88–89}
 JMP c
subneg POS, Z, c ... c: subneg Z, Z
where Z and POS are locations previously set to contain 0 and a positive integer, respectively;
Unconditional branching is assured only if Z initially contains 0 (or a value less than the integer stored in POS). A followup instruction is required to clear Z after the branching, assuming that the content of Z must be maintained as 0.
A variant is also possible with four operands – subneg4. The reversal of minuend and subtrahend eases implementation in hardware. The nondestructive result simplifies the synthetic instructions.
subneg4 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. Melzac 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 next instruction.
If this operation is not possible because there is not enough counter in Y, then leave the abacus as it is an proceed to instruction T.
This essentially a subneg where the test is done before rather than after the subtraction, in order to keep all number positive and mimic a human operator computing on a real world abacus.
command X, Y, Z, T ; if (Mem[Y] < Mem[X]) goto T
; Mem[Z] = Mem[Y]  Mem[X]
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, Melzac shows explicitly how to simulate an arbitrary Turing machine on his Arithmetic Machine.
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 ^{[12]}on a 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]}
Example
To set x to the value of y minus z:
# 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]
[Note 1] If the value stored at "temp" is initially a negative value and the instruction that executed right before the first "RSSB temp" in this routine borrowed, then four "RSSB temp" instructions will be required for the routine to work.
[Note 2] If the value stored at "z" is initially a negative value then the final "RSSB x" will be skipped and thus the routine will not work.
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}^{[13]}
move a to b ; Mem[b] := Mem[a] (+, , *, /, ...) Mem[b]
sometimes written as:
a > b ; Mem[b] := 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, ifthenelse, forloop, 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.^{[14]}
Cryptoleq
Cryptoleq^{[15]} is a language consisting of one, the eponymous, instruction, is capable of performing generalpurpose 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_{1} and O_{2} on three values A, B, and C:
Cryptoleq a, b, c [b] = O_{1}([a],[b]) ; IP = c, if O_{2}[b] ≤ 0 IP = IP + 3, otherwise
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_{1} and O_{2} are defined as follows:
The main difference with Subleq is that in Subleq, O_{1}(x,y) simply subtracts y from x and O_{2}(x) equals to x. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of O_{2} 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 reencryption of a value based on the O_{2} operation:
where is the reencrypted value of y and is encrypted zero. x is the encrypted value of a variable, let it be m, and equals .
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.
See also
References
 ^ ^{a} ^{b} Mavaddat, F.; Parhami, B. (October 1988). "URISC: The Ultimate Reduced Instruction Set Computer" (PDF). Int'l J. Electrical Engineering Education. Manchester University Press. 25 (4): 327–334. Retrieved 20101004. This paper considers "a machine with a single 3address instruction as the ultimate in RISC design (URISC)". Without giving a name to the instruction, it describes a SBN OISC and its associated assembly language, emphasising that this is a universal (i.e., Turingcomplete) machine whose simplicity makes it ideal for classroom use.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Gilreath, William F.; Laplante, Phillip A. (2003). Computer Architecture: A Minimalist Perspective. Springer Science+Business Media. ISBN 9781402074165. Archived from the original on 20090613. Intended for researchers, computer system engineers, computational theorists and students, this book provides an indepth examination of various OISCs, including SBN and MOVE. It attributes SBN to W. L. van der Poel (1956).
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} Nürnberg, Peter J.; Wiil, Uffe K.; Hicks, David L. (September 2003), "A Grand Unified Theory for Structural Computing", Metainformatics: International Symposium, MIS 2003, Graz, Austria: Springer Science+Business Media, pp. 1–16, ISBN 9783540220107 This research paper focusses entirely on a SUBLEQ OISC and its associated assembly language, using the name SUBLEQ for "both the instruction and any language based upon it".
 ^ Oleg Mazonka, "Bit Copying: The Ultimate Computational Simplicity", Complex Systems Journal 2011, Vol 19, N3, pp. 263–285
 ^ "Addleq". Esolang Wiki. Retrieved 20170916.
 ^ "DJN OISC". Esolang Wiki. Retrieved 20170916.
 ^ "P1eq". Esolang Wiki. Retrieved 20170916.
 ^ Mazonka, Oleg (October 2009). "SUBLEQ". Archived from the original on 20170629. Retrieved 20170916.
 ^ "Subleq". Esolang Wiki. Retrieved 20170916.
 ^ Z. A. Melzak (1961). "An informal arithmetical approach to computability and computation". Canadian Mathematical Bulletin.
 ^ Oleg Mazonka A Simple MultiProcessor Computer Based on Subleq
 ^ J. Lambek (1961). "How to program an infinite abacus". Canadian Mathematical Bulletin.
 ^ Jones, Douglas W. (June 1988). "The Ultimate RISC". ACM SIGARCH Computer Architecture News. New York: ACM. 16 (3): 48–55. doi:10.1145/48675.48683. Retrieved 20101004. "Reduced instruction set computer architectures have attracted considerable interest since 1980. The ultimate RISC architecture presented here is an extreme yet simple illustration of such an architecture. It has only one instruction, move memory to memory, yet it is useful."
 ^ Catsoulis, John (2005), Designing embedded hardware (2 ed.), O'Reilly Media, pp. 327–333, ISBN 9780596007553
 ^ Mazonka, Oleg; Tsoutsos, Nektarios Georgios; Maniatakos, Michail (2016), Cryptoleq: A Heterogeneous Abstract Machine for Encrypted and Unencrypted Computation
External links
 Subleq on the esoteric programming languages wiki – interpreters, compilers, examples and derivative languages
 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 32bit OISC implementation – transport triggered architecture (TTA) on an FPGA using Verilog
 Introduction to the MAXQ Architecture – includes transfer map diagram
 OISCEmulator – graphical version
 TrapCC (recent Intel x86 MMUs are actually Turingcomplete OISCs.)
 SBN simulator – simulator and design inspired by CARDboard Illustrative Aid to Computation
 Onebit Computing at 60 Hertz – intermediate between a computer and a state machine
 The NOR Machine – info on building a CPU with only one Instruction
 Cryptoleq – Cryptoleq resources repository
 CAAMP – Computer Architecture A Minimalist Perspective
 DawnOS – an operating system for the SUBLEQ architecture