A swift Turing machine simulator

Installation and usage

Installation

make
make demo
sudo make install

Usage

tm [OPTION...] MACHINE_FILE

-f, --fast: Be as fast as possible: deactivate any delays, do not print tape state after each step, print step number rarely. Specify this option twice to disable printing step/tape information after machine halts

--frame: Draw frame around tape

-s, --speed[=SPEED]: Set speed of simulation (0 - slowest, 10 - no delays, default 7)

--tape[=TAPE_FILE]: Use tape from the specified file; the tape from the machine file is ignored, if is

--tui: Use ncurses-based interface

-?, --help: Give this help list

--usage: Give a short usage message

Examples

See examples/ directory.

Machine file format:

[:] q0
[.] f1 f2 [...]
P a -> Q b DIR
...
=-=-=
TAPE_ENTRY
...

q0, f1, ..., P, Q are state names. State names may be multi-character.

a, b are symbol names. Symbol names may be multi-character.

Reserved names for states/symbols are null, (null), *, _.

DIR is one of the following characters: l, <, r, >.

All transitions are undefined by default.

Entries may overwrite previous ones.

Machine in undefined state halts with error code 1.

You may define a transition from undefined (null) symbol.

You may not define transition from undefined state.

You may use wildcards for a pair of states/symbols in a transition:

<*> -> <s> means transitions from all instances of that class to instance s.

<_> -> <_> means transitions independent of that class.

<s> -> <_> means transition that does not change class instance s.

Examples:

* a -> H b > (in any state, if symbol a is encountered, write b and move right into state H)

P _ -> Q _ l (in state P, move left into state Q without overwriting the current symbol)

P a -> _ b < (in state P, if symbol a is encountered, write b and move left into the same state)

=-=-= line indicates start of tape description.

You may omit tape description to get an empty tape.

TAPE_ENTRY format is one of the following:

pos: a b c ...

pos~end: a b c ...

pos~inf: a b c ...

inf~pos: a b c ...

a, b, c, ... are symbol names.

1. Insert symbols from pos and forth (until all symbols are inserted)

2. Insert pattern symbols from pos to end, including end

3. Insert pattern symbols from pos to right infinity

4. Insert pattern symbols from left infinity to end, including end. The last pattern symbol will be at the end position

Tape entries overwrite previous ones if intersections occur.