

                      Alana - A Turing Machine Simulator
                      ==================================


        1) Requirements
        ---------------

Alana requires Tcl/Tk version 8.3 or later, available from http://www.tcl.tk.


        2) What Is a Turing Machine?
        ----------------------------

A Turing machine (or TM for short) is an abstract machine named after its
designer, Alan Turing. It consists of a set of states, a read-write head (also
called tape head), a tape, a tape alphabet (symbols the tape head can read from
and write to the tape), a single starting state, a set of halting states (also
called final or accepting states, a - possibly empty - subset of the states
mentioned before) and a transition function (also called delta-function).

The tape has infinite length both to the right and to the left. It is
structured logically into "cells". Every cell contains exactly one symbol of
the tape alphabet at a given time. There is a special symbol in every tape
alphabet, called the blank symbol (often depicted as an empty box) with which
the tape (every cell of the tape, to be exact) is initially filled. The tape
head can only move discretely between cells (this means that it can never be in
the midst of two cells).

At any time, you know two things about a TM:

        *) the current tape content (= content of every cell of the tape), and
           in particular, the content of the cell beneath the tape head
        *) the current state of the machine

This is called the configuration, or instantaneous description, of the TM.

Initially, a TM is in the starting state (specified in the input). As mentioned
before, the tape contains only blank symbols. Well, not quite: You can also
specify some symbols (a finite number) that should be on the tape right from
the start. In this case, the tape head will be placed above the first non-blank
symbol on the tape. Otherwise, it is placed above any blank symbol on the tape.

Now that everything is initialized, the fun part begins. Given the current
state and the symbol beneath the tape head, we can compute the next step of our
computation via the transition (or delta) function! The transition function is
a mapping from the current configuration to a triple <s, c, d>, where s is a
state, c is a symbol (or character) of the tape alphabet, and d is either "r"
or "l". This tells the machine what to do next (in this order):

        1) switch to state s
        2) write the symbol c at the current position of the tape head
        3) move the tape head one cell to the right / left

The machine halts when there is no transition defined for the current
configuration. The input is said to be accepted by the machine if the machine
halts in a final state, not accepted otherwise. After the input is accepted by
the TM, the final tape content is called the result of the computation. A
problem is called Turing-computable or simply computable if there exists a TM
that accepts the problem specification as its input and halts with the result
written on the tape. Although you would not guess it at first sight, every
computation that a contemporary computer (program) can execute, can as well be
translated to a TM. The device is thus more powerful than it looks.
 
Notice that every TM is computable itself, because you can specify a transition
function for some other TM that expects the specification of the initial TM and
its input as its input (this is no mistake!) in some reasonable encoding and
then interprets the encoded form of the initial TM to execute exactly the
operations that the first TM would have executed on the original input.

Such a TM that simulates other TMs is called a universal Turing machine or UTM.
Alana itself is an example of a UTM, because you can give it a specification of
a TM (using a somewhat reasonable encoding described below) and it will
simulate the execution of this given TM. Yet, you could translate the operation
of Alana to a TM, because the language that Alana is written in (Tcl/Tk) is no
more powerful (in terms of computation ability) a concept than Turing machines
are. Translating Alana to a TM is cumbersome, but achievable.  Have a look at
P. J. Denning, J. B. Dennis, and J. E. Qualitz, "Machines, Languages, and
Computation", where an example of a UTM is presented.


        3) What Else Is a Turing Machine?
        ---------------------------------

There exist many other essentially equivalent definitions of Turing machines.
They differ only in specification details, not in expressiveness or computation
power. For example, some of them let you not only shift the tape head to the
right or left, but also let it stay in place. This can of course be achieved in
our model by introducing an additional state that shifts the tape head back to
where it came from. Some machines use multiple tapes. This can be achieved in
our model by using more than one letter per cell and interpret the n-th letter
as the content of the n-th tape. For example, "gxa" could be interpreted as "g"
on tape 1, "x" on tape 2, "a" on tape 3. Also, without loss of generality, we
may assume that the tape extends infinitely only to the right (or left),
because we can interpret (for example) every odd-numbered cell as extending to
the left and every even-numbered cell as extending to the right.

If you want to delve deeper into the subject, you may consider the following
books and the references found therein good starting points:

    Martin Davis: "The Universal Computer: The Road from Leibniz to Turing",
        W. W. Norton & Company (October 2000)

    Martin D. Davis, Ron Sigal, Elaine J. Weyuker: "Computability, Complexity,
        and Languages", Academic Press, 2nd edition (April 1994)

    John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: "Introduction
        to Automata Theory, Languages, and Computation", Addison-Wesley
        Publishing, 2nd edition (November 2000)

    Elliott Mendelson: "Introduction to Mathematical Logic", Chapman & Hall,
        3rd edition (January 1987)


        4) Using Alana
        --------------

