Metropolis
Metropolis is a 2D Turing Machine language designed by Brian Thompson in 2006. It was originally inspired by Langton's Ants, but later refined on the more general idea of Turmites (also called Turning Machines) - the two-dimensional equivalent of Turing Machines.
Syntax
A Metropolis program operates by specifying a symbol transition table that tells Metropolis how to interpret the symbols at each grid cell. Each symbol may be any printable ASCII character, and the rules specify both which direction the program should turn, and what symbol should replace the current symbol. An example to implement Langton's Ant is given here:
S0 RS Dir WS S1 0 ' ' L * 0 0 * R ' ' 0
In this table, S0 and S1 stand for State0 and State1 - the state of the program when it encounters the symbol, and the state when it leaves the symbol. Langton's Ant does not utilize any states, so they are left as 0 for now. RS is called the Read Symbol, and WS is the Write Symbol - which identify initial and final symbol values for each cell. The Dir column signifies which direction to turn when leaving the cell. For Langton's Ant, when it encounters a space it changes it to an * and turns left, while when it encounters a * it unmarks it and turns right. Any characters not specified by the rules table, including spaces, have an implicit "Do nothing" transition, which makes the program continue straight past the cell without changing the symbol or the state. The following is the actual syntax used in Metropolis:
{S0,S1}[RS,WS,Dir]
States can be any string that does not include [,],{,},%,spaces, or commas. Symbols may be ANY single printable ASCII character. - including spaces. Lastly, the direction may be L, R, S (straight), or B (backwards). Allowances may be made in the final implementation for 45-degree angles as well.
Non-determinism
To add non-determinism to the language, multiple transition rules for the same symbol can appear. Each one may be proceeded by a % sign and a positive integer which identifies the weighting of the transition.
{S0,S1}[RS,WS,Dir]%Weight
Computational Class
Metropolis is Turing complete, since it can simulate any ordinary Turing machine with 95 symbols or less by travelling along a single line: Split each state into two versions according to which direction the machine is moving in, and use S and B directions as appropriate.