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 177 1c2e639d4e54
parent 176 d2c85556d290
child 178 8248f8adf17d
equal deleted inserted replaced
176:d2c85556d290 177:1c2e639d4e54 
    20 
    20 
    21 def hd[A](xs: List[A]) : A = xs.head
 
    21 def hd[A](xs: List[A]) : A = xs.head
 
    22 
    22 
    23 def nth_of[A](xs: List[A], n: Int) = 
    23 def nth_of[A](xs: List[A], n: Int) = 
    24   if (n <= xs.length) Some(xs(n)) else None 
    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 
    25 
    29 
    26 
    30 
    27 //tapes
 
    31 //tapes
 
    28 case class Tape(l: List[Cell], r: List[Cell]) {
 
    32 case class Tape(l: List[Cell], r: List[Cell]) {
 
    29   def update(a: Action) = a match {
 
    33   def update(a: Action) = a match {
 
    59   override def toString = tp.toString
 
    63   override def toString = tp.toString
 
    60 }
 
    64 }
 
    61 
    65 
    62 
    66 
    63 // Turing Machines
 
    67 // Turing Machines
 
    64 case class TM(p: Prog, tp: Tape) {
 
    68 case class TM(p: Prog) {
 
    65   
    69   
    66   def fetch(s: State, a: Cell) = (s, a) match {
 
    70   def fetch(s: State, a: Cell) = (s, a) match {
 
    67     case (0, _) => (Nop, 0)
 
    71     case (0, _) => (Nop, 0)
 
    68       case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    72       case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
 
    69         case None => (Nop, 0)
 
    73         case None => (Nop, 0)
 
    82   def steps(cf: Config, n: Int) : Config = n match {
 
    86   def steps(cf: Config, n: Int) : Config = n match {
 
    83     case 0 => cf
 
    87     case 0 => cf
 
    84     case n => steps(step(cf), n - 1)
 
    88     case n => steps(step(cf), n - 1)
 
    85   } 
    89   } 
    86 
    90 
    87   def steps(n: Int) : Config = steps(Config(1, tp), n)
 
       
    88 
       
    89   def run(cf: Config) : Config = {
 
    91   def run(cf: Config) : Config = {
 
    90     if (cf.is_final) cf else run(step(cf))
 
    92     if (cf.is_final) cf else run(step(cf))
 
    91   }
 
    93   }
 
    92  
    94  
    93   def run : Tape = run(Config(1, tp)).tp
 
    95   def run(tp: Tape) : Tape = run(Config(1, tp)).tp
 
    94 }
 
    96 }
 
    95 
    97 
    96 
    98 
    97 
    99 
    98 // examples
 
   100 // examples
 
   100   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), 
   101           (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   103           (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
   102           (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
   104           (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
   103           (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
   105           (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
   104           (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   106           (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
   105           (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)), new STape(n))
 
   107           (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
 
   106 
   108 
   107 println((new TMCopy(0)).run)
 
   109 println("TM: " + (new TMCopy(0)).run(new STape(3)))
 
   108 
   110 
       
   111 
       
   112 // Abacus
 
       
   113 abstract class AInst 
       
   114 case class Inc(n: Int) extends AInst
 
       
   115 case class Dec(n: Int, l: Int) extends AInst
 
       
   116 case class Goto(l: Int) extends AInst
 
       
   117 
       
   118 type AProg = List[AInst]
 
       
   119 type Regs = Map[Int, Int]
 
       
   120 
       
   121 
       
   122 
       
   123 case class AConfig(s: Int, regs: Regs)  
       
   124 
       
   125 case class Abacus(p: AProg) {
 
       
   126   
       
   127   def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
 
       
   128     case (None, _) => cf
 
       
   129     case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
 
       
   130     case (Some(Dec(n, l)), s) => {
 
       
   131       if (dget(cf.regs, n) == 0) AConfig(l, cf.regs)
 
       
   132       else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
 
       
   133     }
 
       
   134     case (Some(Goto(l)), _) => AConfig(l, cf.regs)
 
       
   135   }  
       
   136 
       
   137   def steps(cf: AConfig, n: Int) : AConfig = n match {
 
       
   138     case 0 => cf
 
       
   139     case n => steps(step(cf), n - 1)
 
       
   140   } 
       
   141 
       
   142   def steps(regs: Regs, n: Int) : AConfig = steps(AConfig(0, regs), n)
 
       
   143 
       
   144   def run(cf: AConfig) : AConfig = {
 
       
   145     if (cf.s >= p.length || cf.s < 0) cf else run(step(cf))
 
       
   146   }
 
       
   147  
       
   148   def run(regs: Regs): Regs = run(AConfig(0, regs)).regs
 
       
   149 }
 
       
   150 
       
   151 // examples
 
       
   152 class Copy(in: Int, out: Int) extends 
       
   153   Abacus(List(Dec(in, -1), Inc(out), Goto(0))) 
       
   154 
       
   155 class Plus(in1: Int, in2: Int, out: Int) extends 
       
   156   Abacus(List(Dec(in1, 4), Inc(in2), Inc(out),
 
       
   157               Goto(0), Dec(out, -1), Inc(in1), Goto(4))) 
       
   158 
       
   159 
       
   160 println("Ab: " + (new Plus(0, 1, 2)).run(Map(0 -> 3, 1 -> 4)))
tm