# CleanTuringMachines

Turing machines implementation in [Clean](http://wiki.clean.cs.ru.nl/Clean). Features include:

 * Straightforward types for turing machines and their states
 * Running and stepping a turing machine in execution
 * Simple `toString` instances for easy display of the types
 * A `turinglog` program as an example and to be used to get a trace of the execution of a machine

Read further for examples.

### License

This program and the example are distributed under the MIT license. For more details, see the LICENSE file.

## Types and classes

### IterableClass

Provides two general classes:

    class step a :: !a -> a
    class rewind a :: !a -> a

Both are meant to be instantiated by types that can be 'stepped'. For example, the TuringMachineState instantiates the `step` class to be able to compute the next state for a current state. The `rewind` class is currently unused, but it only made sense to include it and make this a separate module. It allows a type to step backwards. Note, that for a Turing machine it is impossible to instantiate this class, because the transition function need not have an inverse.

There are three derivative functions:

    stepn :: Int !a -> a | step a
    rewindn :: Int !a -> a | rewind a
    stepOrRewindn :: Int !a -> a | step, rewind a

The first and second simply iterate `step` and `rewind`. Negative values for the first argument will never terminate. The latter function will evaluate to either `rewindn` or `stepn`, depending on the sign of the first argument.

### TuringMachines

The tape is a simple list of Maybes of an arbitrary type. `Nothing` encodes a blank, `Just a` encodes the value `a`.

    :: Tape a :== [Maybe a]

The transition function (shown subsequently) results in a `TuringMachineMove`. This can either be a `Step`, or a `Halt`. Normally, the transition function is a partial function. Here, it is expected to be a nonpartial function to avoid runtime errors. What would normally be undefined is now `Halt`: it tells the turing machine to terminate.

    :: TuringMachineMove a = Step Int (Maybe a) Direction | Halt
    :: Direction = Left | Right

Here, `a` is the alphabet once again. A step changes state to the first argument, writes the second argument on the tape, and moves in the specified direction.

A Turing machine state consists of a Turing machine definition, but also includes the current state, the position of the tape head, the tape itself, and whether the machine is running or not:

    :: TuringMachineState a = { machine :: TuringMachine a,
                                state :: Int,
                                tapeHead :: Int,
                                tape :: Tape a,
                                running :: TuringMachineTermination }
    :: TuringMachineTermination = Running | Normal | Abnormal

Here, `a` is the tape alphabet. We will come back to that.

As you can see, we specify states simply with integers. Mathematically, a Turing machine is a quintuple (Q,&Sigma;,&Gamma;,&delta;,q<sub>0</sub>) where Q is the set of states and q<sub>0</sub> the initial state (Sudkamp, Languages and Machines, 1997). Here, we take the integers as Q and 0 as q<sub>0</sub>. `a` relates to &Gamma;, `i` relates to &Sigma; and we will get back to &delta;.

The machine may be `Running`, or it may be terminated. In the latter case we distinguish between `Normal` termination (after a `Halt` move) and `Abnormal` termination (if the tape head position goes negative).

Finaly, the definition of the Turing machine itself:

    :: TuringMachine a = { alphabet :: [a],
                           inputs :: [a],
                           transition :: Int (Maybe a) -> TuringMachineMove a }

Again, we see the alphabet `a`. The transition function (&delta;) is a function from `Int` (the current state) and `Maybe a` (the character read by the tape head to a `TuringMachineMove a`. The `inputs` key specifies the input alphabet, typically a subset of the alphabet itself. It defines the characters allowed in the input.

### Examples

The following is a simple machine to replace `a` with `b` and vice versa. It is an example from Sudkamp, Languages and Machines, 1997, where it is represented as a state machine:

![A graphical representation of the replace machine](http://i.stack.imgur.com/gOtXY.png)

    replace :: TuringMachine Char
    replace = { alphabet = ['a','b'],
                inputs = ['a','b'],
                transition = f }
    where
        f :: Int (Maybe Char) -> TuringMachineMove Char
        f 0 Nothing     = Step 1 Nothing Right
        f 1 Nothing     = Step 2 Nothing Left
        f 1 (Just 'a')  = Step 1 (Just 'b') Right
        f 1 (Just 'b')  = Step 1 (Just 'a') Right
        f 2 (Just 'a')  = Step 2 (Just 'a') Left
        f 2 (Just 'b')  = Step 2 (Just 'b') Left
        f _ _           = Halt

Note the final catch-all alternative of the transition function `f`, which is used to make sure `f` is nonpartial.

## Firing up the machine

Getting a `TuringMachineState` from a `TuringMachine` is fairly straightforward. All you need is a `Tape`. For the example above, we may write:

    state :: TuringMachineState Char Char
    state = initTuringMachine replace tape
    where
        tape = [Just c \\ c <- fromString "aabbaa"]

The set builder for the tape is just ease of notation, we may as well have written `['a','a','b','b','a','b']`. A first and final blank is added to the tape by `initTuringMachine`.

`initTuringMachine` checks that there are no characters on the tape that are not in the input alphabet, and aborts if there are.

## Stepping and running

From this state we can either `step`...

    state1 = step state
    state5 = stepn 5 state

... or run until termination:

    statef = run state

## Showing results

The `TuringMachineState` instantiates `toString`. The result of `toString statef` would be:

    [q2]BbbaabbB (Normally terminated)

As you can see, the machine definition is in no way represented by this function.

Blanks (`Nothing` on the tape) are represented with 'B'.

## Using `turinglog`

`turinglog` is a simple implementation of the library and can be used to get a trace of the execution of a machine.

Compile with:

    clm -I /opt/clean/lib/StdLib turinglog -o turinglog

Replace `/opt/clean/lib/StdLib` with the appropriate path. 

Run with:

    ./turinglog

Example output:

    [q0]BabbabaB (Running)
    B[q1]abbabaB (Running)
    Bb[q1]bbabaB (Running)
    Bba[q1]babaB (Running)
    Bbaa[q1]abaB (Running)
    Bbaab[q1]baB (Running)
    Bbaaba[q1]aB (Running)
    Bbaabab[q1]B (Running)
    Bbaaba[q2]bB (Running)
    Bbaab[q2]abB (Running)
    Bbaa[q2]babB (Running)
    Bba[q2]ababB (Running)
    Bb[q2]aababB (Running)
    B[q2]baababB (Running)
    [q2]BbaababB (Running)
    [q2]BbaababB (Normally terminated)

As you can see, for each iteration the state is outputted.

This example is using the `replace` machine of above and using the input `abbaba`. This is also the values in `turinglog` at the moment. Replace the machine and the tape as needed.

## Future ideas

 * It would be really cool to have some kind of graphical frontend and a possibility to step through the machine with some input