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:

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-|

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

Post a comment