1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
# 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. 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:
[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'.
## 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
|
