View source for One-instruction set computer

{{Short description|Abstract machine that uses only one instruction}}
{{Distinguish|1-bit computing}}
A '''one-instruction set computer''' ('''OISC'''), sometimes referred to as an '''ultimate [[RISC|reduced instruction set computer]]''' ('''URISC'''), is an [[abstract machine]] that uses only one instruction{{snd}}obviating the need for a [[machine language]] [[opcode]].<ref name=urisc /><ref name=caamp /><ref name=agut /> With a judicious choice for the single instruction and given arbitrarily many resources, an OISC is capable of being a [[universal computer]] in the same manner as traditional computers that have multiple instructions.<ref name=caamp />{{rp|55}} OISCs have been recommended as aids in teaching computer architecture<ref name=urisc />{{rp|327}}<ref name=caamp />{{rp|2}} and have been used as computational models in structural computing research.<ref name=agut /> The first [[carbon nanotube computer]] is a [[1-bit computing|1-bit]] one-instruction set computer (and has only 178 transistors).<ref>{{cite web | url=https://www.bbc.co.uk/news/science-environment-24232896 | title=First computer made of carbon nanotubes is unveiled | publisher=BBC | date=26 September 2013 | accessdate=26 September 2013}}</ref>

== Machine architecture ==
In a [[Turing completeness|Turing-complete model]], each memory location can store an arbitrary integer, and{{snd}}depending 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 computer]]s 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.<ref name="mazonka">Oleg Mazonka, [http://www.complex-systems.com/pdf/19-3-5.pdf "Bit Copying: The Ultimate Computational Simplicity"], Complex Systems Journal 2011, Vol 19, N3, pp. 263–285</ref>

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 manipulation|Bit-manipulating]] machines are the simplest class.

