equal
deleted
inserted
replaced
1 package object turing { |
1 package object turing { |
2 |
2 |
3 import scala.annotation.tailrec |
3 import scala.annotation.tailrec |
4 import lib._ |
4 import lib._ |
5 |
5 |
|
6 // tape cells |
6 sealed abstract class Cell { |
7 sealed abstract class Cell { |
7 def * (n: Int) : List[Cell] = n match { |
8 def * (n: Int) : List[Cell] = n match { |
8 case 0 => Nil |
9 case 0 => Nil |
9 case n => this :: this * (n - 1) |
10 case n => this :: this * (n - 1) |
10 } |
11 } |
11 } |
12 } |
12 case object Bk extends Cell { override def toString = "0" } |
13 case object Bk extends Cell { override def toString = "0" } |
13 case object Oc extends Cell { override def toString = "1" } |
14 case object Oc extends Cell { override def toString = "1" } |
14 |
15 |
|
16 // actions |
15 sealed abstract class Action |
17 sealed abstract class Action |
16 case object WBk extends Action |
18 case object WBk extends Action |
17 case object WOc extends Action |
19 case object WOc extends Action |
18 case object R extends Action |
20 case object R extends Action |
19 case object L extends Action |
21 case object L extends Action |
21 |
23 |
22 type State = Int |
24 type State = Int |
23 type Inst = (Action, State) |
25 type Inst = (Action, State) |
24 type Prog = List[Inst] |
26 type Prog = List[Inst] |
25 |
27 |
26 //tapes |
28 // tapes |
27 case class Tape(l: List[Cell], r: List[Cell]) { |
29 case class Tape(l: List[Cell], r: List[Cell]) { |
28 |
30 |
29 def update(a: Action) = a match { |
31 def update(a: Action) = a match { |
30 case WBk => Tape(l, Bk::tl(r)) |
32 case WBk => Tape(l, Bk::tl(r)) |
31 case WOc => Tape(l, Oc::tl(r)) |
33 case WOc => Tape(l, Oc::tl(r)) |
40 } |
42 } |
41 |
43 |
42 override def toString = join(l.reverse) + ">" + join(r) |
44 override def toString = join(l.reverse) + ">" + join(r) |
43 } |
45 } |
44 |
46 |
45 //standard tapes |
47 // standard tapes |
46 object Tape { |
48 object Tape { |
47 def apply(ns: Int*) : Tape = |
49 def apply(ns: Int*) : Tape = |
48 Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _)) |
50 Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _)) |
49 } |
51 } |
50 |
|
51 |
52 |
52 // configurations |
53 // configurations |
53 case class Config(s: State, tp: Tape) { |
54 case class Config(s: State, tp: Tape) { |
54 def is_final = s == 0 |
55 def is_final = s == 0 |
55 |
56 |
56 override def toString = tp.toString |
57 override def toString = tp.toString |
57 } |
58 } |
58 |
59 |
59 |
|
60 // Turing machines |
60 // Turing machines |
61 case class TM(p: Prog) { |
61 case class TM(p: Prog) { |
62 |
62 |
|
63 // simple composition |
63 def ++ (that: TM) = TM(this.p ::: that.p) |
64 def ++ (that: TM) = TM(this.p ::: that.p) |
64 |
65 |
65 def shift(n: Int) = |
66 def shift(n: Int) = |
66 TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)}) |
67 TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)}) |
67 def adjust(n: Int) : TM = |
68 def adjust(n: Int) : TM = |
95 } |
96 } |
96 |
97 |
97 def run(tp: Tape) : Tape = run(Config(1, tp)).tp |
98 def run(tp: Tape) : Tape = run(Config(1, tp)).tp |
98 } |
99 } |
99 |
100 |
|
101 // some syntactical convenience |
|
102 object TM { |
|
103 def apply(is: Inst*) : TM = TM(is.toList) |
100 } |
104 } |
|
105 |
|
106 } |