Beturing is a "Befunge-flavoured" language for describing Turing machines; both the tape and the finite control are laid out two-dimensionally. In addition, the finite control must be expressed as a planar graph (no edge representing a transition may cross any other edge.) It was devised this way as a test of the so-called "wire-crossing problem". It turns out that there are universal Turing machines with finite controls that are planar graphs, so Beturing is Turing-complete.
Sample Program
# D(40, 4)
# @(40, 4)
$bbab$
# C(0, 0)
# @(0, 0)
. . . . . .
*v*<*<*<*>*v
aa .ab . .aa .
>/*>./*^*^</*v
bb .ba . .bb .
>/*^./*^*^</*v
$$ .$$ . .$$ .
>/*^</*>*^.@*v
. . .
*@ *^*<*<
Computational Class
Programming Paradigms
Documentation
Implementations
-
beturing.lua, an interpreter in Lua
To run this implementation, you need:
Download
Development
Github: catseye/Beturing
Bitbucket: catseye/beturing
Issue tracker: on github