CleanTuringMachines

Turing machines implementation in 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,Σ,Γ,δ,q₀) where Q is the set of states and q₀ the initial state (Sudkamp, Languages and Machines, 1997). Here, we take the integers as Q and 0 as q₀. a relates to Γ, i relates to Σ and we will get back to δ.

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 (δ) 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:

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