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. 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. OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research. The first carbon nanotube computer is a 1-bit one-instruction set computer (and has only 178 transistors).
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.Oleg Mazonka, "Bit Copying: The Ultimate Computational Simplicity", Complex Systems Journal 2011, Vol 19, N3, pp. 263–285
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, 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 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 TOGgle a And branch to b if the result of the toggle operation is true.
Multi-bit copying machine Similar to BitBitJump, a multi-bit copying machine 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.
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) 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, the SUBLEQ language, 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 .
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).
Subtract and branch if less than or equal to zero The instruction ("subtract and branch if less than or equal to zero") subtracts the contents at address from the contents at address , stores the result at address , and then, if the result is not positive, transfers control to address (if the result is positive, execution proceeds to the next instruction in sequence). 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.
Synthesized instructions It is possible to synthesize many types of higher-order instructions using only the instruction.
Unconditional branch:
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 being added to the content at location :
subleq a, Z subleq Z, b subleq Z, Z
The first instruction subtracts the content at location from the content at location (which is 0) and stores the result (which is the negative of the content at ) in location . The second instruction subtracts this result from , storing in this difference (which is now the sum of the contents originally at and ); the third instruction restores the value 0 to .
A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location getting replaced by the content at location , again assuming the content at location is maintained as 0:
subleq b, b subleq a, Z subleq Z, b subleq Z, Z
Any desired arithmetic test can be built. For example, a branch-if-zero condition can be assembled from the following instructions:
subleq b, Z, L1 subleq Z, Z, OUT L1: subleq Z, Z subleq Z, b, c OUT: ...
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:
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
Emulation The following program (written in pseudocode) emulates the execution of a -based 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 is indexed by nonnegative integers. Consequently, for a instruction (, , ), the program interprets , , or an executed branch to as a halting condition. Similar interpreters written in a -based language (i.e., self-interpreters, which may use self-modifying code as allowed by the nature of the instruction) can be found in the external links below.
A general purpose SMP-capable 64-bit operating system called Dawn OS has been implemented in an emulated Subleq machine. The OS contains a 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.
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.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 computerhttps://habr.com/ru/post/584596/ A description of the virtual computer Izhora on Habr (in Russian)
Compilation There is a compiler called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into code.Oleg Mazonka A Simple Multi-Processor Computer Based on Subleq
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 Richard James Howe SUBLEQ eForth
The Eternal Software InitiativeAdrian Cable Eternal Software Initiative provides a LLVM compiler backend that compiles standard C and C++ programs directly to a minimal Subleq+ VM. It's good enough to run Linux natively on it and preserve it as a "time capsule".
Subtract and branch if negative The instruction ("subtract and branch if negative"), also called , is defined similarly to :
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.
Synthesized instructions It is possible to synthesize many types of higher-order instructions using only the instruction. For simplicity, only one synthesized instruction is shown here to illustrate the difference between and .
Unconditional branch:
subneg POS, Z, c
where and are locations previously set to contain 0 and a positive integer, respectively;
Unconditional branching is assured only if initially contains 0 (or a value less than the integer stored in ). A follow-up instruction is required to clear after the branching, assuming that the content of must be maintained as 0.
subneg4