When you fire up Alana, you see the main window. It shows you a few cells of
the tape and an entry field for the transition function. Notice that the tape
contains only blank symbols, denoted by "_" (underscore). Try changing the tape
content by clicking on any cell and pressing a letter or number on your
keyboard. Move the tape head (the cell in the midst) to the right and left by
clicking the buttons labeled "<<" and ">>" or by pressing the cursor keys.
Double-click (or Ctrl + Click) on a cell to enter a string instead of a single
symbol. Clear all non-blank cells again by clicking on them and pressing space.

Now let's define a transition. We want to specify: If you are in state 53
and the symbol beneath the tape head is "b", switch to state 3, write "a" to
the tape (overwriting the "b") and move the tape head to the left. This is
specified by entering (with parentheses!):

        (53 b 3 a L)

If we did not want to write "a" to the tape, but leave the "b" intact and just
switch states and move the tape head, we could write

        (53 b 3 L)

as an abbreviation for (53 b 3 b L). If we had just wanted to move the tape
head, but stay in state 53 and leave the "b" intact, we would have written

        (53 b L)

as a shorter version of (53 b 53 b L) or (53 b 53 L). You can of course also
use the longer versions if you want.

To shift the tape head to the right, write "R" instead of "L". These
directions are not case sensitive - you can also write "r" and "l". State
identifiers and tape symbols are case sensitive, though.

Notice that as you enter this transition, the status message underneath the
entry field displays syntax errors (missing closing parenthesis and such).
Don't worry about it - look at it only after you finished typing the whole
transition (and every opening parenthesis, bracket and curly brace is closed)
to check if your specification is syntactically valid. "Entity" in error
messages means either a transition, a set of halting states, the starting state
or an initial character/symbol of the tape.

OK, the transition entry field now reads (53 b 3 a L). The message says that
this input is valid, and Alana can deduce from the input that the Turing
machine we are about to define has at least 2 states: 3 and 53. You can choose
the current state of the machine at any time using the drop-down box labeled
"Current state". Choose state 53.

In the bottom right corner of the main window, Alana displays what it would do
next if you clicked "Step". Currently, it does not know what to do, because no
transition matches the current configuration of the machine. Therefore, enter a
"b" in any cell of the tape and place the tape head above this "b" by clicking
the buttons labeled "<<" and ">>" or by pressing the cursor keys.

Immediately, Alana displays "3 a L" in the bottom right corner, meaning that if
you click "Step", it will switch to state 3, write an "a" and move the tape
head to the left. Click "Step" now to execute this transition.

Now, enter a new transition saying that if we are in state 3 (what we are) and
see the blank symbol beneath the tape head (which we see), switch to state 87
and move the tape head to the right:

        (3 _ 87 r)

Click step again to execute this transition. The next step is undefined,
because no transition matches the current configuration. If we want to accept
this input, we must add state 87 to the set of halting states. This is
accomplished by entering

        {87}

in the entry field. If we also want to add state 3, we would write

        {87 3}   or   {3 87}

(separated by whitespace). Click step again - done! The machine has accepted
the input, because no transition matches the current configuration, but we are
in a halting state, so we are done. If you enter two or more conflicting
transitions, sets of halting states or starting states, the last one will
overrule every preceding one. To undo the most recent transitions (up to 64),
click "File -> Undo".


Great - this was our first program. Very useful, wasn't it? Now, let's try an
infinite loop. First, let Alana display the whole tape content in a single text
box by clicking "File -> Tape content". The text box contains all non-blank
symbols in the tape. Clear this box and click "OK" to reset all cells to
contain only blank symbols.

Clear the transition entry field, and enter the transitions:

        (aaa _ bbb r)
        (bbb _ aaa l)

This time, I chose letters instead of numbers as state identifiers. This is
surely possible, because the meaning can always be deduced from the position of
the string in the transition. We now have two states: aaa and bbb. When the
machine is in state aaa and sees a blank symbol, it switches to bbb and moves
the tape head to the right. After that, it switches back to aaa (because there
is a blank symbol) and moves the tape head to the left.

Select "aaa" as the current state and click "Run". Play with the execution
speed and watch the machine going completely crazy. You think the tape head
does not move? It does! Place a letter in the second visible cell or so and see
it go left and right like a tiger trapped in a cage. Stop the machine by
clicking "Stop". It is of course easy to see that this machine would never
halt, even if we ran it for years and decades.

However, the problem to decide whether a given TM will eventually halt, known
as the "halting problem" or "Entscheidungsproblem" (decision problem), is
generally not solved easily. It is in fact undecidable (this was proved by
Turing; the proof is included in the file "halting.txt" of this package).


For maximal execution speed, you should run Alana in console mode. In this
mode, the graphical interface is not displayed and therefore need not be
updated. To start Alana in console mode, run

        alana.tcl <file> -nogui

