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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
# 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,Σ,Γ,δ,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
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
|
