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
It can probably be shown that Ypsilax is Turing-complete through a reduction from or simulation of Thue. However, this has not yet been attempted. (A possible complication here is that both sides of every Ypsilax rule must be the same size, while this is not the case for rules in Thue.)