where <file> is the file which contains the instructions you want to execute
(see the next chapter for saving and loading files). The <file> argument is
mandatory, as you have no other means of communicating with Alana, and it must
always be the first argument (others may be given in any order). Immediately
after the file is loaded, Alana runs the resulting Turing machine. It displays
the number of executed steps (= transitions), the final non-blank part of the
tape content (result) and the final position of the tape head after the machine
halts, relative to the displayed content. You can use the form

        alana.tcl <file> -nogui -verbose <num>

to display the current number of executed transitions every <num> steps (if
<num> is not specified, it defaults to 5000). This is if you mistrust the
author and want to be sure that the program is still running (Alana itself
could contain a mistake and misinterpret instructions or take a nap every once
in a while - which it does, by the way, muahahaha).

To ignore the initial tape content specified in the file and set some different
initial content, use

        alana.tcl <file> -nogui -tape <tape content>

Where <tape content> is a string of tape symbols separated by whitespace. You
may need to quote <tape content> to make your shell treat it as a single
argument. A typical invocation would be

        alana.tcl examples/divisibility.al -nogui -tape '1 1 / 1' -verbose 10


        5) Saving and Loading Files
        ---------------------------

You can save your program by clicking "File -> Save" and load it at a later
time via "File -> Open...". When a file is loaded, a string in brackets is read
as the initial starting state (for example, [5]). This is useful if you run
Alana without the graphical interface. Additionally, any symbol not contained
in parentheses, brackets or curly braces (for transitions, starting state and
halting states) is interpreted as a tape symbol - it is written directly onto
the tape.

After the file is completely loaded, the tape head is positioned above the
first non-blank cell of the tape (or above any blank cell if you did not
specify any initial tape content).

If a line contains the symbol "#", everything from that symbol to the end of
the line is ignored. You can thus embed comments in your files.

You can simulate (or repeat, respectively) the effects of loading a file
(resetting the tape, setting the starting state as the current state) at any
time by clicking "File -> Reparse". If you invoke Alana using the form

        alana.tcl <file>

then <file> is automatically loaded and displayed (provided it exists and is
readable).


        6) Shortcuts
        ------------

The following shortcuts to the "File" menu entries are available when the
cursor is in the delta entry field:

        CTRL + e: Step
        CTRL + n: New
        CTRL + r: Reparse
        CTRL + s: Save File
        CTRL + t: Tape content
        CTRL + u: Undo
        ALT  + x: Exit


        7) Busy Beavers
        ---------------

Related to the halting problem (see above) is the quest for "Busy Beavers". The
problem specification is this:

Given a fixed number n of states, a blank tape, and a finite tape alphabet S,
construct a transition function so that the resulting Turing machine writes the
maximum number of "1"s onto the tape and then halts.

You can freely choose the starting state and the halting states. The alphabet S
is sometimes implicitly assumed to be {blank, 1} or {blank, 0, 1}.

The crux of the problem lies in the last requirement, namely that the machine
has to halt! It is of course possible to examine every possible Turing machine
with n states that could be constructed via arbitrary transition functions over
the alphabet S (because it is finite), but the number of possible machines
grows rapidly with the number n of states, and for every candidate machine, it
cannot be seen beforehand whether it will halt eventually or simply loop
forever.

I have included a transition function for a 5-state Turing machine in the
examples directory (busy5.al) that halts with 501 "1"s on the tape after
134,467 steps. It is already known that this TM is not the optimal solution, so
it is strictly speaking no Busy Beaver (because an n-state Busy Beaver has to
write the *maximum* number of "1"s onto the tape that can be achieved with n
states). However, due to the undecidability of the halting problem, the Busy
Beaver function B(n), returning the number of "1"s written on the tape by an
n-state Busy Beaver, is non-computable. So we sometimes incorrectly use the
description "an n-state Busy Beaver" when what we really mean is "a (former)
candidate for an n-state Busy Beaver".


        8) The Examples
        ---------------

A glance at the included examples should quickly lead to a much thorougher
understanding of TMs. I recommend that you browse through the examples in order
of increasing complexity (no one is supposed to understand the Busy Beaver):

  a) unaryadd.al       - a very simple example performing addition in unary
                         encoding: 1 is 1, 2 is 11, 3 is 111, 4 is 1111, ...
  b) anbncn.al         - accepting strings of the form (a^n)(b^n)(c^n), n >= 0
  c) a2n.al            - accepting strings of the form a^(2^n), n >= 0
  d) subtract.al       - subtraction of two numbers in unary encoding
  e) copyinput.al      - copy a given string of "0"s and "1"s to the tape
  f) binaryadd.al      - addition of two numbers in binary encoding
  g) multiplication.al - multiplication of two numbers in unary encoding
  h) divisibility.al   - divisibility testing of two numbers in unary encoding
  i) primality.al      - test if a given number (in unary encoding) is prime


        9) Latest Version and Contact
        -----------------------------

The latest version of Alana will be available from

        http://triskam.virtualave.net/alana/alana.html

and from

        http://www.freshmeat.net

I can be reached via

        triska@gmx.at
        ICQ: 41792116

Good luck,
Markus Triska.
August 8th, 2003
