Turing Machine in Scala

I am currently enrolled in a theoretical computer science class. Last week, we started learning about Turing machines. The professor wrote and made available a small Turing machine simulator that we can use to write and run simple programs. Unfortunately for the students using Linux or MacOS X, the program is written in C# and runs only on Windows.

I decided to write my own little Turing machine simulator in Scala. The code is short (~40 lines of code) and I felt like sharing it.

First a small introduction to Turing machines (as I understand them):

• The controller stores the current state that the machine is in. It can hold only one state at a time.
• The tape is an infinite array onto which we can write characters.
• The head points to a character on the tape.
• The head can move one position backward or forward (left or right).
• When the program is loaded, the initial input is copied at the beginning of the tape. The rest of the tape consists of blanks.
• The transition function takes the current state and current character under the head and sets a new state, writes a new character on the tape and moves left or right.
• The programs runs until the state is ACCEPTED or REJECTED.

I may have forgotten some details, but that’s the gist of it. Now let’s see how we implement a Turing Machine.

import scala.collection.mutable.Map

Right off the bat, we’re going to make the Haskell people cry in agony and use a mutable Map in our program. We’ll see later what it’s used for.

object Direction extends Enumeration {
  val left = Value(-1)
  val right = Value(1)
}

We define an enumeration type that represents the two directions where the head can go. We used the values -1 and 1 to make the actual move a simple addition.

class Tape(input: String) {
  private val tape: Array[Char] = Array.fill(65536)('_')
  private var head: Int = 0
  for (i <- 0 until input.length) {
    tape(i) = input(i)
  }

  def getValue() = tape(head)
  def setValue(c: Char) = tape(head) = c
  def move(d: Direction.Value) = head += d.id
}

This is the class that represents the tape. It has a private member called tape which is an array of 65,536 characters initialized to the underscore character (which will be our blank character). It also has a private member called head which emulates the Turing machine’s head. It’s just an integer value that indicates which is the “active cell” on the tape. The constructor of Tape takes a string that is copied onto the tape.

The methods getValue() and setValue() respectively read the current character and write a new value onto the tape. move() changes the position of head. d.id gives us the -1 or 1 value that we defined earlier in Direction.

class TuringMachine(private var input: String, private var state: String) {
  private val tape = new Tape(input)
  private val transition: Map[(String, Char), (String, Char, Direction.Value)] = Map()

  def addRule(tuple: ((String, Char), (String, Char, Direction.Value))) {
    transition(tuple._1) = tuple._2
  }

  def execute() {
    while (state != "ACCEPTED" && state != "REJECTED") {
      val value = tape.getValue
      val (newState, newValue, direction) = transition((state, value))
      println(newState, newValue, direction)
      state = newState
      tape.setValue(newValue)
      tape.move(direction)
    }
    println(state)
  }
}

This is the main class that brings everything together. A TuringMachine’s constructor receives an input to be written on the tape and an initial state. A TuringMachine has a Map (dictionnary) from (String, Char) — a 2-tuple representing the current state and character — to (String, Char, Direction.Value), a 3-tuple that contains the new state, new character and direction for the head.

addRule() is a simple function that adds an entry to the transition map.

execute() loops until the state is either “ACCEPTED” or “REJECTED”. Inside the loop, we take the value on the tape and the state, find the transition rule associated with that pair, and update the state, the tape and the head. We print every intermediary step. When the loop is done, we print the final state.

And that’s it. That’s our Turing machine. Now, let’s write a small program for it:

object TuringMachine {
  def usage() {
    println("Usage: scala TuringMachine  ")
    exit(1)
  }

  def main(args: Array[String]) {
    if (args.length != 2)
      usage()

    val tm = new TuringMachine(args(0), args(1))
    tm.addRule(("even", '0') -> ("even",     '0', Direction.right))
    tm.addRule(("even", '1') -> ("odd",      '1', Direction.right))
    tm.addRule(("even", '_') -> ("ACCEPTED", '_', Direction.right))
    tm.addRule(("odd",  '0') -> ("odd",      '0', Direction.right))
    tm.addRule(("odd",  '1') -> ("even",     '1', Direction.right))
    tm.addRule(("odd",  '_') -> ("REJECTED", '_', Direction.right))

    tm.execute()
  }
}

This is a program that, given an input of ones and zeros, accepts the program if the number of ones is even and rejects the program otherwise. Here’s a sample execution with the string “110101″ and given an initial state of “even” (since 0 ones is even):

$ scala -cp . TuringMachine 110101 even
(odd,1,right)
(even,1,right)
(even,0,right)
(odd,1,right)
(odd,0,right)
(even,1,right)
(ACCEPTED,_,right)
ACCEPTED

Advertisement