Ypsilax
Ypsilax, invented by Chris Pressey in 2001, is a reflective (i.e. potentially self-modifying), non-deterministic esoteric programming language based on grid-rewriting. Both the program and its state are rendered as symbols in a grid; in this manner, rules may rewrite the state, other rules, or both.
Program form
Each Ypsilax program is an unbounded two-dimensional grid of cells, each of which can contain a single symbol from a finite alphabet.
The rewriting rules in an Ypsilax program are two-dimensional structures located in this grid. Each of these is delimited by parentheses above and to either side of it; also, it must be twice as wide as it is high. For example, a rewriting rule which rewrites A symbols to B symbols:
( ) AB
A critical property of these rewriting rules is that they will only rewrite things below them; never above or on the same line. In this manner, a hierarchy of rewriting rules can be formed, some of which rewrite other rewriting rules. For example, the following rule would rewrite the above rule into a different rule:
( ) ( )( ) AB CD
(Note that this rule is in fact eight cells wide by four cells high, even though the bottom two lines are filled with blanks.)
Computational class
Ypsilax is Turing-complete because it can directly implement an arbitrary Turing machine. The Turing machine tape can be represented using two adjacent rows of the grid: the top row represents the symbols (where the "blank symbol" that fills the unvisited potion of the tape is represented by an Ypsilax blank symbol), and the bottom row specifies the state and the location of the tape pointer: it is mostly blank, but the symbol directly below the location of the tape pointer is a non-blank symbol specifying what state the Turing machine is in. Each non-halt Turing machine transition then compiles into a number of rewrite rules equal to the number of symbols: there is one rule for each symbol it could be moving onto, because although that symbol is meaningless to how the Turing machine operates, it exists within the 2×2 bounding box of the machine's output, and thus a rewrite rule is needed for every possible value of that symbol. (Halt transitions are left out of the compilation, so that the Ypsilax program has no matching rewrite rules at that point.)
For example, the 2-symbol 4-state busy beaver Turing machine:
| A | B | C | D | |
|---|---|---|---|---|
| 0 | 1→B | 1←A | Halt | 1→D |
| 1 | 1←B | 0←C | 1←D | 0→A |
compiles to the following Ypsilax program:
( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) 1 111 1 1 11 1 111 1 1 1111 1 111 1 1 1111 1 11 1 A B A B BA BA D D D D AB AB BC BC CD CD D A D A A