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? ;-)

2 comments:

Unknown said...

Maybe i misscalculated the number of cycles it takes...
DJN 0, TEMP
(TEMP would be an already known location, so this line could be removed)

DJN 0, B ;b times

DJN 1, TEMP ;a times
DJN -1, A ;a times

DJN 1, A ;CORESIZE-a
DJN 1, B ;CORESIZE-a
DJN -2, TEMP ;CORESIZE-a
So:
3*(CORESIZE-a) +2*a +b = 3*CORESIZE+ b -a
That is, from 16K to 32K for a 8K CORESIZE
Am i right? 8-|

John said...

Hi Neo,

Your calculations are correct, but you're missing the special case where a=0, b=0.

As you mentioned DJN 0, TEMP can be left out if the value of TEMP is already known.

Cheers,

John