|
1 abstract class Cell |
|
2 case object Bk extends Cell { override def toString = "0" } |
|
3 case object Oc extends Cell { override def toString = "1" } |
|
4 |
|
5 abstract class Action |
|
6 case object WBk extends Action |
|
7 case object WOc extends Action |
|
8 case object R extends Action |
|
9 case object L extends Action |
|
10 case object Nop extends Action |
|
11 |
|
12 type State = Int |
|
13 type Prog = List[(Action, State)] |
|
14 |
|
15 //some list functions |
|
16 def tl[A](xs: List[A]) : List[A] = xs match { |
|
17 case Nil => Nil |
|
18 case x::xs => xs |
|
19 } |
|
20 |
|
21 def hd[A](xs: List[A]) : A = xs.head |
|
22 |
|
23 def nth_of[A](xs: List[A], n: Int) = |
|
24 if (n <= xs.length) Some(xs(n)) else None |
|
25 |
|
26 |
|
27 //tapes |
|
28 case class Tape(l: List[Cell], r: List[Cell]) { |
|
29 def update(a: Action) = a match { |
|
30 case WBk => Tape(l, Bk::tl(r)) |
|
31 case WOc => Tape(l, Oc::tl(r)) |
|
32 case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r) |
|
33 case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r)) |
|
34 case Nop => Tape(l, r) |
|
35 } |
|
36 |
|
37 def read = r match { |
|
38 case Nil => Bk |
|
39 case x::_ => x |
|
40 } |
|
41 |
|
42 override def toString = |
|
43 l.reverse.map(_.toString).foldLeft("")(_+_) + |
|
44 ">" + r.map(_.toString).foldLeft("")(_+_) |
|
45 } |
|
46 |
|
47 // standard tapes |
|
48 def std(n: Int) : List[Cell] = n match { |
|
49 case 0 => List(Oc) |
|
50 case n => Oc::std(n - 1) |
|
51 } |
|
52 |
|
53 class STape(ns: Int*) extends Tape(Nil, ns.map(std).reduceLeft(_ ::: List(Bk) ::: _)) |
|
54 |
|
55 // configurations |
|
56 case class Config(s: State, tp: Tape) { |
|
57 def is_final = s == 0 |
|
58 |
|
59 override def toString = tp.toString |
|
60 } |
|
61 |
|
62 |
|
63 // Turing Machines |
|
64 case class TM(p: Prog, tp: Tape) { |
|
65 |
|
66 def fetch(s: State, a: Cell) = (s, a) match { |
|
67 case (0, _) => (Nop, 0) |
|
68 case (s, Bk) => nth_of(p, 2 * (s - 1)) match { |
|
69 case None => (Nop, 0) |
|
70 case Some(i) => i |
|
71 } |
|
72 case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match { |
|
73 case None => (Nop, 0) |
|
74 case Some(i) => i |
|
75 } |
|
76 } |
|
77 |
|
78 def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match { |
|
79 case (a, s_next) => Config(s_next, cf.tp.update(a)) |
|
80 } |
|
81 |
|
82 def steps(cf: Config, n: Int) : Config = n match { |
|
83 case 0 => cf |
|
84 case n => steps(step(cf), n - 1) |
|
85 } |
|
86 |
|
87 def steps(n: Int) : Config = steps(Config(1, tp), n) |
|
88 |
|
89 def run(cf: Config) : Config = { |
|
90 if (cf.is_final) cf else run(step(cf)) |
|
91 } |
|
92 |
|
93 def run : Tape = run(Config(1, tp)).tp |
|
94 } |
|
95 |
|
96 |
|
97 |
|
98 // examples |
|
99 class TMCopy(n: Int) extends |
|
100 TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), |
|
101 (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), |
|
102 (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), |
|
103 (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), |
|
104 (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), |
|
105 (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)), new STape(n)) |
|
106 |
|
107 println((new TMCopy(0)).run) |
|
108 |