Op Codes? We don't need no stinking Op Codes!

If a computer (or computer language) can do anything that any other computer (or computer language) -- given enough time and storage --  it is said to be Turing complete.

A computer can be Turing complete even if it has only one type of operation.  The most common operation used to illustrate this is 'subtract the value at address B from the value at address A replacing the value at address A with the result of the subtraction and branch to the instruction at address C if the result is negative or zero'.

This can be represented by an instruction with three addresses and no op codes.  In this discussion, an instruction will be written as

A,B,C

where A is the address of the minuend and the result, B is the address of the subtrahend, and C is the address of the next instruction if the result is negative or zero; if C is omitted, the third address is the address of the location following the instruction.  A data value will be represented by

+X

or

-X

(depending on whether the value is non-negative or negative) where X is a string of decimal digits; a data value of zero will be represented by +0.  A dollar sign ($) in an address represents the address of the current location.  A label is a string of letters or digits beginning with a letter and followed by a colon (:); it represents the address of the instruction or data value that it precedes.  Comments will begin with an asterisk (*), and a number sign (#) inside a comment means the value of the given location.

External devices (and internal features such as virtual memory) can be accessed using memory-mapped registers, where specific addresses provide access to the registers of the device or feature.  An external device may have status registers, control registers, input registers, and output registers.  To simplify the programs, we will assume that an input register has a negative value if no input is available and an output register has a negative value if the device cannot accept output, while status and control information can be accessed at any time.  Also, we will assume that the value of a memory-mapped register will not change if an instruction accesses the register as its second operand and one of the next two instructions executed accesses the register as its first operand.


Now for simulating the instructions of a conventional computer.  The following values are assumed to be defined in all of the examples:

ZERO:     +0
ONE:      +1
MINUSONE: -1
WORKLOC:  +0
WORKLOC2: +0

A subtract operation is obtained by

          A,B,$+1 (or A,B)

A location can be set to zero by

          A,A

An add is obtained by

          WORKLOC,WORKLOC,$+1          * WORKLOC = 0
          WORKLOC,B,$+1                * WORKLOC = -#B
          A,WORKLOC,$+1                * A = #A + #B

A negate operation is obtained by

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC,B                    * WORKLOC = -#B
          WORKLOC2,WORKLOC             * WORKLOC2 = #B
          WORKLOC2,WORKLOC             * WORKLOC2 = 2*#B
          B,WORKLOC2                   * B = -#B

A move from A to B is performed by

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,A                    * WORKLOC = -#A
          B,B                          * B = 0
          B,WORKLOC                    * B = #A

or, if B is a  mapped register,

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC,A                    * WORKLOC = -#A
          WORKLOC2,B                   * WORKLOC2 = -#B
          WORKLOC,WORKLOC2             * WORKLOC = #B - #A
          B,WORKLOC                    * B = #A

A swap between A and B is performed by

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC,A                    * WORKLOC = -#A
          WORKLOC2,B                   * WORKLOC2 = -#B
          A,A                          * A = 0
          A,WORKLOC2                   * A = #B
          B,B                          * B = 0
          B,WORKLOC                    * B = #A


or, if B is a memory mapped register,

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC,A                    * WORKLOC = -#A
          WORKLOC2,B                   * WORKLOC2 = -#B
          WORKLOC,WORKLOC2             * WORKLOC = #B - #A
          B,WORKLOC                    * B = #A
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,WORKLOC             * WORKLOC2 = #A - #B
          A,WORKLOC2                   * A = #B

An unconditional branch is performed by

          WORKLOC,WORKLOC,NEWADDR

A compare is performed by

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC,A                    * WORKLOC = -#A
          WORKLOC2,WORKLOC             * WORKLOC2 = #A
          WORKLOC2,B,$+2               * IF #A <= #B
                                       * SKIP 1 INSTRUCTION
          WORKLOC,WORKLOC,AGTB         * GOTO AGTB (#A > #B)
          WORKLOC2,MINUSONE,ALTB       * IF #A < #B GOTO ALTB
AEQB:                                  * IF #A == #B CONTINUE

A subroutine call can be made using

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,PARMLIST+1           * WORKLOC = -#A
          A,A                          * (FIRST ARGUMENT) = 0
          A,WORKLOC                    * (FIRST ARGUMENT) = #A
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,PARMLIST+2           * WORKLOC = -#B
          B,B                          * (SECOND ARGUMENT) = 0
          B,WORKLOC                    * (SECOND ARGUMENT) = #B
          SUBROUT,SUBROUT              * BEGINNING OF SUBROUTINE = 0

          SUBROUT,RETADDR              * BEGINNING OF SUBROUTINE =
                                       * RETURN ADDRESS
          WORKLOC,WORKLOC,SUBROUT+1    * GOTO SUBROUTINE
RETADDR:  +0-RETURN                    * ADDRESS OF LOCATION
                                       * FOLLOWING SUBROUTINE CALL
X:        +0                           * RESULT FROM SUBROUTINE CALL
RETURN:   WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,RESULT               * WORKLOC = -#RESULT
          X,X                          * X = 0
          X,WORKLOC                    * X = #RESULT
                                       * CONTINUE

                                       * . . .

SUBROUT:  +0                           * RETURN ADDRESS
          WORKLOC,WORKLOC,SUBRBODY     * SKIP OVER PARMLIST
RESULT:   +0                           * RESULT
A:        +0                           * FIRST ARGUMENT
B:        +0                           * SECOND ARGUMENT
SUBRBODY:

                                       * . . .

          WORKLOC,WORKLOC,SUBROUT      * RETURN TO CALLING ROUTINE


Notice that this computer executes many more instructions than a conventional computer to perform the same task.  Turing complete does not mean that a computer is as efficient as other computers, it merely means that it can (eventually) perform the same tasks.