diff -r 317a2532c567 -r fc2a5e9fbb97 scala/turing.scala --- 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) } + +}