Mercurial Mercurial > hg > tm / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
turing.scala
changeset 188 8939cc9b14f9
parent 183 4cf023ee2f4c
child 189 5974111de158
equal deleted inserted replaced
187:326310016da9 188:8939cc9b14f9 
     8 def hd[A](xs: List[A]) : A = xs.head
 
     8 def hd[A](xs: List[A]) : A = xs.head
 
     9 
     9 
    10 def nth_of[A](xs: List[A], n: Int) = 
    10 def nth_of[A](xs: List[A], n: Int) = 
    11   if (n <= xs.length) Some(xs(n)) else None 
    11   if (n <= xs.length) Some(xs(n)) else None 
    12 
    12 
    13 def replicate[A](x: A, n: Int) : List[A] = n match {
 
       
    14   case 0 => List(x)
 
       
    15   case n => x::replicate(x, n - 1)
 
       
    16 }
 
       
    17 
       
    18 
    13 
    19 //some map functions
 
    14 //some map functions
 
    20 def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
 
    15 def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
 
    21 
    16 
       
    17 
    22 //some string functions
 
    18 //some string functions
 
    23 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
 
    19 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
 
    24 
    20 
    25 
    21 
    26 
    22 
    27 abstract class Cell
 
    23 abstract class Cell {
 
       
    24   def * (n: Int) : List[Cell] = n match {
 
       
    25     case 0 => Nil
 
       
    26     case n => this :: this * (n - 1)
 
       
    27   }
 
       
    28 }
 
    28 case object Bk extends Cell { override def toString = "0" }
 
    29 case object Bk extends Cell { override def toString = "0" }
 
    29 case object Oc extends Cell { override def toString = "1" }
 
    30 case object Oc extends Cell { override def toString = "1" }
 
    30 
    31 
    31 abstract class Action
 
    32 abstract class Action
 
    32 case object WBk extends Action
 
    33 case object WBk extends Action
 
    34 case object R extends Action
 
    35 case object R extends Action
 
    35 case object L extends Action
 
    36 case object L extends Action
 
    36 case object Nop extends Action
 
    37 case object Nop extends Action
 
    37 
    38 
    38 type State = Int
 
    39 type State = Int
 
    39 type Prog = List[(Action, State)]
 
    40 type Inst = (Action, State)
 
       
    41 type Prog = List[Inst]
 
    40 
    42 
    41 //tapes
 
    43 //tapes
 
    42 case class Tape(l: List[Cell], r: List[Cell]) {
 
    44 case class Tape(l: List[Cell], r: List[Cell]) {
 
    43   def update(a: Action) = a match {
 
    45   def update(a: Action) = a match {
 
    44     case WBk => Tape(l, Bk::tl(r))
 
    46     case WBk => Tape(l, Bk::tl(r))
 
    56   override def toString = join(l.reverse) + ">" + join(r)
 
    58   override def toString = join(l.reverse) + ">" + join(r)
 
    57 }
 
    59 }
 
    58 
    60 
    59 // standard tapes
 
    61 // standard tapes
 
    60 class STape(ns: Int*) extends 
    62 class STape(ns: Int*) extends 
    61   Tape(Nil, ns.map(replicate[Cell](Oc, _)).reduceLeft(_ ::: List(Bk) ::: _))
 
    63   Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
 
    62   
    64   
    63 
    65 
    64 // configurations
 
    66 // configurations
 
    65 case class Config(s: State, tp: Tape) {
 
    67 case class Config(s: State, tp: Tape) {
 
    66   def is_final = s == 0
 
    68   def is_final = s == 0
 
    69 }
 
    71 }
 
    70 
    72 
    71 
    73 
    72 // Turing machines
 
    74 // Turing machines
 
    73 case class TM(p: Prog) {
 
    75 case class TM(p: Prog) {
 
       
    76 
       
    77   def ++ (that: TM) = TM(this.p ::: that.p)
 
    74 
    78 
    75   def shift(n: Int) =
 
    79   def shift(n: Int) =
 
    76     TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
 
    80     TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
 
    77   
    81   
    78   def fetch(s: State, a: Cell) = (s, a) match {
 
    82   def fetch(s: State, a: Cell) = (s, a) match {
 
    79     case (0, _) => (Nop, 0)
 
    83     case (0, _) => (Nop, 0)
 
    80       case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    84     case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    81         case None => (Nop, 0)
 
    85       case None => (Nop, 0)
 
    82         case Some(i) => i
 
    86       case Some(i) => i
 
    83       }
 
    87     }
 
    84     case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
 
    88     case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
 
    85       case None => (Nop, 0)
 
    89       case None => (Nop, 0)
 
    86       case Some(i) => i
 
    90       case Some(i) => i
 
    87     }
 
    91     }
 
    88   } 
    92   } 
   100     if (cf.is_final) cf else run(step(cf))
 
   104     if (cf.is_final) cf else run(step(cf))
 
   101   }
 
   105   }
 
   102  
   106  
   103   def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 
   107   def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 
   104 }
 
   108 }
 
   105 
       
   106 
   109 
   107 
   110 
   108 // Turing machine examples
 
   111 // Turing machine examples
 
   109 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
   112 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
   110                      (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   113                      (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   113                      (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   116                      (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   114                      (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
 
   117                      (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
 
   115 
   118 
   116 def TMFindnth(n: Int) : TM = n match {
 
   119 def TMFindnth(n: Int) : TM = n match {
 
   117   case 0 => TM(Nil)
 
   120   case 0 => TM(Nil)
 
   118   case n => {
 
   121   case n => TMFindnth(n - 1) ++ TM(List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
 
   119     val tm = TMFindnth(n - 1)
 
       
   120     TM(tm.p ::: List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
 
       
   121   }
 
       
   122 }
 
   122 }
 
   123 
   123 
   124 def TMMopup(n: Int) = {
 
   124 def TMMopup(n: Int) = {
 
   125   def TMMopup1(n: Int) : TM = n match {
 
   125   def TMMopup1(n: Int) : TM = n match {
 
   126     case 0 => TM(Nil)
 
   126     case 0 => TM(Nil)
 
   127     case n => {
 
   127     case n => TMMopup1(n - 1) ++ TM(List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
 
   128       val tm = TMMopup1(n - 1) 
       
   129       TM(tm.p ::: List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
 
       
   130     }
 
       
   131   }
 
   128   }
 
   132 
   129 
   133   val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
 
   130   val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
 
   134                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
 
   131                          (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
 
   135 
   132 
   136   val tm1 = TMMopup1(n)
 
   133   TMMopup1(n) ++ TMMopup2.shift(2 * n)
 
   137   val tm2 = TMMopup2.shift(2 * n)
 
   134 }
 
   138   TM(tm1.p ::: tm2.p)
 
   135 
   139 }
 
       
   140 
   136 
   141 println("TMCopy:    " + (TMCopy.run(new STape(3))))
 
   137 println("TMCopy:    " + (TMCopy.run(new STape(3))))
 
   142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
 
   138 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
 
   143 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
   139 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
   144 
   140 
   171 
   167 
   172 case class Abacus(p: AProg) {
 
   168 case class Abacus(p: AProg) {
 
   173 
   169 
   174   def shift(offset: Int, jump: Int) = Abacus(p.map(ashift(_, offset, jump)))
 
   170   def shift(offset: Int, jump: Int) = Abacus(p.map(ashift(_, offset, jump)))
 
   175   def adjust(old_jump: Int, jump: Int) = Abacus(p.map(aadjust(_, old_jump, jump)))
 
   171   def adjust(old_jump: Int, jump: Int) = Abacus(p.map(aadjust(_, old_jump, jump)))
 
       
   172 
       
   173   //def toTM()
 
   176  
   174  
   177   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
 
   175   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
 
   178     case (None, _) => cf
 
   176     case (None, _) => cf
 
   179     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
 
   177     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
 
   180     case (Some(Dec(n, l)), s) => {
 
   178     case (Some(Dec(n, l)), s) => {
 
   220 
   218 
   221 println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
 
   219 println("Copy: " + (Copy(0, 1, -1).run(Map(0 -> 3, 1 -> 0))))
 
   222 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
 
   220 println("Plus: 3 + 4 " + (Plus(0, 1, 2, -1).run(Map(0 -> 3, 1 -> 4, 2 -> 0))))
 
   223 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
 
   221 println("Mult: 3 * 5 " + (Mult(0, 1, 2, 3, -1).run(Map(0 -> 3, 1 -> 5, 2 -> 0, 3 -> 0))))
 
   224 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
   222 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
       
   223 
       
   224 
       
   225 // Abacus to TM translation
 
       
   226 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
       
   227                     (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
 
       
   228                     (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
 
       
   229 
       
   230 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
       
   231                     (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
 
       
   232                     (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
 
       
   233                     (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
 
       
   234                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
       
   235                     (R, 0), (WBk, 16)))
 
       
   236 
       
   237 def TMINC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
 
       
   238 
       
   239 def TMDEC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
 
       
   240 
       
   241 
       
   242 
   225 
   243 
   226 //Recursive Functions
 
   244 //Recursive Functions
 
   227 abstract class Rec {
 
   245 abstract class Rec {
 
   228   def eval(ns: List[Int]) : Int
 
   246   def eval(ns: List[Int]) : Int
 
   229 }
 
   247 }
tm