Skip to content

Instantly share code, notes, and snippets.

@gclaramunt
Created October 3, 2011 03:26
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save gclaramunt/1258371 to your computer and use it in GitHub Desktop.
Turing Machine in purely functional Scala
val I= left _
val D= right _
case class Tape(l:List[Symb],head:Symb, r:List[Symb]){
override def toString = ( l.reverse ++ (head::r) ).mkString.trim
}
// less painful tape builder from a string, setting the head at the start char of the list
def tape(s:String)= right (Tape(Nil,b,s.toList ))
def write(c:Symb, t:Tape)=Tape(t.l,c,t.r)
def read(t:Tape)= t.head
//infinite tape: it grows with blanks when any end is reached
def left(t:Tape)=t match {
case Tape(Nil,head,right) =>Tape(Nil,b,head::right)
case Tape(left,head,right) =>Tape(left.tail,left.head,head::right)
}
def right(t:Tape)=t match {
case Tape(left,head,Nil) =>Tape(head::left,b,Nil)
case Tape(left,head,right) =>Tape(head::left,right.head,right.tail)
}
@tailrec
final def step(q:State, t:Tape,tm:TrnsMtrx, qf:State):Tape =
if (q == qf ) t else {
val (qnew,c,move)=tm (q)(t.head);
step(qnew,move(write(c,t)),tm,qf)
}
object TMsample extends App {
val machine=new TuringMachine[Symbol]()
import machine._
// map current state -> symbol -> (new state, symbol to write, direction )
val tm:TrnsMtrx = Map(
'q1->Map('1'->('q1,'1',D), '0'->('q1,'0',D), '#'->('q1,'#',D), b->('q2,b,I)),
'q2->Map('1'->('q3,b,I), '#'->('qf,b,I)),
'q3->Map('1'->('q3,'1',I),'#'->('q4,'#',I)),
'q4->Map('1'->('q4,'0',I),'0'->('q1,'1',D),b->('q1,'1',D))
)
println ( step ('q1, tape("0#11"), tm,'qf))
println ( step ('q1, tape("100#" ), tm,'qf))
println ( step ('q1, tape("1000#11" ), tm,'qf))
println ( step ('q1, tape("1111#1" ), tm,'qf))
println ( step ('q1, tape("1#11" ), tm,'qf))
println ( step ('q1, tape("1#111" ), tm,'qf))
}
//transition matrix
type Move=Tape=>Tape
type TrnsMtrx= Map[State, Map[Symb,(State,Symb,Move)]]
import scala.annotation.tailrec
class TuringMachine[State]{
type Symb=Char
val b=' ';
case class Tape(l:List[Symb],head:Symb, r:List[Symb]){
override def toString = ( l.reverse ++ (head::r) ).mkString.trim
}
// less painful tape builder from a string, setting the head at the start char of the list
def tape(s:String)= right (Tape(Nil,b,s.toList ))
def write(c:Symb, t:Tape)=Tape(t.l,c,t.r)
def read(t:Tape)= t.head
//infinite tape: it grows with blanks when any end is reached
def left(t:Tape)=t match {
case Tape(Nil,head,right) =>Tape(Nil,b,head::right)
case Tape(left,head,right) =>Tape(left.tail,left.head,head::right)
}
def right(t:Tape)=t match {
case Tape(left,head,Nil) =>Tape(head::left,b,Nil)
case Tape(left,head,right) =>Tape(head::left,right.head,right.tail)
}
val I= left _
val D= right _
//transition matrix
type Move=Tape=>Tape
type TrnsMtrx= Map[State, Map[Symb,(State,Symb,Move)]]
@tailrec
final def step(q:State, t:Tape,tm:TrnsMtrx, qf:State):Tape =
if (q == qf ) t else {
val (qnew,c,move)=tm (q)(t.head);
step(qnew,move(write(c,t)),tm,qf)
}
}
object TMsample extends App {
val machine=new TuringMachine[Symbol]()
import machine._
// map current state -> symbol -> (new state, symbol to write, direction )
val tm:TrnsMtrx = Map(
'q1->Map('1'->('q1,'1',D), '0'->('q1,'0',D), '#'->('q1,'#',D), b->('q2,b,I)),
'q2->Map('1'->('q3,b,I), '#'->('qf,b,I)),
'q3->Map('1'->('q3,'1',I),'#'->('q4,'#',I)),
'q4->Map('1'->('q4,'0',I),'0'->('q1,'1',D),b->('q1,'1',D))
)
println ( step ('q1, tape("0#11"), tm,'qf))
println ( step ('q1, tape("100#" ), tm,'qf))
println ( step ('q1, tape("1000#11" ), tm,'qf))
println ( step ('q1, tape("1111#1" ), tm,'qf))
println ( step ('q1, tape("1#11" ), tm,'qf))
println ( step ('q1, tape("1#111" ), tm,'qf))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment