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 bit addressed by a to the bit addressed by b and jump to the address c.

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 RISK, and RISK 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). 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.