==== FlipJump ====
The [https://esolangs.org/wiki/FlipJump 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,<ref name="mazonka" /> 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 copying address that will be subsequently executed.

==== Toga computer ====
Another machine, called the [https://esolangs.org/wiki/TOGA_computer Toga Computer], inverts a bit and passes the execution conditionally depending on the result of inversion. The unique instruction is TOGA(a,b) which stands for '''TOG'''gle ''a'' '''A'''nd branch to ''b'' if the result of the toggle operation is true.

{{Expand section|date=December 2016}}

==== Multi-bit copying machine ====
Similar to BitBitJump, a multi-bit copying machine copies several bits at the same time. The problem of [[Turing completeness|computational universality]] is solved in this case by keeping predefined jump tables in the memory.{{clarify|not apparent how this solves anything and what criterion is being used here?|date=December 2016}}

=== 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, <u>add</u> and branch if <u>l</u>ess than or <u>eq</u>ual to zero)<ref name="esolang-addleq">{{cite web |url=https://esolangs.org/wiki/Addleq|title=Addleq|author=<!--Not stated--> |website=Esolang Wiki|access-date=2017-09-16}}</ref>
* decrement (DJN, <u>D</u>ecrement and branch (<u>J</u>ump) if <u>N</u>onzero)<ref name="esolang-djn">{{cite web |url=https://esolangs.org/wiki/DJN_OISC|title=DJN OISC|author=<!--Not stated--> |website=Esolang Wiki|access-date=2017-09-16}}</ref>
* increment (P1eq, <u>P</u>lus <u>1</u> and branch if <u>eq</u>ual to another value)<ref name="esolang-p1eq">{{cite web |url=https://esolangs.org/wiki/P1eq|title=P1eq|author=<!--Not stated--> |website=Esolang Wiki|access-date=2017-09-16}}</ref>
* subtraction (subleq, <u>sub</u>tract and branch if <u>l</u>ess than or <u>eq</u>ual to zero)<ref name="mazonka-subleq">{{cite web |url=http://mazonka.com/subleq/index.html |title=SUBLEQ|last=Mazonka|first=Oleg|date=October 2009|access-date=2017-09-16|archive-url=https://web.archive.org/web/20170629094925/http://mazonka.com/subleq/index.html|archive-date=2017-06-29}}</ref><ref name="esolang-subleq">{{cite web |url=https://esolangs.org/wiki/Subleq|title=Subleq|author=<!--Not stated--> |website=Esolang Wiki|access-date=2017-09-16}}</ref>
* positive subtraction when possible, else branch (Arithmetic machine)<ref name="melzak">
{{cite journal |title=An informal arithmetical approach to computability and computation |author=Z. A. Melzak |date=1961 |journal=[[Canadian Mathematical Bulletin]] |volume=4|issue=3 |pages=279–293 |doi=10.4153/CMB-1961-031-9 |doi-access=free }}</ref>

== Instruction types ==
Common choices for the single instruction are:

* [[#Subtract and branch if less than or equal to zero|Subtract and branch if less than or equal to zero]]
* [[#Subtract and branch if negative|Subtract and branch if negative]]
* [[#Arithmetic machine|Subtract if positive else branch]]
* [[#Reverse subtract and skip if borrow|Reverse subtract and skip if borrow]]
* [[#Transport triggered architecture|Move]] (used as part of a transport triggered architecture)<ref name="movfuscator">{{cite web |url=https://github.com/xoreaxeaxeax/movfuscator | title=movfuscator | author=xoreaxeaxeax | website = GitHub | access-date=2022-11-12}}</ref>

* [[#Subtract and branch if not equal to zero|Subtract and branch if non zero]] (SBNZ a, b, c, destination)
* [[#Cryptoleq|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,<ref name=caamp />{{rp|41}} the SUBLEQ language,<ref name="agut" />{{rp|4}} etc.). Each of the above instructions can be used to construct a Turing-complete OISC.

This article presents only subtraction-based 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 [http://esolangs.org/wiki/Subleq].

=== Subtract and branch if not equal to zero ===
The <code>SBNZ a, b, c, d</code>  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).<ref name=agut />

=== Subtract and branch if less than or equal to zero ===
The {{mono|subleq}} instruction ("''subtract and branch if less than or equal to zero''") subtracts the contents at address {{mono|''a''}} from the contents at address {{mono|''b''}}, stores the result at address {{mono|''b''}}, and then, ''if the result is not positive'', transfers control to address {{mono|''c''}} (if the result is positive, execution proceeds to the next instruction in sequence).<ref name=agut />{{rp|4–7}} [[Pseudocode]]:

 '''Instruction''' <syntaxhighlight lang="nasm" inline>subleq a, b, c</syntaxhighlight>
     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 (computing)|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''' <syntaxhighlight lang="nasm" inline>subleq2 a, b</syntaxhighlight>
     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 higher-order instructions using only the {{mono|subleq}} instruction.<ref name=agut />{{rp|9–10}}

Unconditional branch:

;{{mono|JMP c}}
:<syntaxhighlight lang="nasm">
  subleq Z, Z, c
</syntaxhighlight>

Addition can be performed by repeated subtraction, with no conditional branching; e.g., the following instructions result in the content at location {{mono|a}} being added to the content at location {{mono|b}}:

;{{mono|ADD a, b}}
:<syntaxhighlight lang="nasm">
  subleq a, Z
  subleq Z, b
  subleq Z, Z
</syntaxhighlight>

The first instruction subtracts the content at location {{mono|a}} from the content at location {{mono|Z}} (which is 0) and stores the result (which is the negative of the content at {{mono|a}}) in location {{mono|Z}}.  The second instruction subtracts this result from {{mono|b}}, storing in {{mono|b}} this difference (which is now the sum of the contents originally at {{mono|a}} and {{mono|b}}); the third instruction restores the value 0 to {{mono|Z}}.

A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location {{mono|b}} getting replaced by the content at location {{mono|a}}, again assuming the content at location {{mono|Z}} is maintained as 0:

;{{mono|MOV a, b}}
:<syntaxhighlight lang="nasm">
  subleq b, b
  subleq a, Z
  subleq Z, b
  subleq Z, Z
</syntaxhighlight>

Any desired arithmetic test can be built.  For example, a branch-if-zero condition can be assembled from the following instructions:

;{{mono|BEQ b, c}}
:<syntaxhighlight lang="nasm">
  subleq b, Z, L1
  subleq Z, Z, OUT
L1:
  subleq Z, Z
  subleq Z, b, c
OUT:
  ...
</syntaxhighlight>

Subleq2 can also be used to synthesize higher-order 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:

;{{mono|NOT a}}
:<syntaxhighlight lang="nasm">
  subleq2 tmp          ; tmp = 0 (tmp = temporary register)
  subleq2 tmp
  subleq2 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
</syntaxhighlight>

==== Emulation ====
The following program (written in [[pseudocode]]) emulates the execution of a {{mono|subleq}}-based OISC:

<syntaxhighlight lang="c">
 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
</syntaxhighlight>

This program assumes that {{mono|memory[]}} is indexed by ''nonnegative'' integers. Consequently, for a {{mono|subleq}} instruction ({{mono|a}}, {{mono|b}}, {{mono|c}}), the program interprets {{mono|a < 0}}, {{mono|b < 0}}, or an executed branch to {{mono|c < 0}} as a halting condition.  Similar interpreters written in a {{mono|subleq}}-based language (i.e., [[self-interpreter]]s, which may use [[self-modifying code]] as allowed by the nature of the {{mono|subleq}} instruction) can be found in the external links below.

A general purpose [[Symmetric multiprocessing|SMP]]-capable 64-bit [[operating system]] called '''Dawn OS''' has been implemented in an emulated Subleq machine. The OS contains a [[C language|C]]-like compiler. Some memory areas in the virtual machine are used for peripherals like the keyboard, mouse, hard drives, network card, etc. Basic applications written for it include a media player, painting tool, document reader and scientific calculator.<ref>{{cite web | url=http://users.atw.hu/gerigeri/DawnOS/index.html | title=Dawn for SUBLEQ }}</ref>

A 32-bit Subleq computer with a graphic display and a keyboard called '''Izhora''' has been constructed by [[Yoel Matveyev]] as a large [[cellular automata|cellular automation]] pattern.<ref>https://www.gazetaeao.ru/zanimatelnaya-nauka-vchera-segodnya-zavtra/ A Russian article on popular science in [[Birobidzhaner Shtern]] with a brief discussion of Yoel Matveyev's Izhora computer</ref><ref>https://habr.com/ru/post/584596/ A description of the virtual computer Izhora on [[Habr]] (in Russian)</ref>

==== Compilation ====
There is a [[compiler]] called '''Higher Subleq''' written by Oleg Mazonka that compiles a simplified C program into {{mono|subleq}} code.<ref>Oleg Mazonka [https://arxiv.org/abs/1106.2593 A Simple Multi-Processor Computer Based on Subleq]</ref>

Alternatively there is a self hosting [[Forth (programming language)|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 <ref>Richard James Howe [https://github.com/howerj/subleq SUBLEQ eForth]</ref>

=== Subtract and branch if negative ===
The {{mono|subneg}} instruction ("''subtract and branch if negative''"), also called {{mono|SBN}}, is defined similarly to {{mono|subleq}}:<ref name=caamp />{{rp|41,51–52}}

 '''Instruction''' <syntaxhighlight lang="nasm" inline>subneg a, b, c</syntaxhighlight>
     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 higher-order instructions using only the {{mono|subneg}} instruction. For simplicity, only one synthesized instruction is shown here to illustrate the difference between {{mono|subleq}} and {{mono|subneg}}.

Unconditional branch:<ref name=caamp />{{rp|88–89}}

;{{mono|JMP c}}
:<syntaxhighlight lang="nasm">
  subneg POS, Z, c
</syntaxhighlight>

where {{mono|Z}} and {{mono|POS}} are locations previously set to contain 0 and a positive integer, respectively;

Unconditional branching is assured only if {{mono|Z}} initially contains 0 (or a value less than the integer stored in {{mono|POS}}). A follow-up instruction is required to clear {{mono|Z}} after the branching, assuming that the content of {{mono|Z}} must be maintained as 0.

==== subneg4 ====
A variant is also possible with four operands – subneg4.  The reversal of minuend and subtrahend eases implementation in hardware.  The non-destructive result simplifies the synthetic instructions.

 '''Instruction''' <syntaxhighlight lang="nasm" inline>subneg s, m, r, j</syntaxhighlight>
     ''(* 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: 
<blockquote>
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 X, then leave the abacus as it is and proceed to instruction n. <ref>{{cite journal |title=An informal arithmetical approach to computability and computation |author=Z. A. Melzak |date=2018-11-20 |orig-date=September 1961 |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=279–293 |doi=10.4153/CMB-1961-032-6 |doi-access=free}}</ref></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.

;{{mono|MUL p, q}}
:<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<ref name="lambek">{{cite journal |title=How to program an infinite abacus |author=J. Lambek |date=2018-11-20 |orig-date=September 1961 |journal=[[Canadian Mathematical Bulletin]] |volume=4 |issue=3 |pages=295–302 |doi=10.4153/CMB-1961-032-6 |doi-access=free}}</ref> 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 (computing)|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.<ref name=caamp />

 '''Instruction''' <syntaxhighlight lang="nasm" inline>rssb x</syntaxhighlight>
     ACCUM = Mem[x] - ACCUM
     Mem[x] = ACCUM
     '''if''' (ACCUM < 0)
         '''goto''' PC + 2

==== Example ====
To set x to the value of y minus z:

<syntaxhighlight lang="asm">
# 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]
</syntaxhighlight>
* [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 ===
{{Main|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:<ref name=caamp />{{rp|42}}<ref name=dwj />

 '''Instruction''' <syntaxhighlight lang="nasm" inline>movx a, b</syntaxhighlight> (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, [[Addressing mode#Conditional execution|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.<ref name=deh />

=== Cryptoleq ===
[[File:Cryptoleq Processor.jpeg|thumb|Cryptoleq processor made at NYU Abu Dhabi]]
Cryptoleq<ref name=crq /> is a language similar to Subleq. It consists of one [[eponymous]] instruction and is capable of performing general-purpose computation on encrypted programs. Cryptoleq works on continuous cells of memory using direct and indirect addressing, and performs two operations {{math|''O''<sub>1</sub>}} and {{math|''O''<sub>2</sub>}} on three values A, B, and C:

 '''Instruction''' <syntaxhighlight lang="nasm" inline>cryptoleq a, b, c</syntaxhighlight>
     Mem[b] = O<sub>1</sub>(Mem[a], Mem[b])
     '''if''' O<sub>2</sub>(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 {{math|''O''<sub>1</sub>}} and {{math|''O''<sub>2</sub>}} are defined as follows:

:<math>\begin{array}{lcl} O_1(x,y) & = & x^{-1} y \,\bmod\, N^2  \end{array}</math>

:<math>\begin{array}{lcl} O_2(x) & = & \left \lfloor \frac{x-1}{N} \right \rfloor  \end{array}</math>

The main difference with Subleq is that in Subleq, {{math|''O''<sub>1</sub>(''x,y'')}} simply subtracts {{mvar|y}} from {{mvar|x}} and {{math|''O''<sub>2</sub>(''x'')}} equals to {{mvar|x}}. Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of {{math|''O''<sub>2</sub>}} corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. However, Cryptoleq implements fully homomorphic calculations and is capable of 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 {{math|''O''<sub>2</sub>}} operation:

:<math>G(x,y) = \begin{cases} \tilde{0}, & \text{if }O_2(\bar{x})\text{ }\leq 0 \\ \tilde{y}, & \text{otherwise} \end{cases}</math>

where <math>\tilde{y}</math> is the re-encrypted value of {{mvar|y}} and <math>\tilde{0}</math> is encrypted zero. {{mvar|x}} is the encrypted value of a variable, let it be {{mvar|m}}, and <math>\bar{x}</math> equals {{tmath|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]].

== See also ==
* [[FRACTRAN]]
* [[Minimal axioms for Boolean algebra]]
* [[Register machine]]
* [[Turing tarpit]]
* [[Reduced instruction set computer]]
* [[Complex instruction set computer]]
* [[Explicitly parallel instruction computing]]
* [[Minimal instruction set computer]]
* [[Very long instruction word]]
* [[Zero instruction set computer]]

== References ==
{{Reflist|refs=

<ref name=urisc>{{Cite journal
  | last = Mavaddat
  | first = F.
  |author2=Parhami, B.
  | title = URISC: The Ultimate Reduced Instruction Set Computer
  | journal = International Journal of Electrical Engineering Education
  | volume = 25
  | issue = 4
  | pages = 327–334
  | publisher = Manchester University Press
  | date = October 1988
  |url=http://www.ece.ucsb.edu/~parhami/pubs_folder/parh88-ijeee-ultimate-risc.pdf
  | doi =10.1177/002072098802500408
  | s2cid = 61797084
  | access-date = 2010-10-04}}
This paper considers "a machine with a single 3-address 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., [[Turing-complete]]) machine whose simplicity makes it ideal for classroom use.</ref>

<ref name=caamp>{{Cite book
 |last        = Gilreath
 |first       = William F.
 |author2     = Laplante, Phillip A.
 |title       = Computer Architecture: A Minimalist Perspective
 |publisher   = [[Springer Science+Business Media]]
 |year        = 2003
 |url         = http://www.caamp.info
 |isbn        = 978-1-4020-7416-5
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20090613042342/http://www.caamp.info/
 |archive-date = 2009-06-13
}}
Intended for researchers, computer system engineers, computational theorists and students, this book provides an in-depth examination of various OISCs, including SBN and MOVE. It attributes SBN to W. L. van der Poel (1956).</ref>

<ref name=agut>{{Citation
  | last1 = Nürnberg
  | first1 = Peter J.
  | last2 = Wiil
  | first2 = Uffe K.
  | last3 = Hicks
  | first3 = David L.
  | title = Metainformatics: International Symposium, MIS 2003
  | place = Graz, Austria
  | publisher = [[Springer Science+Business Media]]
  | date = September 2003
  | chapter = A Grand Unified Theory for Structural Computing
  | chapter-url = https://books.google.com/books?id=uxjigT31ns4C&pg=PA1
  | pages = 1–16
  | url = http://www.informatik.uni-trier.de/~ley/db/conf/metainformatics/metainformatics2003.html
  | isbn = 978-3-540-22010-7
  | access-date = 2009-09-07
  | archive-date = 2015-01-03
  | archive-url = https://web.archive.org/web/20150103161748/http://www.informatik.uni-trier.de/~ley/db/conf/metainformatics/metainformatics2003.html
  | url-status = dead
  }}
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".</ref>

<ref name=dwj>{{Cite journal
  | last = Jones
  | first = Douglas W.
  | title = The Ultimate RISC
  | journal = ACM SIGARCH Computer Architecture News
  | volume = 16
  | issue = 3
  | pages = 48–55
  | publisher = ACM
  | location = New York
  | date = June 1988
  |url=http://www.cs.uiowa.edu/~jones/arch/risc/
  | doi = 10.1145/48675.48683
  | s2cid = 9481528
  | access-date = 2010-10-04}}
"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."</ref>

<ref name=deh>{{Citation
  | last = Catsoulis
  | first = John
  | title = Designing embedded hardware
  | publisher = [[O'Reilly Media]]
  | year = 2005
  | edition = 2
  | pages = 327–333
  | isbn = 978-0-596-00755-3}}</ref>

<ref name=crq>{{Citation
  | first = Oleg
  | last = Mazonka
  | author2 =  Tsoutsos, Nektarios Georgios
  | author3 = Maniatakos, Michail
  | title = Cryptoleq: A Heterogeneous Abstract Machine for Encrypted and Unencrypted Computation
  | journal = IEEE Transactions on Information Forensics and Security
 | year = 2016
  | volume = 11
 | issue = 9
 | pages = 2123–2138
 | doi= 10.1109/TIFS.2016.2569062| s2cid = 261387
 }}</ref>
}}

== External links ==
<!-- Do not add any external links that are available on the sites already linked! -->
* [http://esolangs.org/wiki/Subleq Subleq on the esoteric programming languages wiki] – interpreters, compilers, examples and derivative languages
* {{youTube|NmWwRmvjAE8|Reductio ad absurdum}} by Christopher Domas
* [https://web.archive.org/web/20151121172708/http://www.sccs.swarthmore.edu/users/06/adem/engin/e25/finale/ Laboratory subleq computer] – [[FPGA]] implementation using [[VHDL]]
* [http://catb.org/~esr/retro/#emulators The Retrocomputing Museum] – SBN emulator and sample programs
* [http://bitstuff.blogspot.com/2007/02/subtract-and-branch-if-negative.html Laboratory SBN computer] – implemented with [[7400 series]] integrated circuits
* [http://esolangs.org/wiki/RSSB RSSB on the esoteric programming languages wiki] – interpreters and examples
* [http://www.ddj.com/embedded/221800122?pgno=1 Dr. Dobb's 32-bit OISC implementation] – transport triggered architecture (TTA) on an [[FPGA]] using [[Verilog]]
* [http://www.maxim-ic.com/appnotes.cfm/appnote_number/3222 Introduction to the MAXQ Architecture] – includes transfer map diagram
* [http://sourceforge.net/projects/oiscemulator OISC-Emulator] – graphical version
* [https://github.com/jbangert/trapcc TrapCC] (recent Intel x86 MMUs are actually Turing-complete OISCs.)
* [https://github.com/yoelmatveyev/Izhora Izhora] – Yoel Matveyev's Subleq computer built as a cellular automation
* [http://cs.drexel.edu/~bls96/oisc/ SBN simulator] – simulator and design inspired by [[CARDboard Illustrative Aid to Computation]]
* [http://laughtonelectronics.com/Arcana/One-bit%20computer/One-bit%20computer.html One-bit Computing at 60 Hertz] – intermediate between a computer and a [[state machine]]
* [https://demin.ws/blog/english/2010/04/06/modelling-a-cpu-with-only-one-operation/ The NOR Machine]{{snd}}info on building a CPU with only one Instruction
* [https://github.com/howerj/subleq/ SUBLEQ eFORTH] A complete Forth interpreter running on the SUBLEQ OISC.
* [https://github.com/momalab/cryptoleq Cryptoleq]{{snd}}Cryptoleq resources repository
* [https://sites.google.com/site/comparchampsite/ CAAMP]{{snd}}Computer Architecture A Minimalist Perspective
* [https://deegen1.github.io/sico SICO] – Single Instruction COmputer: a variant of SUBLEQ using unsigned integers

{{Clear}}
{{CPU technologies}}
{{Authority control}}

[[Category:Models of computation]]
[[Category:Esoteric programming languages]]
{{Esoteric programming languages}}