Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.