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 192 3c1107984b41
parent 191 98370b96c1c5
equal deleted inserted replaced
191:98370b96c1c5 192:3c1107984b41 
    19 //some string functions
 
    19 //some string functions
 
    20 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
 
    20 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
 
    21 
    21 
    22 
    22 
    23 
    23 
    24 abstract class Cell {
 
    24 sealed abstract class Cell {
 
    25   def * (n: Int) : List[Cell] = n match {
 
    25   def * (n: Int) : List[Cell] = n match {
 
    26     case 0 => Nil
 
    26     case 0 => Nil
 
    27     case n => this :: this * (n - 1)
 
    27     case n => this :: this * (n - 1)
 
    28   }
 
    28   }
 
    29 }
 
    29 }
 
    30 case object Bk extends Cell { override def toString = "0" }
 
    30 case object Bk extends Cell { override def toString = "0" }
 
    31 case object Oc extends Cell { override def toString = "1" }
 
    31 case object Oc extends Cell { override def toString = "1" }
 
    32 
    32 
    33 abstract class Action
 
    33 sealed abstract class Action
 
    34 case object WBk extends Action
 
    34 case object WBk extends Action
 
    35 case object WOc extends Action
 
    35 case object WOc extends Action
 
    36 case object R extends Action
 
    36 case object R extends Action
 
    37 case object L extends Action
 
    37 case object L extends Action
 
    38 case object Nop extends Action
 
    38 case object Nop extends Action
 
   142 println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
 
   142 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))))
 
   143 println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
   144 
   144 
   145 
   145 
   146 // Abacus machines
 
   146 // Abacus machines
 
   147 abstract class AInst 
   147 sealed abstract class AInst 
   148 case class Inc(n: Int) extends AInst
 
   148 case class Inc(n: Int) extends AInst
 
   149 case class Dec(n: Int, l: Int) extends AInst
 
   149 case class Dec(n: Int, l: Int) extends AInst
 
   150 case class Goto(l: Int) extends AInst
 
   150 case class Goto(l: Int) extends AInst
 
   151 
   151 
   152 
   152 
   179       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
 
   179       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
 
   180     }
 
   180     }
 
   181     case (Some(Goto(l)), _) => AConfig(l, cf.regs)
 
   181     case (Some(Goto(l)), _) => AConfig(l, cf.regs)
 
   182   }  
   182   }  
   183 
   183 
   184   
       
   185   def steps(cf: AConfig, n: Int) : AConfig = n match {
 
   184   def steps(cf: AConfig, n: Int) : AConfig = n match {
 
   186     case 0 => cf
 
   185     case 0 => cf
 
   187     case n => steps(step(cf), n - 1)
 
   186     case n => steps(step(cf), n - 1)
 
   188   } 
   187   } 
   189 
   188 
   218 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
   217 println("Expo: 3 ^ 4 " + (Expo(0, 1, 2, 3, 4, -1).run(Map(0 -> 4, 1 -> 3, 2 -> 0, 3 -> 0, 4 -> 0))))
 
   219 
   218 
   220 
   219 
   221 
   220 
   222 // Abacus to TM translation
 
   221 // Abacus to TM translation
 
   223 type Layout = List[Int]
 
       
   224 
       
   225 def layout(p: AProg) = p.map(_ match {
 
   222 def layout(p: AProg) = p.map(_ match {
 
   226   case Inc(n) => 2 * n + 9 
   223   case Inc(n) => 2 * n + 9 
   227   case Dec(n, _) => 2 * n + 16 
   224   case Dec(n, _) => 2 * n + 16 
   228   case Goto(n) => 1
 
   225   case Goto(n) => 1
 
   229 })
 
   226 })
 
   230 
   227 
   231 def start(ly: Layout, n: Int) = ly.take(n).sum + 1
 
   228 def start(p: AProg, n: Int) = layout(p).take(n).sum + 1
 
   232 
   229 
   233 val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
   230 def compile_Inc(s: Int, n: Int) = {
 
   234                     (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
 
   231   val TMInc = TM(List((WOc, 1), (R, 2), (WOc, 3), (R, 2), (WOc, 3), (R, 4), 
   235                     (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
 
   232                       (L, 7), (WBk, 5), (R, 6), (WBk, 5), (WOc, 3), (R, 6),
 
   236 
   233                       (L, 8), (L, 7), (R, 9), (L, 7), (R, 10), (WBk, 9)))
 
   237 val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
   234   TMFindnth(n).shift(s - 1) ++ TMInc.shift(2 * n).shift(s - 1)
 
   238                     (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
 
   235 }
 
   239                     (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
 
   236 
   240                     (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
 
   237 def compile_Dec(s: Int, n: Int, e: Int) = {
 
   241                     (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
   238   val TMDec = TM(List((WOc, 1), (R, 2), (L, 14), (R, 3), (L, 4), (R, 3),
 
   242                     (R, 0), (WBk, 16)))
 
   239                       (R, 5), (WBk, 4), (R, 6), (WBk, 5), (L, 7), (L, 8),
 
   243 
   240                       (L, 11), (WBk, 7), (WOc, 8), (R, 9), (L, 10), (R, 9),
 
   244 def TMINC(s: Int, n: Int) = (TMFindnth(n) ++ TMInc.shift(2 * n)).shift(s - 1)
 
   241                       (R, 5), (WBk, 10), (L, 12), (L, 11), (R, 13), (L, 11),
 
   245 
   242                       (R, 17), (WBk, 13), (L, 15), (L, 14), (R, 16), (L, 14),
 
   246 def TMDEC(s: Int, n: Int, e: Int) = TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
 
   243                       (R, 0), (WBk, 16)))
 
   247 
   244   TMFindnth(n).shift(s - 1) ++ TMDec.shift(2 * n).shift(s - 1).adjust(e)
 
   248 def TMGOTO(n: Int) = TM(List((Nop, n), (Nop, n)))
 
   245 }
 
   249 
   246 
   250 def compile(ly: Layout, s: Int, i: AInst) = i match {
 
   247 def compile_Goto(s: Int) = {
 
   251   case Inc(n) => TMINC(s, n)
 
   248   val TMGoto = TM(List((Nop, 1), (Nop, 1)))
 
   252   case Dec(n, e) => TMDEC(s, n, start(ly, e))
 
   249   TMGoto.shift(s - 1)
 
   253   case Goto(e) => TMGOTO(start(ly, e))
 
   250 }
 
       
   251 
       
   252 def compile(p: AProg, s: Int, i: AInst) = i match {
 
       
   253   case Inc(n) => compile_Inc(s, n)
 
       
   254   case Dec(n, e) => compile_Dec(s, n, start(p, e))
 
       
   255   case Goto(e) => compile_Goto(start(p, e))
 
   254 }
 
   256 }
 
   255 
   257 
   256 def tms(p: AProg) = {
 
   258 def tms(p: AProg) = {
 
   257   val ss = (0 until p.length).map (start(layout(p),_))
 
   259   val ss = (0 until p.length).map (start(p,_))
 
   258   (ss zip p).map{case (n, i) => compile(layout(p), n, i)}
 
   260   (ss zip p).map{case (n, i) => compile(p, n, i)}
 
   259 }
 
   261 }
 
   260 
   262 
   261 def toTM(p: AProg) = tms(p).reduceLeft(_ ++ _)
 
   263 def toTM(p: AProg) = tms(p).reduceLeft(_ ++ _)
 
   262 
   264 
   263 //examples
 
   265 //examples
tm