Sunday, June 22, 2008

One Instruction Set Computer

It is possible to define (and implement) a computer with only 1 instruction, and still have Turing-completeness.

With an instruction like this:

subleq a, b, c
        ;Mem[b] = Mem[b] - Mem[a]
        ;if (Mem[b] ≤ 0) goto c

A similar machine has been built in the 70es and there are also various interpreters and compilers for OISC.

Read more here and here.

Some articles (e.g. A one instruction set architecture for genetic algorithms) also discuss the possibility of building such machine at nanoscale :)

No comments:

Post a Comment