Turing

A Non-Deterministic Multi-Tape Turing
machine is like a Turing machine but it
has several tapes and its set of rules
may prescribe more than one action to
be performed for any given situation.

What is it?

It’s just another Turing machine simulator. It can handle non-deterministic events and there is no limit to tapes number.

Development

It could be a good starting point for a more complete and complex Turing machine simulator.

If you find a bug or just want to contribute to the project, feel free to do it.

Syntax

The first line of the program file must be the input (without starting symbol).
Then, each line consists of:

state; configuration; relation

Where,

• state is a string which represents the name of the state;
• configuration is a sequence enclosed between two brackets where each elements is separated by a comma. The i-th element represents the character on the i-th tape;
• relation is a relation (not necessarily a function). It is represented by a sequence enclosed between two brackets where each elements is separated by a comma. The first element is the state where the Turing machine will go if it is in the state state and has the configuration configuration. Then, there are a two elements of each tape. The first one, for each tape, represents the character which will be written by the head of this tape. The second one, for each tape, represents the direction where the head of this tape will go, in particular:
  • R for right;
  • L for left;
  • - don’t move;

Reserved Characters

Char	Meaning
>	Starting symbol
_	Blank symbol
s	Initial state
H	Halt: final state
Y	Yes: final state
N	No: final state

An example

Check if a binary string is not a palindrome one.

001100
s; (>, >); (s, >, R, >, R)
s; (1, _); (s, 1, R, _, -)
s; (1, _); (s, 1, R, 1, R)
s; (0, _); (s, 0, R, _, -)
s; (0, _); (s, 0, R, 1, R)
s; (_, _); (b, _, L, _, L)
b; (1,1); (b, 1, L, 1, L)
b; (0,1); (b, 0, L, 1, L)
b; (1, >); (z1, 1, L, >, R)
b; (0, >); (z0, 0, L, >, R)
b; (>, >); (N, >, R, >, R)
z0; (1, 1); (z0, 1, L, 1, -)
z0; (0, 1); (z0, 0, L, 1, -)
z0; (>, 1); (q0, >, R, 1, -)
z0; (1, _); (z0, 1, L, _, -)
z0; (0, _); (z0, 0, L, _, -)
z0; (>, _); (q0, >, R, _, -)
z1; (1, 1); (z1, 1, L, 1, -)
z1; (0, 1); (z1, 0, L, 1, -)
z1; (>, 1); (q1, >, R, 1, -)
z1; (1, _); (z1, 1, L, _, -)
z1; (0, _); (z1, 0, L, _, -)
z1; (>, _); (q1, >, R, _, -)
q0; (1,1); (q0, 1, R, 1, R)
q0; (0,1); (q0, 0, R, 1, R)
q1; (1,1); (q1, 1, R, 1, R)
q1; (0,1); (q1, 0, R, 1, R)
q1; (1, _); (N, 1, -, _, -)
q1; (0, _); (Y, 0, -, _, -)
q0; (0, _); (N, 0, -, _, -)
q0; (1, _); (Y, 1, -, _, -)

License

MIT