One instruction set computer

Encyclopedia : O : ON : ONE : One instruction set computer

OISC redirects here. For the Anglo-Saxon king, see Oisc of Kent.

The One Instruction Set Computer, is a single machine language opcode which is sufficient to produce a Turing complete machine. Although such a computer could be taken as the logical conclusion of reduced instruction set computing, the single instruction computer is generally considered a thought experiment to show how small an instruction set could be made while still retaining the properties of a universal computer.

Contents

1 Subtract and branch if negative

1.1 Example emulator
1.2 Common instructions

2 Reverse-subtract and skip if borrow

2.1 Example

3 Move
4 References

Subtract and branch if negative

Subtracts the contents of memory location a from the contents of b, storing the result back into b, and then, if the result was negative or zero, transferring control to the location specified by the address stored in c.

Example emulator

int program_counter = 0;
int memory[384]
while (TRUE)

Common instructions

Subtract and branch if negative abreviated as subleq.

Unconditional branch:

Z is a location previously initialized to contain 0.

JMP c   ==   subleq Z, Z, c

(The branch is unconditional regardless of whether Z previously contained 0, but to prevent overwriting the contents of Z, a special reserved location should be used.)

In any instruction, the conditional branch can be suppressed by pointing it at the instruction that would have been executed next in any case. If the parameter c is missing, it is implied that this is the case.

Addition can be performed as reversed subtraction:

ADD a,b ==   subleq a, Z
subleq Z, b
subleq Z, Z

(Here all the branches have been suppressed.) The first instruction computes the negation of a and stores it in location Z. The second instruction subtracts -a from b; the third instruction restores the value 0 to Z. A copy instruction can be implemented similarly:

STO a,b ==  subleq b,b
subleq a,Z
subleq Z,b
subleq Z,Z

Any desired arithmetic test can be built out of the ≤0 relation. For example, a branch-if-zero 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:...

Reverse-subtract and skip if borrow

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 memory location 0.

Example

To set x to the value of y minus z:

RSSB x
RSSB x
RSSB x
RSSB z
RSSB x
RSSB temp
RSSB temp
RSSB temp
RSSB temp
RSSB y
RSSB temp
RSSB temp
RSSB x
RSSB temp
RSSB temp
RSSB temp
RSSB temp

Move

Moves the contents of one memory location to another memory location. Arithmetic is performed using a memory-mapped ALU, and jumps are performed using a memory-mapped program counter. A [computer] was made from the Wireworld cellular automaton using this design. Douglas Jones wrote an essay on this architecture for ACM [link] describing his architecture and how it worked. [link]

The Transport Triggered Architectures can be seen as a kind of move architecture. [link]

References

[The Retrocomputing Museum]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.