Search code examples
cpucpu-architectureinstruction-setturing-complete

What is the simplest Turing complete CPU instruction set which can execute code from ROM?

I believe that all the OISCs below, require that programs are executed from RAM, in order to be Turing Complete.

https://en.wikipedia.org/wiki/One_instruction_set_computer

Is this the case?

What is the simplest Turing Complete CPU instruction set which can execute code from ROM? i.e. that does not need to modify future instructions in order to make conditional jumps, etc.

Solution

  • I don't believe that all of the OISC's require RAM programs to work. Consider the "subtract and branch if less than zero" (subleq) instruction. You can use it to synthesize much more complex operations without having to rely on self-modifying code. Accordingly, you should be able to write ROM programs using only subleq and still retain Turing-completeness.

    Hope this helps!