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
|
module exercises
import StdEnv
import TuringMachines
Start :: *World -> *World
Start w
# (io,w) = stdio w
# m = initTuringMachine ex_9_4 tape_9_4
# io = fwrites (toString m +++ "\n") io
# io = loop m io
# (ok,w) = fclose io w
| not ok = abort "Couldn't close stdio\n"
| otherwise = w
where
loop m f
# m = step m
# f = fwrites (toString m +++ "\n") f
| m.running == Running = loop m f
| otherwise = f
tape_9_3_b = [Just c \\ c <- fromString "abbaba"]
ex_9_3_b :: TuringMachine Char
ex_9_3_b = { alphabet = ['a', 'b', 'X', 'Y'],
inputs = ['a', 'b'],
transition = f }
where
f :: Int (Maybe Char) -> TuringMachineMove Char
f 0 Nothing = Step 1 Nothing Right
f 1 (Just 'a') = Step 1 (Just 'a') Right
f 1 (Just 'b') = Step 1 (Just 'b') Right
f 1 c = Step 2 c Left
f 2 Nothing = Step 6 Nothing Right
f 2 (Just 'a') = Step 3 (Just 'X') Right
f 2 (Just 'b') = Step 4 (Just 'Y') Right
f 3 (Just c) = Step 3 (Just c) Right
f 3 Nothing = Step 5 (Just 'a') Left
f 4 (Just c) = Step 4 (Just c) Right
f 4 Nothing = Step 5 (Just 'b') Left
f 5 (Just c) = Step 5 (Just c) Left
f 5 Nothing = Step 1 Nothing Right
f 6 (Just 'X') = Step 6 (Just 'a') Right
f 6 (Just 'Y') = Step 6 (Just 'b') Right
f 6 (Just c) = Step 6 (Just c) Left
f _ _ = Halt
tape_9_3_c = [Just c \\ c <- fromString "abbaa"]
ex_9_3_c :: TuringMachine Char
ex_9_3_c = { alphabet = ['a', 'b', 'X'],
inputs = ['a', 'b'],
transition = f }
where
f :: Int (Maybe Char) -> TuringMachineMove Char
f 0 Nothing = Step 1 Nothing Right
f 1 (Just 'a') = Step 1 (Just 'a') Right
f 1 (Just 'b') = Step 1 (Just 'b') Right
f 1 (Just 'X') = Step 2 (Just 'X') Left
f 1 Nothing = Step 2 (Just 'X') Left
f 2 (Just 'a') = Step 3 (Just 'X') Right
f 2 (Just 'b') = Step 4 (Just 'X') Right
f 2 Nothing = Step 5 Nothing Left
f 3 (Just 'X') = Step 2 (Just 'a') Right
f 3 Nothing = Step 2 (Just 'a') Right
f 4 (Just 'X') = Step 2 (Just 'b') Right
f 4 Nothing = Step 2 (Just 'b') Right
f 5 (Just 'a') = Step 6 (Just 'a') Left
f 5 (Just 'b') = Step 6 (Just 'b') Left
f 6 (Just 'X') = Step 5 (Just 'X') Left
f 6 (Just 'a') = Step 2 (Just 'a') Right
f 6 (Just 'b') = Step 2 (Just 'b') Right
f 6 Nothing = Step 7 Nothing Right
f 7 (Just c) = Step 7 (Just c) Right
f 7 Nothing = Step 8 Nothing Left
f 8 (Just 'X') = Step 8 Nothing Left
f 8 (Just c) = Step 8 (Just c) Left
f _ _ = Halt
tape_9_4 = [Just c \\ c <- fromString "babaabbaaacabababb"]
ex_9_4 :: TuringMachine Char
ex_9_4 = { alphabet = ['a', 'b', 'c'],
inputs = ['a', 'b', 'c'],
transition = f }
where
f :: Int (Maybe Char) -> TuringMachineMove Char
f 0 Nothing = Step 1 Nothing Right
f 1 (Just 'a') = Step 2 (Just 'a') Right
f 1 c = Step 1 c Right
f 2 (Just 'a') = Step 3 (Just 'a') Right
f 2 c = Step 1 c Right
f 3 (Just 'a') = Step 4 (Just 'a') Right
f 3 c = Step 1 c Right
f 4 (Just 'a') = Step 4 (Just 'a') Right
f 4 (Just 'c') = Step 5 (Just 'c') Left
f 4 c = Step 1 c Right
f 5 (Just c) = Step 5 (Just c) Left
f _ _ = Halt
|
