# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1361012528 0
# Node ID 8248f8adf17d91d2aef046a0a6477f56283723ce
# Parent  1c2e639d4e549f40b6f5cb2e84685b31bc5bd4e1
added some TM machines

diff -r 1c2e639d4e54 -r 8248f8adf17d turing.scala
--- a/turing.scala	Sat Feb 16 09:07:07 2013 +0000
+++ b/turing.scala	Sat Feb 16 11:02:08 2013 +0000
@@ -1,3 +1,29 @@
+
+//some list functions
+def tl[A](xs: List[A]) : List[A] = xs match {
+  case Nil => Nil
+  case x::xs => xs
+}
+
+def hd[A](xs: List[A]) : A = xs.head
+
+def nth_of[A](xs: List[A], n: Int) = 
+  if (n <= xs.length) Some(xs(n)) else None 
+
+def replicate[A](x: A, n: Int) : List[A] = n match {
+  case 0 => List(x)
+  case n => x::replicate(x, n - 1)
+}
+
+
+//some map functions
+def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
+
+//some string functions
+def join[A](xs: List[A]) = xs.foldLeft("")(_.toString + _)
+
+
+
 abstract class Cell
 case object Bk extends Cell { override def toString = "0" }
 case object Oc extends Cell { override def toString = "1" }
@@ -12,22 +38,6 @@
 type State = Int
 type Prog = List[(Action, State)]
 
-//some list functions
-def tl[A](xs: List[A]) : List[A] = xs match {
-  case Nil => Nil
-  case x::xs => xs
-}
-
-def hd[A](xs: List[A]) : A = xs.head
-
-def nth_of[A](xs: List[A], n: Int) = 
-  if (n <= xs.length) Some(xs(n)) else None 
-
-//some map functions
-def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)
-
-
-
 //tapes
 case class Tape(l: List[Cell], r: List[Cell]) {
   def update(a: Action) = a match {
@@ -43,19 +53,14 @@
     case x::_ => x
   }
 
-  override def toString = 
-    l.reverse.map(_.toString).foldLeft("")(_+_) + 
-    ">" + r.map(_.toString).foldLeft("")(_+_)
+  override def toString = join(l.reverse) + ">" + join(r)
 }
 
 // standard tapes
-def std(n: Int) : List[Cell] = n match {
-  case 0 => List(Oc)
-  case n => Oc::std(n - 1)
-}
+class STape(ns: Int*) extends 
+  Tape(Nil, ns.map(replicate[Cell](Oc, _)).reduceLeft(_ ::: List(Bk) ::: _))
+  
 
-class STape(ns: Int*) extends Tape(Nil, ns.map(std).reduceLeft(_ ::: List(Bk) ::: _))
-  
 // configurations
 case class Config(s: State, tp: Tape) {
   def is_final = s == 0
@@ -66,6 +71,9 @@
 
 // Turing Machines
 case class TM(p: Prog) {
+
+  def shift(n: Int) =
+    TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})
   
   def fetch(s: State, a: Cell) = (s, a) match {
     case (0, _) => (Nop, 0)
@@ -98,15 +106,41 @@
 
 
 // examples
-class TMCopy(n: Int) extends 
-  TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
-          (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
-          (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
-          (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
-          (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
-          (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
+val TMCopy = TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
+                     (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
+                     (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
+                     (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
+                     (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
+                     (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))
+
+def TMFindnth(n: Int) : TM = n match {
+  case 0 => TM(Nil)
+  case n => {
+    val tm = TMFindnth(n - 1)
+    TM(tm.p ::: List((WOc, 2 * n - 1), (R, 2 * n), (R, 2 * n + 1), (R, 2 * n)))
+  }
+}
 
-println("TM: " + (new TMCopy(0)).run(new STape(3)))
+def TMMopup(n: Int) = {
+  def TMMopup1(n: Int) : TM = n match {
+    case 0 => TM(Nil)
+    case n => {
+      val tm = TMMopup1(n - 1) 
+      TM(tm.p ::: List((R, 2 * n + 1), (WBk, 2 * n), (R, 2 * n - 1), (WOc, 2 * n)))
+    }
+  }
+
+  val TMMopup2 = TM(List((R, 2), (R, 1), (L, 5), (WBk, 3), (R, 4), (WBk, 3),
+                         (R, 2), (WBk, 3), (L, 5), (L, 6), (R, 0), (L, 6)))
+
+  val tm1 = TMMopup1(n)
+  val tm2 = TMMopup2.shift(2 * n)
+  TM(tm1.p ::: tm2.p)
+}
+
+println("TMCopy:    " + (TMCopy.run(new STape(3))))
+println("TMfindnth: " + (TMFindnth(3).run(new STape(1,2,3,4,5))))
+println("TMMopup: "   + (TMMopup(3).run(new STape(1,2,3,4,5))))
 
 
 // Abacus
@@ -118,8 +152,6 @@
 type AProg = List[AInst]
 type Regs = Map[Int, Int]
 
-
-
 case class AConfig(s: Int, regs: Regs)  
 
 case class Abacus(p: AProg) {