What is xTuringMachine?

I will not try to explain the concept of Turing machines in any detail, but the basic idea is simple enough:  A machine wanders along an infinite tape that is divided into squares.  Each square is either blank or contains a single symbol.  The Turing machine can read, write, and erase symbols.  In xTuringMachine, the possible symbols are i, o, x, y, z, and $.  The symbol "#" is often used to represent a blank space.  The Turing machine has a "state" which is simply a number.  In xTuringMachine, the state is a number between 0 and 19.  A Turing machine can also be in a special state called the "halt state", which is indicated in xTuring Machine by "h".

The Turing machine has a "program", which is just a set of rules.  Each rule takes the form: "If you are in such-and-such a state and if you read such-and-such a symbol, then write such-and-such a symbol, move one square in such-and-such a direction, and change to such-and-such a state."  Thus each rule is determined by 5 pieces of information:  Current state, current symbol, symbol to write, direction to move, and new state.  When you run xTuringMachine, you will see a table with 5 columns.  Each row of this table represents one of the rules of the Turing machine. You "program" the machine by constructing this table. To "run" a Turing machine, it is started in state number 0 on a tape containing some "input data".  It then "computes" by following its rules until it enters the halt state.  At that point, it stops running, and the contents of the tape represent the "output" of the computation.

Although Turing machines are very simple, they can perform any computation that can be performed by any computer (given enough time--and more states than you are allowed to use in xTuringMachine). This is hard to believe at first, but some of the sample machines perform reasonable non-trivial computations.

Eck, David. (1995). READ ME - Includes Instructions. Electronic Document.

Download xTuringMachine for Mac

Architecture

Motorola 68K

Compatibility notes

Emulating this? It could probably run under: Basilisk II