SMITH

From Esolang
Jump to: navigation, search

SMITH, for Self-Modifying Indecent Turing Hack, is an esoteric programming language designed by Chris Pressey in 2000. It has no jumps whatsoever; the instruction pointer can only be incremented, and only by one instruction at a time. As a substitute for loops, the language allows code to be copied forward where it will be executed in the future.

SMITH was designed for two purposes: as a more powerful descendant of SMETANA, and to one-up Bullfrog's partial lack of jump instructions.

SMITH# is a descendant of SMITH which comes closer to being a Turing tarpit.

Syntax and Semantics[edit]

Syntactically, SMITH resembles assembly code on a generic microcomputer. The specific syntax was loosely modelled after an imaginary register machine language described in "Compilers: Principles, Techniques, and Tools" (a.k.a. the "Dragon" book.)

From this starting point, however, SMITH fails to include any branching instructions. It makes up for this by adding the instruction COR, which stands for "COpy by Register". The purpose of COR is to provide a way to copy previously-executed instructions from the program into storage from which the program will be executed in the future. In this way, repetition of execution of code can still be achieved, despite the lack of branches.

Conditional repetition can be achieved via the single register operand of COR, which controls how many instructions are copied. If this value is zero, no instructions are copied; this can be used to simulate failing to meet a condition, especially in conjunction with the MUL instruction.

Since implementing a loop in SMITH requires only that part of the program is copied past the end of the existing program, the case of overwriting existing program contents with COR was not considered during design. This behaviour was therefore undefined (and, in the reference interpreter, happened to be implemented contrary to reasonable expectations) until version 2.1 (a.k.a "version 2007.0722") of the language.

Computational class[edit]

When it was designed, SMITH was believed to be Turing-complete. It imposes no limit on the number of registers, nor on the amount of information each register may contain. Also, copying (possibly zero-length) sections of already-executed code forward should be strictly equivalent to looping and branching in conventional programming languages.

This remained unproved, however, until September of 2012. On September 9, Chris Pressey wrote a sketch of a proof that SMITH is Turing-complete which shows how a 2-symbol, 3-state Turing machine could be implemented in SMITH. (It is only a sketch because it leaves it up to the reader to extrapolate how to implement an arbitrary 2-symbol Turing machine.) On September 11 2012 Keymaker provided a method and a Python program for translating Minsky machines to SMITH, constituting a much more formal proof.

External resources[edit]