Turn Left

From Esolang
Jump to navigation Jump to search

Turn Left is a reversible esoteric programming language in the 1L family which was originally created by "averaging" two other esoteric programming languages, Turnfunge and Nopstacle. The person who did so, User:ais523, is not convinced that averaging esoteric programming languages is a meaningful or even definable concept in most cases, but it seemed to make sense here (in Turnfunge, the IP turns if it has a non-NOP behind it; in Nopstacle, it turns if it has a non-NOP in front of it; and in Turn Left, it turns exactly on the non-NOP).

Although seemingly a more natural construction than those of Turnfunge and Nopstacle, its reversibility makes it somewhat harder to prove Turing-complete than those languages.

Specification

A Turn Left program is a rectangular grid of cells, each of which contains one of two instructions: an empty instruction ; or a "turn left" instruction G (inspired by Sansism). As in Nopstacle, the program is tiled infinitely rightwards and downwards to make a quarter-infinite plane; the area above and to the left of the program is filled with G.

The topmost row of the program must consist entirely of empty instructions. Program execution starts with the instruction pointer moving leftwards from an arbitrary point on that row (but to the right of the leftmost edge of the program – the exact location doesn't matter because the program will behave the same way regardless). Empty instructions are NOPs – the instruction pointer continues moving in the same direction. The "turn left" instruction causes the instruction pointer's movement direction to rotate 90° anticlockwise (so, e.g., if it moves upwards into a G its next step will be to the left from that G).

There is no state in the program other than the instruction pointer. (However, because the program is tiling a quarter-infinite plane, there are infinitely many places the instruction pointer can be, making it possible to store information using the instruction pointer's location, in the style of Nopfunge or Tip.)

If the instruction pointer is ever moving along a ray with only empty instructions ahead of it forever (i.e. it is moving to the right along a row that was copied from an empty row in the original program, or downwards along a column that was copied from an empty column in the original program), the program halts. Interpreters are encouraged to output some information about the state of the program when it halted.

Reversibility

Turn Left is reversible, in the sense that given a program, together with its instruction pointer location and direction, it is possible to work out where the instruction pointer was on the previous step, and thus to run a program backwards until it reaches its original state. Reversing a program can be accomplished via reversing the instruction pointer's movement direction and replacing the "turn left" instructions with "turn right" instructions; or alternatively by transposing the program (together with the instruction pointer and its movement direction) then reversing the instruction pointer's movement direction.

Computational class

Turn Left is Turing complete, because it can almost directly implement the 2-counter version of Bouncy Counters (with one start side, and halting when a stop side bounces, restrictions that do not affect Turing-completeness). Each side that affects one of the counters is mapped to a column, and each side that affects the other counter is mapped to a row; counterpart sides are placed in adjacent columns (with the increment to the left of, or below, the decrement), but otherwise the sides are spaced out sufficiently to allow the rest of the construction to work. The start side is the second row (with its counterpart being the empty first row), and likewise the counterparts of stop sides are left empty. Points that are in a side row/column (other than a start/stop side's counterpart), and also at the edge of the program, are called "side edges"; a side edge is "inbounds" if it is at the bottom or right of a decrementing side or top or left of an incrementing side, and "outbounds" otherwise.

Because it is possible to turn right using three turn left instructions, and because the sides can be spaced arbitrarily far apart, it is possible to connect any inbounds side edge to any outbounds side edge (in the sense that if the instruction pointer approaches from the inbounds side edge it will leave through the outbounds side edge), as long as each side edge connects to only one other. The side definitions of the Bouncy Counters program obey this restriction; and if the side edges are connected by connecting the inbound side edge of the left-hand side of each rule definition to the outbound side edge of its right-hand side, then the Turn Left program will directly implement the Bouncy Counters program:

  • The value of the counters is stored by looking at which copy of the original program contains the instruction pointer, with the copy's vertical position storing one counter and its horizontal position storing the other;
  • Allowing execution to leave via an outbound side will generally decrement (moving left or up) or increment (moving down or right) the corresponding counter, performing a counter change, by moving to the next copy of the program; and then the connection from the opposite inbound side will move to the next side, implementing the basic rule of Bouncy Counters execution;
  • Attempting to decrement a counter below 0 will move to the G filler beyond the topmost or leftmost edge of the program, at which point the instruction pointer turns left twice, moving in the opposite direction in an adjacent column/row, which corresponds to the inbound edge of the counterpart side, i.e. emulating a counter bounce;
  • The startup and halt conditions match (with Turn Left's startup state corresponding to Bouncy Counters's, and likewise the halt states corresponding).

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Turn_Left&oldid=142684"