--- a/scala/turing.scala Thu Feb 21 16:07:40 2013 +0000
+++ b/scala/turing.scala Fri Feb 22 14:31:34 2013 +0000
@@ -3,6 +3,7 @@
import scala.annotation.tailrec
import lib._
+// tape cells
sealed abstract class Cell {
def * (n: Int) : List[Cell] = n match {
case 0 => Nil
@@ -12,6 +13,7 @@
case object Bk extends Cell { override def toString = "0" }
case object Oc extends Cell { override def toString = "1" }
+// actions
sealed abstract class Action
case object WBk extends Action
case object WOc extends Action
@@ -23,7 +25,7 @@
type Inst = (Action, State)
type Prog = List[Inst]
-//tapes
+// tapes
case class Tape(l: List[Cell], r: List[Cell]) {
def update(a: Action) = a match {
@@ -42,13 +44,12 @@
override def toString = join(l.reverse) + ">" + join(r)
}
-//standard tapes
+// standard tapes
object Tape {
def apply(ns: Int*) : Tape =
Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))
}
-
// configurations
case class Config(s: State, tp: Tape) {
def is_final = s == 0
@@ -56,10 +57,10 @@
override def toString = tp.toString
}
-
// Turing machines
case class TM(p: Prog) {
+ // simple composition
def ++ (that: TM) = TM(this.p ::: that.p)
def shift(n: Int) =
@@ -97,4 +98,9 @@
def run(tp: Tape) : Tape = run(Config(1, tp)).tp
}
+// some syntactical convenience
+object TM {
+ def apply(is: Inst*) : TM = TM(is.toList)
}
+
+}