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)