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

Stun Step is Turing-complete because Delta Relay can be compiled into it.

The basic idea is for the Stun Step tape to alternate between cells that store the value of a Delta Relay counter (with an offset of 1 – a counter value of n in Delta Relay is represented by a cell with value n+1 in Stun Step), and bit buckets that have arbitrary values greater than or equal to 1. The main body of the program works by doing a "zero test and influence" of each counter in turn, which is implemented as follows (starting from a known pointer location):

1. use < and > to move to each of the bit buckets that are to the right of a cell that this counter negatively influences, and use + to increase those bit buckets by the absolute value of the influence;
2. use < and > to move to the cell that represents the counter;
3. do ->+ (which moves the pointer one cell to the right if the cell was greater than 1, but does nothing if the cell was 1, i.e. the counter was 0);
4. do a sequence of unconditional pointer moves and adjustments that would (if the pointer stayed in the same place in the previous step) adjust all the influenced counters by the amount of influence, returning the pointer back to its location at the start of this step (if the counter was nonzero, i.e. the cell was not 1, this sequence adjusts the bit buckets rather than the counters and thus effectively does nothing; this cannot reduce a bit bucket below 1 because the bit buckets were topped up in step 1);
5. do -<+ (which undoes the ->+ earlier, moving the pointer back to the cell that was zero-tested, so it is now in a known location again).

Because each counter is tested in turn, always in the same order, this naturally handles Delta Relay's rule that when execution reaches a state where there are two zeroed counters, the newly zeroed counter is tested before the previously zeroed counter.

In order to make starting the program work, the Delta Relay program is first simulated until there are two zeroed counters (which can necessarily be done in a number of steps less than the highest initial counter value), and the value of each counter at that point is recorded. The "influence" of the first counter on each other counter is changed to be equal to that counter's recorded value (thus, it effectively changes the set of counters from all-zero – corresponding to Stun Step's all-ones starting state – to the correct starting values as of the first simultaneous zeroing). The merged counter is placed on the first Stun Step tape cell, and the program as a whole is rotated so that execution starts just after the - in step 3 of the merged counter's zero test (which is a one-character rotation, because steps 1 and 2 are both no-ops). This means that at the start of the program, the Stun Step program will think it has just "tested the merged counter and found it to be zero", will then set up the first valid state in which some other counter is also zero, and continue simulating the Delta Relay program from there.

For halting, each halt counter's influence matrix row is changed to positively influence every counter (by an arbitrary positive amount), except that it does not influence itself, and negatively influences the first counter by -1. This influence adjustment will ensure that the halt counter will stay as the only zeroed counter until the first counter becomes zero, at which point the Stun Step program will exit (because it will wrap just after the - of step 3, at which point the current tape cell will be zero if and only if the first counter was 0 before the decrement, i.e. the corresponding cell was 1 before the decrement).

Implementations

An x86 assembly interpreter by User:Bangyen.

See also

• Home Row
• Brainpocalypse