Beturing

a Befunge-flavoured Turing(-esque) machine

Chris Pressey, June 2005

Introduction

Beturing is a programming language based on a "universal" Turing machine with an unbounded, 2-dimensional "tape". (The Turing machine on which it is based is "universal" in the sense that the machine's state transition diagram is stored on the "tape" along with the data.)

General Layout

This 2-dimensional "tape" is where all the action happens; it is called the playfield and is divided into discrete units called cells. Each cell may store exactly one of a number of symbols drawn from a finite alphabet.

There are two "heads" that access the playfield, one of which (the data head) reads and alters the data (like in a common Turing machine,) the other of which (the code head) reads the state transition diagram.

The state transition diagram is made up of codes. Each code is a 2x2 block of cells in the following form:

The code head is considered to be over a code when it is over the upper-left cell of it. The names and meanings of the four parts of the code are as follows:

• The upper-left cell of a code contains a symbol to look for, called the seek symbol. All symbols are valid seek symbols.
• The upper-right cell of the code contains a symbol to replace it with, called the replacement symbol. All symbols are valid replacement symbols.
• The lower-left cell of the code contains an indication of how to move the data head, called the data head movement operator. The set of valid data head movement operators is {>, <, ^, v, ., *}.
• The lower-right cell of the code contains an indication of what to do with the code head, called the state transition operator. The set of valid state transition operators is {>, <, ^, v, /, @}.

Syntax

When a Beturing playfield is loaded from source such as a text file, lines are translated to rows in the playfield. The first line is loaded at (0, 0), and subsequent lines are loaded at (0, 1), (0, 2), etc. Lines which begin with a # are not loaded into the playfield. Certain lines that begin with #, listed below, are directives meaningful to any Beturing interpreter. The rest may have a local interpretation (such as the #! convention on Unix systems,) or be ignored. A line which begins with ## is guaranteed to be ignored.

• Lines of the form # @(x, y) where x and y are integers reposition the loading of the text file; subsequent lines will be loaded into the playfield at the given position.
• Lines of the form # C(x, y) specify the initial position of the code head. The last such line is the one that takes effect.
• Lines of the form # D(x, y) specify the initial position of the data head. The last such line is the one that takes effect.

Semantics

When a Beturing machine is set in motion, it interprets the code under the code head, transitions to a new state by moving the code head, then repeats indefinitely until the machine enters the halt state.

Here is how each code is interpreted:

• If the data head movement operator is the special symbol *, the following things happen:
  • The code head is moved by the positive interpretation (x2) of the state transition operator.
• Otherwise, if the symbol under the data head matches the seek symbol, the following things happen:
  • The replacement symbol is written to the cell under the data head.
  • The data head is moved by the positive interpretation of the data head movement operator.
  • The code head is moved by the positive interpretation (x2) of the state transition operator.
• Otherwise the symbol under the data head does not match the seek symbol, and the following things happen:
  • The code head is moved by the negative interpretation (x2) of the state transition operator.

The positive and negative interpretations of the data head movement and state transition operators are given below:

Note that "x2" in the rules given above means to advance two cells in the given direction; this is used everywhere for moving the code head because codes are 2x2 cell blocks.

Discussion

The Beturing language was designed (in part) as a test of the wire-crossing problem, in the following manner.

Note that the code head does not have "direction" or "delta" state as the instruction pointer does in Befunge; it has only "position" state. Its next position (and thus the machine's next state) is determined entirely by the state transition operator of the current code.

Note also that there is no "leap over" state transition operator (like # in Befunge.) Therefore the next state must always be reachable by a continuous, unbroken path through the playfield.

This means that a Beturing machine is incapable of having a state transition diagram that, when rendered on a 2-dimensional plane, requires that two edges cross. (A state diagram with, e.g., 5 states, and a transition from each state to every other state, appears to have this property (although it would be nice to have a reference to a watertight proof of this...))

This might mean that it is impossible to construct a true universal Turing machine in Beturing, if a universal Turing machine requires a state diagram which has edges that cross when rendered in two dimensions.

If this were the case (and it may well be) then Beturing would not be Turing-complete, and in fact its level of computational power would probably be difficult to determine.