Blind
Blind is a two-dimensional pattern-matching based language designed by Keymaker in 2011. The language is based on structures that are matched on an infinite field; the structures hold in themselves the coding/data that is to be matched and instructions to modify the field upon a match. Only one match may happen per cycle (but is not required to happen), and the search (from the first structure to the last) begins again -- on the next cycle -- from the first structure. (The field is searched from left to right, from up to down.) The language is fully deterministic.
A program might look like this:
.1..........1 1.1.........1 .1..........1 ..*.. ..x.x *x*x. ..x.x ..*.. .x*. x*x* .x*.
Running it, one will see a 3x3 cell circle-shape moving right until it meets the wall. The program has the initial structure, composed of characters '1' and '.', and two normal structures, composed of characters 'x', '*', and '.'. Initially, once a program is executed, the initial structure will be placed in the center of the field. All the space in the field is unrecognized space initially. The '1' characters in the initial structure change that space into recognized space. Only recognized space can be matched with the structures (and each needs to have at least one cell that is used for matching recognized space). Explanations of the three types of characters a structure may have:
- 'x' is used to match recognized space on the field. If and only if all the 'x's of a structure have a matching recognized space cell, a match occures. The matching recognized space becomes unrecognized.
- '*' flips the underlying space -- unrecognized becomes recognized and recognized becomes unrecognized. Essentially they are the only way to create new recognized cells, but they may also be used to remove recognized space.
- '.' as with the initial structure, '.' is used in forming the structure (every line in a structure must have the equal length). But in normal structures they have the function of indifference to the field -- the field remains as it is wherever '.'s are applied over it.
Now, back to the example. The first actual structure is what determines what happens when the circle is near the wall. The second structure is its movement. In the second structure, a new circle is formed using '*' instructions. 'x's, upon matching the circle remove it, and as '*' create the new one, movement seems to happen. The first shape destroys the wall (all but its middle as '.' is applied there) and the circle, and flips four cells. There is no structure in the program that would match in the resulting field, so nothing will happen on further cycles. (But the program will not end, as Blind programs cannot terminate.)
Computational class
Blind can be caused to implement any 1-dimensional cellular automaton via encoding each colour in the cellular automaton's data array as a set of n uniquely recognisable patterns, where n is the number of cells that depend on any given cell, and all the patterns across all the colours are unique. (In the simple case of nearest-neighbour cellular automata, n is 3). This construction does not initialize more than a finite portion of the cellular automaton tape, so it would need modifications for a rule 110-based Turing completeness proof, but by using more than two colours or more than one neighbour, complex cellular automata that function even in the absence of infinite initialization can be used.
Interpreter
A visual interpreter exists (here) and it is extremely slow. It also does not implement an infinite field but finite, so take caution with things reaching the edge (which should not be there in the infinite field of Blind). The interpreter is initially in the halting state; to run press F10, or alternatively up-key, which runs only one cycle. F9 halts the process, and the before-mentioned keys can start it again. As said, it is an extremely slow piece of software.
External resources
- Blind page (the specs, a few programs, a visual Python interpreter)