SMETANA
SMETANA, the Self-Modifying Extremely Tiny AutomatoN Application, is a language operating on a series of steps, with two instructions. It was invented around 1994 by Chris Pressey. "Smetana" means "sour cream" in Russian and Ukrainian languages. It also means "cream" in Czech and is the surname of a Czech composer.
Example
SMETANA programs look like this:
Step 1. Go to step 4. Step 2. Swap step 3 with step 5. Step 3. Go to step 6. Step 4. Swap step 1 with step 6. Step 5. Go to step 2. Step 6. Swap step 1 with step 2.
Commands
The syntax of SMETANA is described as follows:
Smetana ::= Step {".\n" Step} ".".
Step ::= "Step" Integer "." (GoTo | Swap).
GoTo ::= "Go" "to" "step" Integer.
Swap ::= "Swap" "step" Integer "with" "step" Integer.
Integer ::= "0".."9" {"0".."9"}.
The program will start from step 1 [1] and proceed to either the target of GoTo instruction or the next step (current step + 1)[2].
A program ends when it tries to execute step n+1, where n is the number of steps given in the source.
The behavior of trying to execute steps n+2 and beyond, or those before step one, is not defined. The behaviour of swapping steps n+1 and beyond, or those before step one, is likewise not defined. The reference implementation, however, simply stops.[3]
Also not addressed is how SMETANA takes input or produces output. It is generally assumed that input must be encoded into the initial configuration of the program, and the output decoded from the final configuration.
Computational class
Consider a SMETANA program with n steps. The possible states of the program are determined solely by its current step (n possibilities) and the arrangement of its steps (n! possibilities) - this is a total of n*n! possible configurations.
However, SMETANA is not explicit about the limits of n, and we can technically take it to be either finite or infinite.
Taking n to be finite is the usual case (since most definitions of algorithms define them to be a finite number of steps, and SMETANA programs are usually considered to be algorithms of a sort). We can argue, for example, that if the program will only halt when it tries to execute the n+1th step, then either n must be finite, or the program can never halt - and if it never halts, it can presumably never produce output.
If we take n to be finite, then the total number of possible configurations is bounded as well, putting SMETANA in the computational class of bounded-storage machines with bounded input (i.e. linear bounded automata).
On the other hand, if we take n to be infinite, we could make a case for SMETANA being Turing-complete, but it would need to invoke two phenomena: a way to determine the contents of all the steps which are not explicitly defined by the program, and some way for it to fulfill an alternate halting condition (or, to produce output even though it does not halt - but then how do you know if that is the final output?) Interestingly, these two phenomena are often invoked when reasoning about the computational abilities of cellular automata, so it is not entirely out of the question. However, they are also undefined for SMETANA, and such an argument could be seen as relying on non-standard extensions to the language.
Related languages
Nikita Ayzikovsky created a compiler which translates programs from the Brainfuck-like language Smallfuck into SMETANA. While this is an impressive feat, Smallfuck is also a bounded-storage machine without interactive input; as such, the existence of the compiler reinforces the first conclusion listed above.
SMITH is a (fairly distant) descendant of SMETANA which is much more definitively Turing-complete.
SMATINY is based on the same swapping principle as SMETANA, and features output.
SMETANA To Infinity! is an extension of SMETANA which has a way of specifying infinitely many steps, and also has a facility for output. SMETANA To Infinity! is mostly backwards-compatible with SMETANA: every valid SMETANA program (except for programs which mention "step 0") is also a valid SMETANA To Infinity! program, whose behavior is consistent with the behavior of the original program. SMETANA To Infinity! is probably Turing-complete.