--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/turing.scala	Fri Feb 15 18:24:00 2013 +0000
@@ -0,0 +1,108 @@
+abstract class Cell
+case object Bk extends Cell { override def toString = "0" }
+case object Oc extends Cell { override def toString = "1" }
+
+abstract class Action
+case object WBk extends Action
+case object WOc extends Action
+case object R extends Action
+case object L extends Action
+case object Nop extends Action
+
+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 
+
+
+//tapes
+case class Tape(l: List[Cell], r: List[Cell]) {
+  def update(a: Action) = a match {
+    case WBk => Tape(l, Bk::tl(r))
+    case WOc => Tape(l, Oc::tl(r))
+    case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)
+    case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))
+    case Nop => Tape(l, r)
+  }
+
+  def read = r match {
+    case Nil => Bk
+    case x::_ => x
+  }
+
+  override def toString = 
+    l.reverse.map(_.toString).foldLeft("")(_+_) + 
+    ">" + r.map(_.toString).foldLeft("")(_+_)
+}
+
+// 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(std).reduceLeft(_ ::: List(Bk) ::: _))
+  
+// configurations
+case class Config(s: State, tp: Tape) {
+  def is_final = s == 0
+
+  override def toString = tp.toString
+}
+
+
+// Turing Machines
+case class TM(p: Prog, tp: Tape) {
+  
+  def fetch(s: State, a: Cell) = (s, a) match {
+    case (0, _) => (Nop, 0)
+      case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
+        case None => (Nop, 0)
+        case Some(i) => i
+      }
+    case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
+      case None => (Nop, 0)
+      case Some(i) => i
+    }
+  } 
+
+  def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {
+    case (a, s_next) => Config(s_next, cf.tp.update(a))
+  }
+
+  def steps(cf: Config, n: Int) : Config = n match {
+    case 0 => cf
+    case n => steps(step(cf), n - 1)
+  } 
+
+  def steps(n: Int) : Config = steps(Config(1, tp), n)
+
+  def run(cf: Config) : Config = {
+    if (cf.is_final) cf else run(step(cf))
+  }
+ 
+  def run : Tape = run(Config(1, tp)).tp
+}
+
+
+
+// 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)), new STape(n))
+
+println((new TMCopy(0)).run)
+