Sunday 19 April 2009

Redcode's OISC - the DJN Computer

An OISC is an abstract computer designed to be Turing complete with only one instruction. OISC is short for One-Instruction Set Computer.

The instruction used by most variants of OISC subtracts and branches on certain conditions, for example the URISC / RSSB Single Instruction Computer. It may come as a surprise that the Redcode instruction set contains a primative instuction suitable for building a One-Instruction Computer, DJN.

DJN X, Y uses Y as a pointer into memory. 1 is subtracted from the value stored at location Y. If the result is non-zero, DJN jumps to X. Here's an example demonstrating how to copy A to B using DJN:

        DJN 0,   TEMP
DJN 0, B
DJN 1, TEMP
DJN -1, A
DJN 1, A
DJN 1, B
DJN -2, TEMP


Unfortunately, the performance is poor, 56000 cycles to execute a MOV!

The following code proves DJN is Turing complete by equivalence to SUBLEQ A, B, C:

         DJN 0,   TEMP
DJN 1, TEMP
DJN 10, B
DJN 4, SCRATCH
DJN 3, SCRATCH
DJN 1, TEMP
DJN 1, B
DJN -2, A
DJN 1, A
DJN -1, TEMP
DJN C, SCRATCH
DJN C, SCRATCH
DJN -11, A
DJN 1, A
DJN -1, TEMP


So, who's volunteering to implement the first self-interpreter? ;-)