Beturing
Beturing is an esoteric programming language devised by Chris Pressey in 2005; it is described as a "Befunge-flavoured Turing machine".
Both the "tape" and the control mechanism exist in an unbounded two-dimensional space. The control mechanism consists of codes, each of which is 2x2 cells. There are two "heads", a data head which works more or less traditionally, and a code head which reads, and transitions between, codes.
There are three major differences in the behaviour of the code head and the behaviour of Befunge's instruction pointer:
- The code head has no concept of 'direction' - each move it makes is directly determined by the code that is under it;
- There is no wrapping around the edges of the playfield; and
- There is no way for the code head to 'jump over' a cell.
In this manner, the motion of the code head - and thus the form of the control mechanism - is restricted to a planar graph. This was in part an intentional test of the wire-crossing problem (as it relates to the control mechanism of a Turing machine, at any rate.) However it looks likely that a universal Turing machine can be constructed in Beturing in spite of this restriction.