1 package object turing {

     2 

     3 import scala.annotation.tailrec

     4 import lib._

     5 

     6 sealed abstract class Cell {

     7   def * (n: Int) : List[Cell] = n match {

     8     case 0 => Nil

     9     case n => this :: this * (n - 1)

    10   }

    11 }

    12 case object Bk extends Cell { override def toString = "0" }

    13 case object Oc extends Cell { override def toString = "1" }

    14 

    15 sealed abstract class Action

    16 case object WBk extends Action

    17 case object WOc extends Action

    18 case object R extends Action

    19 case object L extends Action

    20 case object Nop extends Action

    21 

    22 type State = Int

    23 type Inst = (Action, State)

    24 type Prog = List[Inst]

    25 

    26 //tapes

    27 case class Tape(l: List[Cell], r: List[Cell]) {

    28   

    29   def update(a: Action) = a match {

    30     case WBk => Tape(l, Bk::tl(r))

    31     case WOc => Tape(l, Oc::tl(r))

    32     case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)

    33     case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))

    34     case Nop => Tape(l, r)

    35   }

    36 

    37   def read = r match {

    38     case Nil => Bk

    39     case x::_ => x

    40   }

    41 

    42   override def toString = join(l.reverse) + ">" + join(r)

    43 }

    44 

    45 //standard tapes

    46 object Tape {

    47   def apply(ns: Int*) : Tape = 

    48     Tape(Nil, ns.map(n => Oc * (n + 1)).reduceLeft(_ ::: List(Bk) ::: _))

    49 }

    50 

    51 

    52 // configurations

    53 case class Config(s: State, tp: Tape) {

    54   def is_final = s == 0

    55 

    56   override def toString = tp.toString

    57 }

    58 

    59 

    60 // Turing machines

    61 case class TM(p: Prog) {

    62 

    63   def ++ (that: TM) = TM(this.p ::: that.p)

    64 

    65   def shift(n: Int) =

    66     TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})

    67   def adjust(n: Int) : TM =

    68     TM(p.map{case (a, s) => (a, if (s == 0) n else s)})

    69   def adjust : TM = adjust(p.length / 2 + 1)

    70   

    71   def fetch(s: State, a: Cell) = (s, a) match {

    72     case (0, _) => (Nop, 0)

    73     case (s, Bk) => nth_of(p, 2 * (s - 1)) match {

    74       case None => (Nop, 0)

    75       case Some(i) => i

    76     }

    77     case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {

    78       case None => (Nop, 0)

    79       case Some(i) => i

    80     }

    81   } 

    82 

    83   def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {

    84     case (a, s_next) => Config(s_next, cf.tp.update(a))

    85   }

    86 

    87   def steps(cf: Config, n: Int) : Config = n match {

    88     case 0 => cf

    89     case n => steps(step(cf), n - 1)

    90   } 

    91 

    92   @tailrec

    93   final def run(cf: Config) : Config = {

    94     if (cf.is_final) cf else run(step(cf))

    95   }

    96  

    97   def run(tp: Tape) : Tape = run(Config(1, tp)).tp

    98 }

    99 

   100 }