SMITH Turing-completeness proof sketch

Overview

To demonstrate that SMITH is Turing-complete, we implement a 2-symbol, 3-state Turing machine in SMITH.

This is just a proof sketch (but my hope is that it will be fairly persuasive nonetheless.) For it to be a full proof, it would need:

• to rigorously define the rules for converting an arbitrary 2-symbol Turing machine into a SMITH program (instead of leaving it up to the reader to extrapolate the mechanism from this one example)
• to be tested (it hasn't been, and I'm not entirely confident I got all the offsets right)

Our chosen Turing machine has two symbols, 0 and 1, and three states:

state #1: If symbol on tape is 0, write 1, move tape right, enter state 2.
          If symbol on tape is 1, write 1, move tape right, stay in state 1.

state #2: If symbol on tape is 0, write 0, move tape right, enter state 2.
          If symbol on tape is 1, write 1, move tape left, enter state 3.

state #3: If symbol on tape is 0, write 0, move tape right, halt.
          If symbol on tape is 1, write 0, move tape right, enter state 1.

We will implement the tape as the sequence of registers stored at R100 upwards. R4 will point to a cell in the tape (easy to remember because "tape" has four letters, as does "head"), initially pointing at R100.

We will implement each state as a pair of code blocks, each of which performs one of the two cases of the state: writing a symbol to the tape, moving the tape head, and switching to a new state.

To indicate which state we are in, we establish a set of registers, one register for each state. The register for the state we are currently in will contain 1, and the others will contain 0. Sort of like a unit vector, with one dimension for each state.

One key thing here is that, the appropriate code block for the current state must to be copied forward from an absolute address (or at least some address where we know we've executed it in the past, but absolute addresses will be simplest for this.) Since COR only takes relative offsets, that means keeping the offsets of the code blocks we want to copy in registers, and updating those registers each time we copy code forward. (I believe Nathan Thern's "99 bottles" in SMITH uses the same, or a very similar, technique.)

In actuality, we probably only need one base offset, from which we could compute all the code block offsets (by adding their offsets from the base offset.) But to keep the presentation from being too obscure, we'll track the offsets of each code block seperately. Also for simplicity, we ensure that each of these code blocks is the same length.

One small caveat with this approach is that we need to execute all of these code blocks once when the program begins. This is not a problem in practice: we make them work on a scratch area instead of the real tape, we re-initialize the tape head and state indicators afterwards, and we ensure that none of these code blocks do anything stupid like COR or STOP.

Actually checking the state and copying the right code block will be the responsibility of a code block common to all states. This code block is copied forward on every iteration as well, of course, but since we know we always execute it on an iteration, we can get away with not knowing its absolute address.

Register Map

R0        always 0, for convenience
R1        always 1, for convenience
R2        always -1, for convenience

R3        "proceed?": if 0, halt; otherwise 1

R4        pointer into tape (starts at R100)

R5        1 if the finite control is in state 1, 0 otherwise
R6        1 if the finite control is in state 2, 0 otherwise
R7        1 if the finite control is in state 3, 0 otherwise

R10       symbol currently under tape head, or NOT of it
R11       working register (product of R10, one of R5..R7, R3,
          and the length of a code block -> # of instructions to copy)

R21..R26  offsets of code blocks #1...#6

R49       length of main loop code block (constant, but COR needs a register)

R90..R99  scratch registers used during initialization
R100      start of tape (extends upward)

Translation of the Turing machine to SMITH

; Initial initialization.

MOV R0, 0         ; Initialize R0 to the constant 0 for convenience
MOV R1, 1         ; Initialize R1 to the constant 1 for convenience
MOV R2, 0
SUB R2, 1         ; Initialize R2 to the constant -1 for convenience
MOV R49, 49       ; Initialize R49 to the length of the main loop

MOV R0, 90        ; Initialize the tape pointer to scratch area

; ### code block #1 (state 1a): write 1, move tape right, enter state 2 ###

MOV R[R4], R1
SUB R4, R2
MOV R5, 0
MOV R6, 1
MOV R7, 0

; ### code block #2 (state 1b): write 1, move tape right, stay in state 1 ###

MOV R[R4], R1
SUB R4, R2
MOV R5, 1
MOV R6, 0
MOV R7, 0

; ### code block #3 (state 2a): write 0, move tape right, enter state 2 ###

MOV R[R4], R0
SUB R4, R2
MOV R5, 0
MOV R6, 1
MOV R7, 0

; ### code block #4 (state 2b): write 1, move tape left, enter state 3 ###

MOV R[R4], R1
SUB R4, R1
MOV R5, 0
MOV R6, 0
MOV R7, 1

; ### code block #5 (state 3a): write 0, move tape right, halt ###

MOV R[R4], R0
SUB R4, R2
MOV R3, 0
NOP
NOP

; ### code block #6 (state 3b): write 0, move tape right, enter state 1 ###

MOV R[R4], R0
SUB R4, R2
MOV R5, 1
MOV R6, 0
MOV R7, 0

; Re-initialization.  This block is not copied.

MOV R3, 1         ; Proceed.
MOV R4, 100       ; Move tape head to start of tape.
MOV R5, 1         ; Start in state 1.
MOV R6, 0
MOV R7, 0

; ... Initialize offsets of code blocks, too.  These offsets should
; be relative to the corresponding CORs in the Main Loop below.

MOV R21, 0
SUB R21, 53
MOV R22, 0
SUB R22, 55
MOV R23, 0
SUB R23, 57
MOV R24, 0
SUB R24, 59
MOV R25, 0
SUB R25, 61
MOV R26, 0
SUB R26, 63

; ***** Main Loop *****

; Get bit from tape into R10 and negate it;
; Multiply it by R5 ("in state 1?") and place in R11;
; Multiply R11 by R3 (to zero it if we've halted);
; Multiply R11 by 5 (size of a code block); and
; Copy R11 instructions from code block #1 into what we'll do next.

MOV R10, R[R4]
NOT R10
MOV R11, R5
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +43, R21, R11

; Get bit from tape into R10;
; Multiply it by R5 ("in state 1?") and place in R11;
; Multiply R11 by R3 (to zero it if we've halted);
; Multiply R11 by 5 (size of a code block); and
; Copy R11 instructions from code block #2 into what we'll do next.

MOV R10, R[R4]
NOP
MOV R11, R5
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +36, R22, R11

; same thing for R6 ("in state 2?") and code blocks #3 and #4

MOV R10, R[R4]
NOT R10
MOV R11, R6
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +29, R23, R11

MOV R10, R[R4]
NOP
MOV R11, R6
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +22, R24, R11
 
; same thing for R7 ("in state 3?") and code blocks #5 and #6

MOV R10, R[R4]
NOT R10
MOV R11, R7
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +15, R25, R11

MOV R10, R[R4]
NOP
MOV R11, R7
MUL R11, R10
MUL R11, R3
MUL R11, 5
COR +8, R26, R11

; Now, update code block offsets, so they all still point at the
; code blocks at the beginning of the program.

SUB R21, R49
SUB R22, R49
SUB R23, R49
SUB R24, R49
SUB R25, R49
SUB R26, R49

; Now copy everything from "Main Loop" onward into what we'll
; do right after what we do next.  48 = (7*6)+6

COR +8, -48, R49

; And that should be all we need.