Kelxquoia is an esoteric programming language designed by Chris Pressey on December 23, 2010. It is a self-modifying, in fact self-destroying, language which combines grid-rewriting with remotely fungeoid playfield traversal.
There is an instruction pointer (IP) with a location and a direction in an unbounded, two-dimensional Cartesian grid of symbols. As the IP passes over symbols, it executes them and erases them from the playfield (overwrites them with blanks). The program ends when the IP travels off into space, never to return.
There is a stack. The stack may contain objects of two types, grids and rows. Instructions expect certain types of objects to be present on the stack; if the types are incorrect, or insufficient elements are on the stack, the instruction has no effect. (That means that the state of the stack, too, is unchanged by the instruction.)
If the IP passes over any symbol x, and there is a
' symbol to the right
of the IP's line of travel, a row is popped from the stack, the symbol x is
appended (to the rightmost position) of that row, and the new row is pushed
back onto the stack. The symbol x is erased, but the
' is not.
- pushes an empty row onto the stack.
+ pushes an empty grid onto the stack.
* pops a row, pops a grid, appends the row to the bottom of
the grid, then pushes the new grid. Note that the left-hand edges of every
row in a grid line up, but their right-hand edges need not do that. When
considered as a grid, all unused squares in the grid are considered to contain
? pops a row from the stack, appends a wildcard to it, and
pushes the new row back onto the stack.
/ pops a grid called the replacement, then pops a grid
called the pattern, then replaces all non-overlapping occurrences of the
pattern in the playfield with the replacement. All overlapping occurrences
are untouched, to avoid ambiguity. A few things to note:
- The replacement must not be any larger than the pattern. If it is, the two grids remain popped but the instruction otherwise has no effect.
- If the replacement is smaller than the pattern, it is padded with blanks (to the bottom and to the right.)
- There can be at most one wildcard in the pattern. If there are no wildcards in the pattern, there should be none in the replacement. If either of these conditions does not hold, the two grids remain popped but the instruction otherwise has no effect.
- Any symbol in the playfield may match the wildcard in the pattern. Where-ever there is a wildcard in the replacement, the symbol that matched the wildcard in the pattern is substituted instead.
- If the executed
/instruction itself is replaced by something during this process, whatever it was replaced with will not be erased.
- If the pattern consists only of blanks, or only wildcards, the implementation may choose to halt the program rather than filling the entire playfield with replacement.
v cause the IP to begin travelling east,
west, north, and south, respectively.
! clears the stack.
Executing any other symbol as an instruction has no effect.
$ indicates the initial position of the IP. The initial
direction of the IP is always east. If there are multiple
$ symbols in the
source code, it is an error and the program is not executed.
The author believes Kelxquoia to be Turing-complete because:
- Repeated use of the
/instruction can be used to implement non-overlapping grid-rewriting, which can simulate an arbitrary Turing machine; see below.
- Assuming all instructions that have been erased after execution can be
restored, the IP can travel in a loop, to indefinitely apply the
- Instructions that have been erased after execution can be restored by further rewrites of a certain, fixed form.
- To effect a conditional halt, a critical direction-changing instruction can be selectively not restored to the playfield.
Simulating a Turing Machine with non-Overlapping Grid-Rewriting
In this section we show how a Turing machine can be simulated with
grid-rewriting where we can match only non-overlapping instances of a pattern.
(The addition of wildcards does not add any computational power, but does add
some expressivity, as it can reduce the number of rewrites that need to be
made.) The tape symbols of our machine will be the digits
9, and the
states of the finite control will be labeled with the lowercase letters
z. In addition we will use the
. symbol to depict whitespace, for
We can depict each tape cell with the following 2x2 grid of symbols:
We arrange the tape cells horizontally in the playfield, and we make sure there is only one such tape:
We have rewriting rules that extend the tape in either direction, as needed:
?T.. -> ?T0T T+.. T+T+ ..?T -> 0T?T ..T+ T+T+
We situate the tape head directly below the cell of the tape we wish to affect, and again we make sure there is only one such head. The tape head looks like the following 2x2 grid:
The upper-left corner contains the finite control label, and the lower-right corner contains a "movement indicator". When the head is ready to move, the movement indicator is changed, and we have the following two rewrite rules implement the move:
?H.. -> ..?H HR.. ..HN ..?H -> ?H.. ..HL HN..
Now, for each transition rule in the Turing machine, we can compose a
grid-rewriting rule which implements it. For example, "In state
there is a
5 on the tape, write a
7 and move left" corresponds to the
5T -> 7T T+ T+ fH fH HN HL
From this description it should be fairly evident that this both simulates a Turing machine (not quite arbitrary, but certainly with sufficient symbols and states to be universal) and that the non-overlapping condition poses no obstacle (if the tape and head are arranged as described, these patterns will never match overlapping instances of the playfield).
The following example replaces the words
POP, at the bottom of
the program, with
$+-W*-P*+-B*-M*/ ' ' ' ' WOW POP
The state of the playfield at the end of the program would be:
$ ' ' ' ' BOB MOM
The following example rewrites some stuff then restores the instructions that did the rewriting:
+-0 0*+-1*/+-?*-R*- *+-?*-R*-?*/ RRRRRRRRRRRRRRRRRRR RRRRRRRRRRRR $+-0 0*+-1*/+-?*-R*- *+-?*-R*-?*/ ' ' ' ' ' ' 00 00 00 00
The following example extends the previous example to an infinite loop:
>+-0 0*+-1*/+-?*-R*- *+-?*-R*-?*/v RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRR $>+-0 0*+-1*/+-?*-R*- *+-?*-R*-?*/v ' ' ' ' ' ' ' ' ' ^ /*?-*P-*?-+*?-*P-* -+ < P PPPPPPPPPPPPPPPPPP PP P ^ /*?-*P-*?-+*?-*P-* -+ < 00 00 00 00
The contents of this document were taken from the Kelxquoia article on the esolangs.org wiki, which is in the public domain.