catseye  committed cdd3358 Draft

Initial import of description of Kelxquoia.

  • Participants
  • Branches default

Comments (0)

Files changed (1)

File README.markdown

+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
+Program State
+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.
+The instruction `-` pushes an empty row onto the stack.
+The instruction `+` pushes an empty grid onto the stack.
+The instruction `*` 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
+The instruction `?` pops a row from the stack, appends a wildcard to it, and
+pushes the new row back onto the stack.
+The instruction `/` 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. 
+The instructions `>`, `<`, `^`, and `v` cause the IP to begin travelling east,
+west, north, and south, respectively.
+The instruction `!` clears the stack.
+Executing any other symbol as an instruction has no effect.
+The symbol `$` 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.
+Computational Class
+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 `/`
+    rewrites.
+*   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 `0`-`9`, and the
+states of the finite control will be labeled with the lowercase letters
+`a`-`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:
+    0T
+    T+
+We arrange the tape cells horizontally in the playfield, and we make sure
+there is only one such tape:
+    0T0T1T2T3T0T0T
+    T+T+T+T+T+T+T+
+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:
+    aH
+    HN
+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 `f`, if
+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 `WOW` and `POP`, at the bottom of
+the program, with `BOB` and `MOM`:
+    $+-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*-?*/
+    $+-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
+    $>+-0 0*+-1*/+-?*-R*- *+-?*-R*-?*/v
+        ' '   '       '  '      '   
+                 '         '  '     
+     ^      /*?-*P-*?-+*?-*P-* -+     <
+     ^      /*?-*P-*?-+*?-*P-* -+     <
+     00 00 00 00
+The contents of this document were taken from the Kelxquoia article on the wiki, which is in the public domain.