diff options
Diffstat (limited to 'Readme.md')
| -rw-r--r-- | Readme.md | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/Readme.md b/Readme.md new file mode 100644 index 0000000..0eca67d --- /dev/null +++ b/Readme.md @@ -0,0 +1,130 @@ +# 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 + +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 and `i` is the input 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<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 Γ, `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 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: + + Normally terminated turing machine in state 2, tape head at 0. + Tape: BbbaabbB + +As you can see, the machine definition is in no way represented by this function. + +Blanks (`Nothing` on the tape) are represented with 'B'. + +## 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 + |