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 178 8248f8adf17d
parent 177 1c2e639d4e54
child 179 650e7a7a389b
equal deleted inserted replaced
177:1c2e639d4e54 178:8248f8adf17d 
       
     1 
       
     2 //some list functions
 
       
     3 def tl[A](xs: List[A]) : List[A] = xs match {
 
       
     4   case Nil => Nil
 
       
     5   case x::xs => xs
 
       
     6 }
 
       
     7 
       
     8 def hd[A](xs: List[A]) : A = xs.head
 
       
     9 
       
    10 def nth_of[A](xs: List[A], n: Int) = 
       
    11   if (n <= xs.length) Some(xs(n)) else None 
       
    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 
       
    19 //some map functions
 
       
    20 def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
 
       
    21 
       
    22 //some string functions
 
       
    23 def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
 
       
    24 
       
    25 
       
    26 
     1 abstract class Cell
 
    27 abstract class Cell
 
     2 case object Bk extends Cell { override def toString = "0" }
 
    28 case object Bk extends Cell { override def toString = "0" }
 
     3 case object Oc extends Cell { override def toString = "1" }
 
    29 case object Oc extends Cell { override def toString = "1" }
 
     4 
    30 
     5 abstract class Action
 
    31 abstract class Action
 
     9 case object L extends Action
 
    35 case object L extends Action
 
    10 case object Nop extends Action
 
    36 case object Nop extends Action
 
    11 
    37 
    12 type State = Int
 
    38 type State = Int
 
    13 type Prog = List[(Action, State)]
 
    39 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 //some map functions
 
       
    27 def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
 
       
    28 
       
    29 
       
    30 
    40 
    31 //tapes
 
    41 //tapes
 
    32 case class Tape(l: List[Cell], r: List[Cell]) {
 
    42 case class Tape(l: List[Cell], r: List[Cell]) {
 
    33   def update(a: Action) = a match {
 
    43   def update(a: Action) = a match {
 
    34     case WBk => Tape(l, Bk::tl(r))
 
    44     case WBk => Tape(l, Bk::tl(r))
 
    41   def read = r match {
 
    51   def read = r match {
 
    42     case Nil => Bk
 
    52     case Nil => Bk
 
    43     case x::_ => x
 
    53     case x::_ => x
 
    44   }
 
    54   }
 
    45 
    55 
    46   override def toString = 
    56   override def toString = join(l.reverse) + ">" + join(r)
 
    47     l.reverse.map(_.toString).foldLeft("")(_+_) + 
       
    48     ">" + r.map(_.toString).foldLeft("")(_+_)
 
       
    49 }
 
    57 }
 
    50 
    58 
    51 // standard tapes
 
    59 // standard tapes
 
    52 def std(n: Int) : List[Cell] = n match {
 
    60 class STape(ns: Int*) extends 
    53   case 0 => List(Oc)
 
    61   Tape(Nil, ns.map(replicate[Cell](Oc, _)).reduceLeft(_ ::: List(Bk) ::: _))
 
    54   case n => Oc::std(n - 1)
 
    62   
    55 }
 
       
    56 
    63 
    57 class STape(ns: Int*) extends Tape(Nil, ns.map(std).reduceLeft(_ ::: List(Bk) ::: _))
 
       
    58   
       
    59 // configurations
 
    64 // configurations
 
    60 case class Config(s: State, tp: Tape) {
 
    65 case class Config(s: State, tp: Tape) {
 
    61   def is_final = s == 0
 
    66   def is_final = s == 0
 
    62 
    67 
    63   override def toString = tp.toString
 
    68   override def toString = tp.toString
 
    64 }
 
    69 }
 
    65 
    70 
    66 
    71 
    67 // Turing Machines
 
    72 // Turing Machines
 
    68 case class TM(p: Prog) {
 
    73 case class TM(p: Prog) {
 
       
    74 
       
    75   def shift(n: Int) =
 
       
    76     TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
 
    69   
    77   
    70   def fetch(s: State, a: Cell) = (s, a) match {
 
    78   def fetch(s: State, a: Cell) = (s, a) match {
 
    71     case (0, _) => (Nop, 0)
 
    79     case (0, _) => (Nop, 0)
 
    72       case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    80       case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    73         case None => (Nop, 0)
 
    81         case None => (Nop, 0)
 
    96 }
 
   104 }
 
    97 
   105 
    98 
   106 
    99 
   107 
   100 // examples
 
   108 // examples
 
   101 class TMCopy(n: Int) extends 
   109 val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
   102   TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
   110                      (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   103           (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   111                      (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
   104           (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
   112                      (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
   105           (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
   113                      (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   106           (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   114                      (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
 
   107           (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
 
       
   108 
   115 
   109 println("TM: " + (new TMCopy(0)).run(new STape(3)))
 
   116 def TMFindnth(n: Int) : TM = n match {
 
       
   117   case 0 => TM(Nil)
 
       
   118   case 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 }
 
       
   123 
       
   124 def TMMopup(n: Int) = {
 
       
   125   def TMMopup1(n: Int) : TM = n match {
 
       
   126     case 0 => TM(Nil)
 
       
   127     case 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   }
 
       
   132 
       
   133   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)))
 
       
   135 
       
   136   val tm1 = TMMopup1(n)
 
       
   137   val tm2 = TMMopup2.shift(2 * n)
 
       
   138   TM(tm1.p ::: tm2.p)
 
       
   139 }
 
       
   140 
       
   141 println("TMCopy:    " + (TMCopy.run(new STape(3))))
 
       
   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))))
 
   110 
   144 
   111 
   145 
   112 // Abacus
 
   146 // Abacus
 
   113 abstract class AInst 
   147 abstract class AInst 
   114 case class Inc(n: Int) extends AInst
 
   148 case class Inc(n: Int) extends AInst
 
   115 case class Dec(n: Int, l: Int) extends AInst
 
   149 case class Dec(n: Int, l: Int) extends AInst
 
   116 case class Goto(l: Int) extends AInst
 
   150 case class Goto(l: Int) extends AInst
 
   117 
   151 
   118 type AProg = List[AInst]
 
   152 type AProg = List[AInst]
 
   119 type Regs = Map[Int, Int]
 
   153 type Regs = Map[Int, Int]
 
   120 
       
   121 
       
   122 
   154 
   123 case class AConfig(s: Int, regs: Regs)  
   155 case class AConfig(s: Int, regs: Regs)  
   124 
   156 
   125 case class Abacus(p: AProg) {
 
   157 case class Abacus(p: AProg) {
 
   126   
   158
tm