Stun Step

Stun Step is an esoteric programming language created by User:ais523 in 2018, inspired by Ørjan Johansen's minimalization of Home Row. The resulting language is fairly similar to Brainpocalypse, but has different control flow (and a much simpler proof of Turing completeness, meaning that there's a chance it'll be efficient to write programs in).

Specification

A program consists of a sequence of commands. The program stores data on a tape of unbounded nonnegative integers. Perhaps unusually, these integers are initialised to 1, not 0 (other than the tape element that the data pointer initially starts on, which is initialised to 0). The tape itself does not need to be unbounded for the language to function, as long as it's sufficiently long; as in Home Row, it fits in best with the rest of the language to have it as a closed loop, with the two ends adjacent. As in brainfuck, there's a data pointer which points to a "current tape element".

The language has four commands, which are very similar to those of brainfuck and Brainpocalypse:

• +: increment the current tape element
• -: decrement the current tape element (decrementing 0 is undefined behaviour)
• >: move the data pointer to the right if the current tape element is nonzero (otherwise do nothing)
• <: move the data pointer to the left if the current tape element is nonzero (otherwise do nothing)

The language has no explicit flow control. Rather, at the end of the command sequence, the program will halt if the current tape element is 0, or loop back to the start otherwise (i.e. there's an implicit "goto the start of the program if the current tape element is nonzero (otherwise halt)" at the end of the program).

Minimalization

It's impossible for any tape element, other than the one the data pointer is pointing to, to be zero (because you can't move the data pointer away from a zero element). As such, < is clearly unnecessary when the tape has a known finite length, as you can replace it with an appropriate number of > instead. This reduces the number of commands to three. It's also possible to combine - and > into a single command with the semantics of -> (which could be called, e.g., \); you can then implement > as +\, < in terms of >, and - as \<.

Unlike the four-command version, the minimalization is a subset of Home Row: > is Home Row's a, and \ is Home Row's sjf. (However, Stun Step itself is not a subset of Home Row because the tape length is not locked to being 5 elements long, and more elements are likely to be necessary for Turing-completeness. Additionally, Home Row does not have an implicit loop around the program, but it's easy to write one explicitly.)

Reversibility

One unusual property of Stun Step, compared to most Turing tarpits, is that all its commands are reversible (in the sense that if you know what the current state of the program is, you can determine what the state of the program was before the previous command was run).

Given a state of a running Stun Step program, you can determine the previous state as follows:

• Move the instruction pointer backwards (looping from the start of the program to the end, if the current tape element is nonzero), and look at the command it was pointing to. That's the command that just ran.
• Reverse the effects of that command as follows:
  • If a + just ran, decrement the current tape element (i.e. do -)
  • If a - just ran, increment the current tape element (i.e. do +)
  • If a < or > just ran:
    • If the current tape element is non-zero, it must have moved the pointer (because otherwise the pointer would still be pointing to a zero). So move the pointer the other way (i.e. do > or < respectively).
    • If the current tape element is zero, it must not have moved the pointer (because if it did, the current current tape element would have been 0 before the command was run, and yet not pointed to, which is impossible). So don't move the pointer (i.e. do nothing, or equivalently, do > or <).

It can be seen that not only is the language reversible, but each command has an exact opposite: - directly reverses + and vice versa, and > and < directly reverse each other. (Program fragments in Stun Step thus form a group, in the style of Burro, although just as with Burro, the fact that looping is "external" to the main semantics of the language means that programs as a whole don't compose in the same way.)

Computational class

Proof under construction…

Implementations

An x86 assembly interpreter by User:Bangyen.

See also

• Home Row
• Brainpocalypse