Self-Modifying Indecent Turing Hack
Copyright ©2000-2012 Chris Pressey, Cat's Eye Technologies. All rights reserved.
"This space intentionally left blank."
— MIT's Dungeon (later Infocom's Zork I)
"The only thing that really worried me was the ether. There is nothing in the world more helpless and irresponsible and depraved than a man in the depths of an ether binge. And I knew we'd get into that rotten stuff pretty soon."
— Hunter S. Thompson, Fear and Loathing in Las Vegas
What is SMITH?
SMITH, the successor to SMETANA, is a programming language that goes one better than Bullfrog. Not only are there no conditional jumps, there are no jumps whatsoever. The program counter can only be incremented, and only instruction by instruction.
But, you ask, how can such an ungodly beast be Turing-Complete? Surely this goes against all that is decent and good and sane in the world we know. (OK, maybe you won't put it exactly that way - I forgive you.)
Well, there's actually a relatively straightforward answer. Instead of jumping back into code to repeat and/or recheck something, you must instead copy blocks of code forward, where they will be checked in the near future.
And if the code copied forward includes the instruction that caused the copy in the first place, that will happen again (and again and again) when the copy executes. A loop, but not by means of iteration or recursion but instead by self-propogation.
Otherwise, SMITH is basically a small generic imperative CISC-ish virtual machine with only the most basic arithmetic operations, loosely modelled on the "[imaginary] register machine that is representative of several minicomputers" described in section 9.2 of the Dragon Book.
And when I say loosely modelled, I mean it. Differences between this and
the 'Dragon' machine include the fact that this has no
instruction, and that here, the destination is specified before the
source (not after;) also, the
# before an immediate (literal) is
allowed but not required here, and the indirection syntax is completely
different (there's only indirect references to registers, not memory,
Consider the SMITH machine to have an unlimited number of registers.
These are called
Rn where no arbitrary limit is imposed on
n. In some instructions, they may be referenced indirectly, and in
that case they are called
An indirect reference like
R[R0] refers to 'the register whose number
is the number stored in register zero.' If
R0 contained 7, then
R[R0] would be synonymous with
Each instruction has the general form:
OPCODE [destination[, source[, length]]]
(Here, the square breackets denote "may be omitted", not indirect references.)
destination is either the name of a register or an immediate offset
from the current program counter.
source is either a register, an
immediate offset from the current program counter, or an immediate
length, if present, is the name of a register. All integers
are notated in decimal.
# may precede immediate integers if the
programmer desires. However, it may not precede offsets (they should be
preceded by either
The basic instructions (available in the original version) are:
MOV register, immediate e.g. MOV R0, 0 MOV register, register MOV R1, R0 SUB register, immediate SUB R1, 1 SUB register, register SUB R0, R1 MUL register, immediate MUL R0, 2 NOT register NOT R0 COR offset, offset, register COR +1, -5, R0 STOP STOP
The instructions in the following table were made available in SMITH v2 (June 25 2000).
MOV [register], register MOV R[R1], R0 MOV register, [register] MOV R1, R[R0] MOV [register], "string" MOV R[R0], "nights and weird mornings" MOV register, PC MOV R303, PC MOV register, * MOV R304, * MOV TTY, register MOV TTY, R1 MOV TTY, [register] MOV TTY, R[R65535] MOV register, TTY MOV R0, TTY MOV [register], TTY MOV R[R0], TTY MUL register, register MUL R999999999, R123456789 COR offset, register, register COR +1, R22, R23 BLA offset, NOP, register BLA +2, NOP, R10 NOP NOP
SMITH v2 also added two directives:
; arbitrary text comprising a source comment ; Kilroy was here REP int OPCODE [destination[, source[, length]]] REP 50 STOP
MOV will assign a register a value without modifying it.
TTY forms of
MOV are just a lazy way to refer to some
(potentially complex) system routine for the 'usual' input and output
character streams, so the program can communicate (in some primitive
fashion) with the user.
* forms of
MOV facilitate calculating absolute
addresses of subroutines. Actually,
* is more like a macro which
expands to the current line number in the source file.
"string" form of
MOV moves each character of the immediate
string into a successive register. If
R0 contained 7, then
MOV R[R0], "cat" would result in
R7 == 'c', R8 == 'a', R9 == 't'.
MUL will subtract or multiply a register by a value,
NOT will boolean-negate a register (false = 0/zero, true
COR is the truly interesting opcode; it stands for
Register. The value of the length operand (which is always in a
register) is a count of instructions. This many instructions is copied
from the source offset (which may be immediate or in a register) to the
destination offset (which is always immediate), modifying the program
(thus, self-modifying code.)
Note: prior to version 2007.0722 of the SMITH language, the result of actually overwriting existing instructions with other instructions was not defined. The original idea was that SMITH programs would merely extend themselves by copying bits of themselves to just past the end of the program, like Sylvester chasing Tweety around the Christmas tree on a toy train -- and I still think that's all that's needed for SMITH to be Turing-complete. However, since the language does reasonably claim to be fully "self-modifying" and not just "self-extending" (SEITH?!?), it's official: as of version 2007.0722, you can overwrite instructions with other instructions using
COR. Even when the source and destination ranges of such a copy overlap, the resulting series of instructions at the destination should be an exact copy of the series at the source.
Note note: It seems some of you are having trouble understanding the version system being used for SMITH, which is eminently understandable given that it is completely inconsistent. The first version had no version. The second version, released a scant few days later, containing many new instructions, was "v2". That version was re-christened "version 2.0L" when we added the BSD license to it (because "L" is for "license", y'see?) The third version, released a scant few years later, was "version 2007.0722". This was back when we thought date-based version numbers could substitute entirely for sequence-based version numbers. This version was also known as "version 2.1 revision 2007.0722" when we dropped that idea. The current version, which differs mainly in that its documentation contains this paragraph, is version 2.1-2012.0916. Your knowledge is now complete. Go home.
BLA is kind of a special version of
COR that makes some programming
a lot easier. It stands for
BLAnk and as part of it's very special
format it takes an immediate opcode as its second argument. It copies
that opcode (which must be either
STOP) to the offset, and
uses the number found in the length register as a multiplier.
Execution starts at the beginning of the program (well, naturally,) and
stops when the program counter tries to execute beyond the last
instruction specified in the program. A
STOP instruction will also
serve this purpose, if you choose to use it.
So there you go. Myth debunked. You don't need
or anything so fancy to be Turing-Complete. All you need is to be able
memcpy yourself! Don't that just take the cake?