diff options
Diffstat (limited to 'Readme.md')
| -rw-r--r-- | Readme.md | 50 |
1 files changed, 44 insertions, 6 deletions
@@ -5,6 +5,7 @@ Turing machines implementation in [Clean](http://wiki.clean.cs.ru.nl/Clean). Fea * 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. @@ -18,16 +19,16 @@ This program and the example are distributed under the MIT license. For more det Provides two general classes: - class step a :: a -> a - class rewind a :: a -> a + 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 + 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. @@ -73,7 +74,7 @@ The following is a simple machine to replace `a` with `b` and vice versa. It is  - replace :: TuringMachine Char Char + replace :: TuringMachine Char replace = { alphabet = ['a','b'], inputs = ['a','b'], transition = f } @@ -123,6 +124,43 @@ 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 |