OISC

From Esolang

OISC is the One Instruction Set Computer (by analogy with RISC and CISC), a machine providing only one instruction. The abbreviation URISC (Ultimate RISC) has been used in some publications with the same meaning as OISC.

In some implementations the instruction is subtract and branch unless positive, abbreviated subleq (subtract and branch if less or equal to zero), or sometimes subtract and branch if negative (SBN), which only differ by zero-inclusion. Some languages use a memory mapped instruction pointer (as in RSSB). Branching is done by writing to IP in these implementations. More advanced memory mapping allows complex functionality such as arithmetic, but with the benefit of having a simple copy operation (MOVE).

The subtract-and-branch-unless-positive operation usually has three parameters. subleq(a,b,c) (Subleq) subtracts a from b, stores the result in b, and then transfers control to the address in c if the result was non-positive.

Possibly, the simplest known OISC is BitBitJump. Its instruction has 3 operands as in Subleq, but the meaning is: copy the bit addressed by a to the bit addressed by b and jump to the address c. BitBitJump has a "big brother", ByteByteJump which copies 1 byte at a time instead of 1 bit. Both of these machines belong to a larger class of machines which copy b bits at a time, but have address operands of size n*b, where n≥2 (e.g. 32-bit addresses and 8-bit data for a 32-bit ByteByteJump machine). It is this feature which allows BitBitJump, ByteByteJump and similar machines to perform arithmetic and conditional jumps through the use of self-modifying code.

Although an OISC is not required to be Turing-complete (as RISC, CISC, and other processors), it is necessary that it can perform Turing-complete computations. In other words it should be possible to compile any Turing-complete language program into a sequence of OISC instructions. This requirement obviously comes from real computers: OISC is a subset of RISC, and RISC is a subset of all processors which can be implemented in hardware, which makes OISC to be at least of linear bounded automaton computational class.

Some OISC languages are Turing-complete, making them Turing tarpits. However TC-ness requires them to be defined with sufficient abstraction with respect both to their addressing scheme and their operand size. For example, Subleq uses absolute addressing and does not specify its operand size, so it is TC. BitBitJump, on the other hand, is defined to use bounded operand size and absolute addressing, so it is only linear bounded automaton. It is not known whether either of these languages with bounded operand size could achieve TC-ness by revising them to use relative addressing. It seems likely, however, because relative addressing is the Turing machine property.

Any OISC language belongs to either one of the two groups: with memory mapping (MOVE, RSSB) or without (Subleq, SBN, BitBitJump, ByteByteJump). Note, that a language from the second group may have an extension with memory mapped special addresses, but those addresses are not required for computations; they are used for IO or any other system calls.