Tutorial
FAQ
Manual
Downloads
Contact
This is an introduction to Tursi. You will learn how to write tm-files, load and execute them using the GUI or console mode.
If you want to use Tursi as soon as possible, I recommend to skip this tutorial and download the tm-file examples instead. Most things should be self-explanatory. If you don't get everything, you can always search this tutorial or the manual for an explanation.
This is not a tutorial for turing machines (abbreviated tm). If you don't know, what a turing machine is or how it works, you have to inform you elsewhere.
However there are many different definitions of turing machines, so it has to be described, which one we use:
Our turing machine has
A special alphabet is not required. We just use all available symbols.
The transition function takes the current state and the symbol under the
head as input. It returns a further symbol, a direction and a state.
Therefore, our table has 5 columns. We call its lines rules.
As mentioned above, it must be deterministic. So that there's at most one
output for each input. On the other side, you don't have do define an
output for every input.
Our machine starts with the initial state and calls the transition
function (basically, it searches the table). The output symbol will be
written over the current position. Then, the head will move in the
indicated direction (it can also stay, where it was). Finally the
current state will be changed.
This steps are repeated, until no rule for the current state and symbol
under the head was found or an end state was reached.
When the machine has stopped, you can read what it wrote on the tape and in which state it ended. Tursi just executes the machine and does not validate the result - you have to decide, if your machine did the right thing.
Normally the cells on the tape aren't numbered, but we will number them,
because it's easier to talk about cell n instead of the cell,
which lies n cells to right of the initial head position.
0 is the cell where the head was, as we started the turing machine. We count upwards, when moving right and backwards when moving left.
Tursi is not designed, to create and edit turing machines. So you will need a simple text editor (not word!) to write a tm-file, which describes a turing machine and can be loaded into Tursi.
If you use GEdit, you may want to install tm.lang (see Downloads) to enable syntax highlighting.
a tm-file is basically the transition table, but it can also contain comments and commands. Here's an example:
# this is a comment
# the following 3 lines are commands
#! start s
#! end e0 e1
#! fill *
# Now we specify some rules
s 0 0 R s
s 1 0 R q
s * * N e0
q 0 0 R q
q 1 0 R q
q * * N e1
This is a turing machine, with 4 states - 2 of them (e0 and e1) are end states. It starts in state s on a tape, filled with *. When you open this tm in Tursi, write a binary number onto the tape and execute the machine. It replaces every 1 with a 0 and stops when reaching the end of the word. If it stopped in e0, the word contained no 1.
The tm format is case-sensitive! So q is another state than Q.
A comment starts with # and ends at the
end of the line. If you want to use the symbol # in your machine, you have
to escape it - just write ##.
So ###... would be a #, followed by a comment.
#### would be ## and so on.
This may be a little confusing, but it's easy to type and we don't need
a special escape character, which then also had to be escaped.
A command starts with #! and ends at the next command, comment or
line end.
Even though it begins with #, it's not a comment! This is not very
beautiful, but guarantees compatibility to the old format, which did not
know commands.
The first word after this sequence is interpreted as the command name,
all further words will be passed to this command as arguments (you probably
expected that, if you ever used a shell like bash).
Commands are not mandatory, but Tursi will complain, when it has to
guess vital informations like the start state, end states or default
tape content.
The most important commands are
If you always use these three commands, you're on the safe side.
Here, we used * as fill, because the real space
is used for separating the components of a tm-file. Therefore, it cannot
be interpreted differently.
If you really want to use a space, you could use a non-breaking space.
However, it's not recommended, since you wouldn't be able to keep it apart
from a normal space or even an empty part of your file.
Normally, most of your lines are rules. Remember: A rule is a line of your transition table, which has 5 columns (2 input, 3 output). The columns are separated by whitespace (e.g. tab or space) and have to be in the following order:
Keep in mind, that the turing machine has to be deterministic. This means, all rules must be distinguishable by their first two columns (the input of the transition function).
When you have a tm-file, you can execute it. To do so, we use Tursi's GUI.
Open Tursi, then open your tm-file. If your tm-file is flawless, you will see your transition table on the left.
Before you execute your turing machine, you likely want to write something
onto the tape. To do so, use the top text field on the the right.
Write something and then press enter. You can modify the position, where
your text is written to, by changing the number underneath.
To reset the tape, click the top right button with the tape roll on it.
Now let your machine take its first step. To manually step forwards,
click the right footprint button. You can also use the
right arrow key (click onto the tape, to make sure, that no text field has
the keyboard focus).
After each step, the executed rule pops up in history. You can undo steps
from the history. Click on the left footprint button or use the left
arrow key.
Instead of clicking a button for every step, you can run your machine.
Click on the play button (green triangle arrow) or use the space bar.
Stop it with the same button or key.
Speed it up or down, using the slider on the right. This changes the
pause time between every step.
Some window managers show a number on the slider. This is not the pause time! That's because the slider has a quadratic scale (smaller values can be set with more precision). The real pause time is displayed in a tooltip (move your mouse over the slider and stand still).
Reseting is split into two functions: Reseting the machine to the start state (left button with the purple triangle arrow) and reseting the tape (top right button with the tape roll).
Say, you have a program, that increments a number and stops, where it
has started. You can reset the state, but keep the tape for each run to
increment your number multiple times.
In this scenario, you wouldn't even have to reset at all. Tursi
automatically resets the state, when the machine is in an end state
and is executed again (see File/Preferences/"Reset when starting from
end state").
If you want to reset both, the state and the tape, you can also reload your file (use File/Reload or press ctrl+R).
When working with turing machines, that read or write long words, your
tape will not fit into the window. In such cases Tursi can follow the
head as it moves. You can also scroll manually with your cursor.
Hold and drag the tape or make use of your mouse wheel.
You can change between manual and two different automatic scroll modes.
Just press one of the three buttons on the top right.
There are four special cells, which are marked in the tape viewer. The cell under the head, the leftmost and rightmost cell ever accessed and the cell, where the head has started (0). To jump to one of them, click onto the according labels down right.
Some turing machines can make thousands of steps before they stop.
Even with full speed (0 ms pause time), you might have to wait
long for them to finish.
Like the graphic settings of a video game, Tursi offers options that
reduce or disable graphical features, but relief your system. Most of
them are in the category View of the menu bar. The more you disable,
the faster your machine will run.
When you don't want to disable the tape viewer, you can make your window
narrow, so that less tape is drawn. You can also increase the frame length.
This is the delay for repainting, after the tape was changed. The higher,
the more changes can be packed into one repaint, but your tape will begin
to stutter. You can set the frame length under File/Preferences.
The highest frame length is limited to 1000 ms.
For very long running turing machines, you're better off using the console mode.
Another (and faster) way to execute your tm-file is Turi's console mode. This mode is not interactive - Tursi just runs your machine once and terminates.
Since you won't be able to modify the tape in console mode, you have to use the write command in your tm-file. It writes something onto the tape, before the machine is executed. The machine is not affected by this command (especially the head does not move).
You can use write multiple times or even write multiple times
with only one call of write. The commands will be executed in the
order they were called.
The command comes in two forms:
Keep in mind, that a word can't contain whitespace (space or tab), because
this would split it into two arguments. One of them would be interpreted
as a position.
You also can't simply write #, because this would be a comment.
Write ## instead, to eascape it.
Let's have a look at an example:
# some examples for the write command
#! write abcdefgh
#! write 0 Z 4 ABCD # now the tape will contain 'ZbcdABCD'
#! write ## # and now '#bcdABCD'
To start Tursi in console mode, you have to use the console (what a
suprise).
Note the -c which activates console mode. Remove it to open your
file in the GUI.
java -jar /path/to/tursi.jar /path/to/your/file.tm -c
Windows users may have to add Java to their PATH variable first.
Mac users who have downloaded the app, don't have to download the jar. The app is practically a directory, which includes the jar. You can write Tursi.app/Contents/Resources/Java/Tursi.jar
After your machine was executed, your output may look like this:
(let \t be a tabulator)
57\tq
\ttape (-3, 11, 7), head 4
\txyz
\tabcdefgh
This means, after 57 steps, your machine reached state q.
At this time, the leftmost cell ever accessed was -3 and the
rightmost cell ever accessed was 7. Cells that were never reached,
will not be printed. So the printed tape contains 11 cells.
The head is currently on cell 4 (reads e, because
a is in cell 0).
The last two lines are the tape. The first is the part left from cell 0.
The second is the part from cell on to the right (including cell 0).
The tape would look like "xyzabcdefgh" if you used the GUI. But if
it was written in one line, you had to count characters and calculate, just
to find cell 0. That would be annoying.
You can modify when and what Tursi should print. Just append a further argument to the command line, when starting Tursi.
java -jar tursi.jar file.tm -c <groups>=<options> [...]
The defaults are 'e=st bo='.
If you set options multiple times for one group, only the last one counts.
When a state is in multiple groups (e.g. it is a break and an end state),
the options from the strongest group will be chosen (end >
break > other). Only the nth-step groups mix with
other groups (options are combined with a logical OR).
Lets make an example:
ebo=str e=st bo= 5000=s 10000=t
the first part is wasted - all groups are overwritten by other specifications. This makes the example equal to
e=st b= o= 5000=s 100000=t
With this options, Tursi will print the number of steps and the tape when it reached an end state. Every 5000 steps, the current state and number of steps are printed and every 100000 steps the tape is printed (in addition to the steps and the state, because 100000 is a multiple of 5000).
There are two more commands, which weren't discussed.
You can define break states. This can be used to stop your run in the GUI when reaching a certain state or to apply print options to only a subset of your states in the console mode.
To do so, use the command break. It works just like the end command.
wildcard <symbol> defines <symbol> as a wildcard.
Only one single symbol can be defined as a wildcard.
Wildcards can help you writing tm-files faster when you have a lot of similar rules.
# same output for all inputs
q0 a x R q1
q0 b x R q1
q0 c x R q1
...
This could be written as
#! wildcard ?
q0 ? x R q1
The symbol ? is now a wildcard and applies to all symbols. When in state q0, the rule will be executed no matter what symbol was read.
You can also use the wildcard in the write column, where it is interpreted as the symbol, that was read.
#! wildcard ?
q0 a ? R q1 # ? would be an a
q1 ? ? R q2 # this rule moves to right, without changing the tape
Rules with wildcards will only be executed, if no other rule matches the current state and symbol under the head. You can see it as a fallback.
#! wildcard ?
q0 1 0 R q0
q0 0 1 R q0
q0 ? ? R qErr # error when something other than 0 or 1 was read
Wildcards can only be used in the read and write column of rules. write ? will write a ? and "? r w N ?" will be a rule for state ?, no matter if ? is defined as wildcard or not.