0

Ever since I learned how to manipulate assembly in college, I have been fascinated with the idea of starting as small as possible and building up to infinite complexity. I've been working on my own theoretical minimal instruction set which avoids composite instructions like "subleq." The problem I have with these sorts of instructions is that they act like two (or more) separate instructions with a maintained state. In other words, they could be broken down into (IBM Pseudocode):

S       R0,NUMBER
CLI     R0,XL4'00'
BNH     DESTINATION

So the minimal instruction set I want to use to build more complexity on top of should already be atomized and should not contain state.

So far what I have come up with is three instructions: (s)tore, (n)and, and (j)ump. There is a single accumulator and a PC counter - there is nothing else. All instructions take two bits followed by X bits containing a relative address which means there are no "immediate" values. I can load a value into the accumulator by using these instructions as demonstrated (8-bit):

00 000111    LOAD    S   HOLDER  ; first we must zero-out the accumulator
01 000110            N   HOLDER
01 000101            N   HOLDER
00 000100            S   HOLDER
01 000011            N   HOLDER  ; accumulator is now equal to zero
01 XXXXXX            N   NUMBER  ; load number into accumulator
10 000010            J   NEXT    ; jump over the helper to the next instruction
00 000000    HOLDER  =   0
XX XXXXXX    NEXT    ...

It should become obvious that instruction editing is allowed to make jumps effectively conditional but I'm not entirely sure how to accomplish such a task as yet. Is something so simple still Turing complete or is this a pie in the sky kind of idea?

Timothy Eckstein
  • 307
  • 1
  • 2
  • 10
  • If you can actually implement addition or subtraction and a conditional branch, it's probably Turing complete, It won't be possible to write *efficient* programs to do simple things like sort an array of integers (or just find the min or max), or implement a multiply with addition. Even implementing addition will require looping until carry stops propagating ([What is the best way to add two numbers without using the + operator?](https://stackoverflow.com/q/365522)). Writing a sequence of NAND insns that can S to update the destination of a J looks difficult, even between 2 options. – Peter Cordes Sep 10 '18 at 01:45
  • Are branch targets relative or absolute? If relative, then your implementation already needs an adder internally. Another opcode for add or sub, or instead of NAND, could maybe help be turing complete. You only seem to have 3 opcodes, but I don't understand why the first `S` (store)` insn has a `LOAD` on that line. How can load and store use the same opcode? – Peter Cordes Sep 10 '18 at 01:48
  • 1
    See my quora.com answer describing how to build a universal turing machine with two states and three symbols: http://qr.ae/TUNces (The answer was too big to write in this margin :) – Ira Baxter Sep 10 '18 at 03:06
  • 1
    @Peter: the CM-2 (Connection Machine 2) supercomputer (vintage 1991) had 1 bit CPUs, and implemented floating point by going through a long bit-serial operations. Yes, that's painfully slow, IIRC, something like 200 instructions to execute. But if the overhead is constant, you *can* build "efficient" routines in a complexity theory sense; we're just arguing about a constant. (What made the CM-2 "super" was it had 65,536 of these CPUs and they all worked in parallel execuing from the same instruction stream. So you lost a factor of two hundred, but gained a factor of 300 parallelism. – Ira Baxter Sep 10 '18 at 03:12
  • 1
    Define “state” and “immediate value.” All your instructions take an immediate operand, so there are most definitely immediate values in your instruction set. Even an adder keeps a bunch of immediate values (carry) to perform its operation. – fuz Sep 10 '18 at 07:45

0 Answers0