193
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
1 |
package object turing {
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
import scala.annotation.tailrec
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
import lib._
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
|
192
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
sealed abstract class Cell {
|
188
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
def * (n: Int) : List[Cell] = n match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
case 0 => Nil
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
case n => this :: this * (n - 1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
case object Bk extends Cell { override def toString = "0" }
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
case object Oc extends Cell { override def toString = "1" }
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
|
192
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
sealed abstract class Action
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
case object WBk extends Action
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
case object WOc extends Action
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
case object R extends Action
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
case object L extends Action
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
case object Nop extends Action
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
type State = Int
|
188
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
type Inst = (Action, State)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
type Prog = List[Inst]
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
//tapes
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
case class Tape(l: List[Cell], r: List[Cell]) {
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
def update(a: Action) = a match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
case WBk => Tape(l, Bk::tl(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
case WOc => Tape(l, Oc::tl(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
case Nop => Tape(l, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
def read = r match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
case Nil => Bk
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
case x::_ => x
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
override def toString = join(l.reverse) + ">" + join(r)
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
|
193
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
//standard tapes
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
object Tape {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
def apply(ns: Int*) : Tape =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
// configurations
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
case class Config(s: State, tp: Tape) {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
def is_final = s == 0
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
override def toString = tp.toString
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
// Turing machines
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
case class TM(p: Prog) {
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
|
188
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
def ++ (that: TM) = TM(this.p ::: that.p)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
def shift(n: Int) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
def adjust(n: Int) : TM =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
TM(p.map{case (a, s) => (a, if (s == 0) n else s)})
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
def adjust : TM = adjust(p.length / 2 + 1)
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
def fetch(s: State, a: Cell) = (s, a) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
72 |
case (0, _) => (Nop, 0)
|
188
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
case None => (Nop, 0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
case Some(i) => i
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
}
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
case None => (Nop, 0)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
case Some(i) => i
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
82 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
84 |
case (a, s_next) => Config(s_next, cf.tp.update(a))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
def steps(cf: Config, n: Int) : Config = n match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
case 0 => cf
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
case n => steps(step(cf), n - 1)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
91 |
|
191
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
@tailrec
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
final def run(cf: Config) : Config = {
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
94 |
if (cf.is_final) cf else run(step(cf))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
95 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
96 |
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
def run(tp: Tape) : Tape = run(Config(1, tp)).tp
|
176
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
98 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
99 |
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
}
|