Nopstacle
Nopstacle is an esoteric programming language created by User:ais523 in 2024, inspired by User:Keymaker's Turnfunge. The intent was to produce a language with similar semantics to Turnfunge, but that appealed more to ais523's sense of aesthetics.
The language has some similarities to Black, but is simpler (in particular, it is not self-modifying like Black is, storing data Tip-style in the location of the instruction pointer within infinitely many repeats of the program rather than by modifying the playfield).
Specification
A Nopstacle program is a rectangle of cells, for which each cell is either empty or an obstacle, with the top-left corner empty. Conceptually, this rectangle is copied infinitely rightwards and downwards to create a quarter-infinite plane; the space above and to the left of the rectangle is filled with obstacles.
Program execution makes use of an instruction pointer, which points to a cell of the plane (initially the top-left corner) and has a movement direction (initially downwards). Execution proceeds by repeatedly attempting to move the instruction pointer one cell in its movement direction. If the cell being moved to is empty, the movement succeeds, and the execution continues with the instruction pointer in this new location (and still moving in the same direction). If the cell that would be moved to contains an obstacle, the instruction pointer cannot move there; instead, it remains in position, but its movement direction rotates 90° anticlockwise, and execution continues from the same location, but with this new movement direction.
The program must halt if the instruction pointer ends up stuck in an infinite loop within the same copy of the original program (i.e. it enters a location it has been in since the last time it moved into the current copy of the program, and is moving in the same direction) – however, implementations are not required to detect this halting situation immediately, but rather merely have an obligation to halt eventually if this happens. (For example, a valid algorithm for halting would be "halt if the instruction pointer has been within the same copy of the original program for a length of time equal to the area of the original program × 4".) An implementation may not halt the program unless this situation occurs.
In a file, the rectangle of cells is represented using an ASCII space character for an empty cell, and # for an obstacle, written line-by-line with the lines separated by newlines. (If the lines do not have equal length, an implementation should pad each line to the length of the longest using empty cells.)
Computational class
Nopstacle is Turing complete because it can directly implement Nopfunge Intangible, as follows:
| Nopfunge Intangible | Nopstacle |
|---|---|
|
|
## ##
## ##
## ##
## ##
|
|
|
## ###
## ###
## ##
### ##
|
|
|
## ##
## ##
#
##
## ##
## ##
|
|
|
## ###
## ##
### ##
### ##
|
|
|
## ##
## ##
##
#
## ##
## ##
|
The translation works by using the third column for downwards movement and fourth column for upwards movement, likewise the third row for leftwards movement and fourth row for rightwards movement. At the edge of the plane, the area filled with obstacles will cause the instruction pointer to turn left, and then after its next move, it will turn left again, effectively reversing direction. When encountering empty space in the Nopfunge Intangible program, or when moving in the same or opposite direction as an IP-turning instruction, the row or column the IP is moving along will be entirely empty, so it will continue moving in the same direction. Left turns are implemented directly via the use of an obstacle that turns the IP to the left; right turns are implemented by allowing the IP to continue to the far side of the translation, turning it 180° using two obstacles, and then allowing it to follow the same path as if it had arrived from the other side.
To allow the program to get started, a path needs to be made from the top-left corner of the program. In the Turing-completeness proof for Nopfunge Intangible, the instruction in the top-left corner is always v, and it is trivial to modify the translation of v to work for program startup too:
# ##
# ##
#
#
## ##
## ##
This translation is very similar to the normal implementation of v, but provides space for the IP to reach the fourth row from its starting location.