Coding

Turing Machine in CoffeeScript

langsIf you’ve ever taken a formal languages class and you’ve been following along with my CoffeeScript experiments, then you probably already guessed that this post was coming.  Well, here it is, a CoffeeScript implementation of the Standard Turing Machine.

This is the last CoffeeScript post that I have on my stack.  Not that I won’t ever write about CoffeeScript again, but I don’t have any immediate ideas about what to write next, while I have plenty of ideas about other subjects.  For me, this post is very different than my last two CoffeeScript posts, because this time I am not translating from C/C++.  We haven’t had a homework assignment to implement a Turing Machine, so I don’t have a reference implementation to work from.  This machine was implemented in CoffeeScript from the start, but lessons learned from implementing the deterministic finite automaton and the pushdown automaton certainly gave me a head start.

Node.js

This implementation is also a little different because I finished the experiment using node.js.  I started out on coffeescript.org, but as the number of machines and test cases grew, I got tired of clicking OK on each alert.  Getting started with node.js and CoffeeScript was really easy.   I simply downloaded the windows installer from http://nodejs.org and ran the msi.  After installation, I started a command interpreter and typed “node” at the prompt.  On one machine, node came right up, but on two others I needed to reboot for node to show up in the path.  Maybe I just rebooted the first machine and forgot, but if you are having trouble, try a reboot.  I followed the instructions on http://coffeescript.org to install the coffee-script module using the node package manager.  After that, I was able to run scripts locally on my machine.

Turing Machine

The graphic at the top of this entry describes two languages and one function, each of which can be implemented using a Turing Machine.  I’m not qualified to assert that only a Turing Machine could accept the languages.  I’m pretty sure that the language of even-length strings could be accepted by a finite state machine, which would mean it could also be accepted by pushdown automata.  Certainly it seems likely that the function could not be computed by the more primitive machines, since they have no way to write the computation result.  The second language violates the pumping lemma for context free languages (actually violates the pumping lemma for regular languages too), so we know from an “academic” perspective that neither finite or pushdown automata could accept it.  But I spent a few minutes trying to figure out why a pushdown would fail to accept this language.

If we tried to accept L={a^nb^nc^n:n>=0} with a pushdown, we could start by counting the ‘a’ characters.  We could count them by pushing some symbol onto the pushdown’s stack, lets use X as that symbol.  So we would push some number of X onto the stack, until we encountered the first “b” character.  We would then want to remove an X from the stack, to account for the fact that the language requires the same number of as and bs.  But this wont work.  We still need to know how many as or bs there were so we can use that knowledge to verify the correct number of “c” characters.  So we should put that X back on the stack.  But if we put the X on the stack and keep reading, then we have no way of accounting for the fact that we just read a “b”.  So we are stuck.  This thought experiment might not be academically exhaustive, but it gives me enough intuitive comfort to agree with the textbook that this language cannot be accepted by a PDA.

blockquoteThe Turing Machine moves past this limitation by getting rid of the stack and replacing it with a “tape”.  You can think of a tape as a combination of a list, a stack, and a queue.  CoffeeScript arrays are well suited for emulating Turing’s tape.  You can iterate over the array or access elements at random, which allows the machine to move back and forth over it’s tape.  You have the unshift function, which lets the tape extend infinitely to the left, and the push function, which allows the machine to extend infinitely to the right.  Of course, we are bounded by the real word constraint of needing to store the array’s index, which limits us to 32-bit array sizes if I recall correctly, but for the purposes of this experiment, that boundary is irrelevant.

The tape is presented to the machine with input data already written on it and bounded on the left and right by “blank” symbols.  But, the machine is allowed to update the tape if it wants to, which sets it apart from state machines and pushdowns.  Also, the machine is allowed to move back and forth over the tape, whereas simpler machines are only allowed to read it from beginning to end.  These two differences allow the Turing Machine to keep track of all the data needed to recognize the language of equal numbers of as, bs and cs.  After working through a couple examples, I’ll finish by showing my solution for recognizing this language.  Be forewarned, this post is really long.

Implementation

Here is the gist.

As I mentioned, this implementation started in the CoffeeScript REPL, and ended on node.js.  The REPL runs as a browser and you can use the alert method to show results in message boxes, while node.js runs with a console attached and has no alert method.  The first little problem after migrating was getting output from the alerts into the console.  So we start with a little shim:

alert = (s) -> console.log s

To run the code in the REPL, just remove or comment this line.  With that out of the way, we start by defining the result object for the Turing Machine’s transition function:

createResult = (state, symbol, direction) ->
 nextState: state
 writeSymbol: symbol
 moveTo: direction
 toString: () -> [this.nextState, this.writeSymbol, this.moveTo].join ", "

When a the machine finds a rule that matches, it will need to update its state, write something to the tape and move left or right.  This object delivers that data to the machine, and includes an override of the toString method to facilitate debugging.

createRule = (state, symbol, result) ->
 inState: state
 readSymbol: symbol
 transitionResult: result
 match: (s, y) -> true if (this.inState == s && this.readSymbol == y)
 toString: () -> [this.inState, this.readSymbol, this.transitionResult].join ", "

The Turing Machine rules must match the machine’s current state and the symbol read off the tape.  The match function checks the member data against the data passed in by the machine and returns true when they are the same.  Again, toString is overridden.

createTape = (s, blank) ->
 t = [ blank ].concat s.split ''
 t.push blank
 pos = 0
 pos++ while t[pos] == blank
 pos-- while t[pos] == undefined
 return {
  currentPosition: pos
  buffer: t
  currentSym: () -> this.buffer[this.currentPosition]
  write: (s) -> this.buffer[this.currentPosition] = s
  moveRight: () ->
   p = this.currentPosition
   p++
   this.buffer.push blank if p == this.buffer.length
   this.currentPosition = p
   return null
  moveLeft: () ->
   p = this.currentPosition
   p--
   if p < 0
    this.buffer.unshift blank
    p = 0
   this.currentPosition = p
   return null
  move: (d) ->
   this.moveRight() if d == 'R'
   this.moveLeft() if d == 'L'
   return null
  toString: () -> (this.buffer.join ", ") + " pos: " + this.currentPosition
  }

Next, I’ve defined the behavior of the tape.  Although CoffeeScript arrays are well suited for use as Turing tapes, they need a little help in order to make the behavior more transparent to the machine.  We construct a tape object by providing two pieces of data, the first is a string loaded with the input that we want to pass to the machine.  The second piece of data is the symbol used to indicate to the machine that a cell is empty.  This can be whatever you want it to be, as long as it doesn’t interfere with the symbols used in the machine’s computations.  I found it very convenient to use a ‘B’ rather than null or undefined or some other option.  In C/C++ I would not hesitate to use (char)0 since this is still just a regular character.

Anyway, when we provide this data to the constructor function the function allocates a new array and puts the blank symbol in position 0.  Then, it splits the string into an array of characters and adds that to the buffer.  Finally, it adds another blank to the end of the buffer.  The conventional way to reason about Turing Machines starts the machine with the tape advanced to the leftmost non-blank character.  To support this convention, the tape constructor scans right until it finds a non-blank, or hits an undefined cell (which happens if the empty string “” is passed to the method).  If the constructor does hit the undefined area, it scans left again until it finds the initialized portion of the buffer.  Now, it is ready to construct the object to return by assigning the index and the buffer to a new object.  The methods on the tape object support the methods defined for Turing’s tape, currentSym reads the symbol at the index, write will update the buffer at the index.  The moveRight method will increase the index, and if the new index exceeds the length of the buffer, a new blank is added to the right side of the tape.  Likewise, the moveLeft method will decrease the index, and if the index becomes negative, the buffer is padded on the left side with a blank, and the index is moved back to 0 so that it points at the newly added blank.  The move method decides which of these two methods to use based on the value passed in by the machine, and finally the toString method will return the current contents of the tape along with the position of the read/write head.

Finally we come to the machine:

createMachine = (rules, initialState, blank, finalStates) ->
 transitionRules: rules
 currentState: initialState
 blankSymbol: blank
 acceptanceStates: finalStates
 tape: createTape '', blank
 isHalted: false
 toString: () -> 
  r = this.transitionRules.join "|| "
  f = this.acceptanceStates.join ", "
  [ r, this.currentState, this.blankSymbol, f, this.tape].join ":: "
 acceptedInput: () -> this.currentState in this.acceptanceStates
 loadTape: (s) -> this.tape = createTape s, this.blankSymbol
 readTape: () -> this.tape
 update: (r) ->
  this.currentState = r.nextState
  this.tape.write r.writeSymbol
  this.tape.move r.moveTo
  return null
 read: () ->
  q = this.currentState
  s = this.tape.currentSym()
  for rule in this.transitionRules
   if rule.match q, s
    return this.update rule.transitionResult
  return this.isHalted = true
 run: (s) ->
  this.loadTape s
  this.read() until this.isHalted
  return null

Like most of my machines, it takes a set of rules, the initial state and the set of acceptance states.  The Turing Machine also takes the symbol to use for blanks.  Like I mentioned above, a ‘B’ worked out just fine for me.  The tape is initialized with the empty string, and we also have a flag to indicate that the machine has halted.  Previously we simply read all the characters from the input and halted at the end, even if we entered a dead configuration before reading all the characters.  Since the Turing Machine can move back and forth, reaching the end of the input is not automatically a good place to stop processing, so this flag allows the machine to signal its done.  Like the other machines we have an acceptedInput method which allows the machine to indicate if it stopped in an acceptance state.  New to the Turing Machine is the loadTape method, which takes a string initializes a new tape instance, and a readTape method which allows us to check the contents of the tape.  We need this for machines that compute functions, because we will need to know more than whether the machine accepted the input, we want to look at the tape to see the results of the computation.

The update method applies the changes to the machine and the tape supplied by a rule result when the machine finds a matching rule.  On several of these methods I went ahead and returned null explicitly because I found it kind of annoying that CoffeeScript generated returns for methods where I don’t intend the results to convey useful information.  I could have reordered the instructions in the update method so that the assignment to current state occurred last, as I did with the pushdown automaton.  However, in methods like the run method, CoffeeScript allocates an array and generates a collection as the loop implied by the “until” expression is processed.  But it only does this because it thinks you want to automatically return the results from the last expression in the method.   By returning null, that loop is no longer the last statement, and CoffeeScript doesn’t bother generating the array.  Does this really matter?  I’m no expert, I just thought the extra array was kind of annoying.

I’ll wrap up the description of the machine functions by saying that the read method reads the current tape symbol and tries to find a matching rule.  If it can’t find a match, it flips the isHalted flag.  The run method loads the tape with the user input, then calls the read method until the halt flag is set.

I mentioned that we didn’t have a homework assignment to implement a Turing Machine, which is not to say that we did not have an assignment to describe a few machines.  It was my intention from the get-go to use this machine to work out the answers to my homework, so I create a method that would facilitate running different machine configurations with different test strings.

runMachine = (f, i) ->
 m = f()
 m.run i
 alert "input: " + i + " accepted: " + m.acceptedInput() + " tape: " + m.readTape()

This method expects a factory method that produces a fully configured machine, runs it, then alert/prints the results.

Now we are ready to build some machines.

Example

The first machine was a simple machine from our class lecture notes.  This factory method produces it by creating the necessary rule set, then returning the results from createMachine with appropriate parameters.

# Example from lecture
exampleMachine = () -> 
 exampleRuleSet = [ 
  createRule 0, 'a', createResult 0, 'b', 'R'
  createRule 0, 'b', createResult 0, 'b', 'R'
  createRule 0, 'B', createResult 1, 'B', 'L'
 ]
 createMachine exampleRuleSet, 0, 'B', [ 1 ]

This machine reads a tape full of as and bs, and converts all the as into bs.  It accepts the input if it manages to reach the rightmost blank.  We can test it with these lines.

runMachine exampleMachine, "aaa"
runMachine exampleMachine, "aba"
runMachine exampleMachine, "bbb"
runMachine exampleMachine, "caa"

With the three simple rules, the machine is able to convert the first three strings to all bs, but can’t do anything with the fourth since it has no rules for dealing with cs.

L = { w : |w| is even }

Our next machine accepts even length strings composed of as and bs.

m1 = () ->
 ruleSet = [
   createRule 0, 'B', createResult 5, 'B', 'L' # accept the empty string
   createRule 0, 'a', createResult 1, 'X', 'R' # replace the first a or b with an X
   createRule 0, 'b', createResult 1, 'X', 'R'
   createRule 0, 'Y', createResult 4, 'Y', 'R' # possibly located the tail
   createRule 1, 'a', createResult 1, 'a', 'R' # scan right until {B, Y}
   createRule 1, 'b', createResult 1, 'b', 'R'
   createRule 1, 'B', createResult 2, 'B', 'L'
   createRule 1, 'Y', createResult 2, 'Y', 'L' 
   createRule 2, 'a', createResult 3, 'Y', 'L' # replace first a or b with Y
   createRule 2, 'b', createResult 3, 'Y', 'L'   
   createRule 3, 'a', createResult 3, 'a', 'L' # scan left until X
   createRule 3, 'b', createResult 3, 'b', 'L'
   createRule 3, 'X', createResult 0, 'X', 'R'   
   createRule 4, 'Y', createResult 4, 'Y', 'R' # tail should be all Y
   createRule 4, 'B', createResult 5, 'B', 'L' # accept
 ]
 createMachine ruleSet, 0, 'B', [ 5 ]

We replace valid characters on the left side with X symbols.  Every time we write an X, we move to the right side and replace the rightmost a or b with Y, then we repeat.  If the string is even length, the X and Y string should meet in the middle.  The machine states will let us know if we have found the middle.  Lets look at a failing case:

runMachine m1, "a"

When the machine starts, the tape is positioned at this “a”, and the machine is in state 0.  The second rule in the list will match.  The machine will move to state 1, it will overwrite the “a” with an “X”, and it will move the tape to the right.  Now it is in state 1 and looking at a blank.  The matching rule will move the machine to state 2 and move the tape to the left.  Now the tape is positioned over the “X” again, and it is in state 2.  However, there is no rule that explains what to do with an X in state 2.  If the string had an even length, then there would be an a or b under the head right now, and the machine would replace that symbol with a Y.  But it found an X before finding an a or b to replace, therefore the string length must be odd.  The machine halts in state 2.  State 2 is not in the set of acceptance states, so the string is rejected.

Now consider an passing case:

runMachine m1, "ab"

We start off by replacing the “a” with an X.  Then we scan past the “b” until we hit the right side blank.  We bounce off the blank and end up looking at the “b” again, in state 2 as we were in the last example.  This time, we can still act because we have a rule that matches b in state 2.  We write a Y, go left, and change to state 3.  In state 3, we find an X, switch to sate 0 and move right again.  We are back looking at the Y we just wrote.  This time we are fine though, because in state 0, if we find a Y, it could mean we are done, we just need to check that we have all Ys to the right of our current position.  If we scan past all the Ys and reach the right blank again, we go to state 5, which is the acceptance state.  There are no transitions out of state 5, so the machine will halt.  The gist has a few more example strings that should be enough to exercise the entire rule set.

f(x) = 3x

This machine will multiply the input by 3.  The input will be expressed as strings of “1″ characters.   So 1 = “1”, 2 = “11” and so on.  This notation is called unary notation, its not particularly fun for humans, or as efficient as binary notation, but as we will see, it makes life easy on the machine.  We’re optimizing for compact rule sets when we can, and introducing more numerals just makes the number of states and rules grow.

m2 = () ->
 ruleSet = [
  createRule 0, 'B', createResult 1, 'B', 'L' # accept empty string
  createRule 0, '1', createResult 2, 'X', 'R' # replace all 1 with X
  createRule 2, '1', createResult 2, 'X', 'R'
  createRule 2, 'B', createResult 3, 'B', 'L' # Found the right side B, now return to leftside B
  createRule 3, 'X', createResult 3, 'X', 'L'
  createRule 3, '1', createResult 3, '1', 'L'
  createRule 3, 'B', createResult 4, 'B', 'R' # Found the left side B, now look for an X
  createRule 4, '1', createResult 9, '1', 'R' # Found 1 before finding X, check all '1's
  createRule 4, 'X', createResult 5, 'B', 'R' # Erase an X and look for the rightside B
  createRule 5, 'X', createResult 5, 'X', 'R' 
  createRule 5, '1', createResult 5, '1', 'R'
  createRule 5, 'B', createResult 6, '1', 'R' # Write 3 ones
  createRule 6, 'B', createResult 7, '1', 'R'
  createRule 7, 'B', createResult 8, '1', 'R'
  createRule 8, 'B', createResult 3, 'B', 'L' # Repeat search for additional X
  createRule 9, '1', createResult 9, '1', 'R' # Checking string for all '1's 
  createRule 9, 'B', createResult 1, 'B', 'L' # accept 
 ]

createMachine ruleSet, 0, 'B', [ 1 ]

The first thing we do in this algorithm is accept the empty string.  Why?  Because 0 times 3 is 0.  The tape starts with no “1”s written on it, and ends with no “1”s written on it, that’s the expected result.  But its more interesting if there is something written on the tape, so lets look at this example:

runMachine m2, "111" # 3 x 3 = 9

We replace all the 1s with X until we reach the right boundary.  This is how the machine counts.  Once it is done counting, it returns to the left boundary, then backs up a step so it is looking at the leftmost X.  During these operations it has transitioned from state 0 (replace all 1s) to state 2 (find the left most X).  Now that it found the left most X, it erases it by writing a blank, and moves right.  This time around it finds another X, and this means it is not done yet, so it keeps scanning to the right, past any more Xs or 1s, until it finds the right boundary.  When it finds the right side blank, it writes down three ones.  The tape expands to the right to allow the machine to do what it wants, always providing a new right side boundary whenever the machine decides to overwrite the current boundary.  When it is done writing the 1s, it returns to state 3, which causes the machine to scan left until it finds a blank (which is at the site of the first X we erased.)  The machine bounces off the blank and ends up looking at another X, so it erases this and moves to the right end again so that it can write down three more 1s.  It repeats this until it finds that there are no more Xs after scanning to the left boundary.  When it finds a 1 next to the left boundary, it will scan right again, verifying that the tape is filled entirely with 1s, if it scans all 1s on the way to the right boundary, it accepts the string.  We can then look at the tape and see that 9 1s are written on it.

L = { anbncn | n >= 0 }

So we are back to the textbook example of a language that a pushdown automaton cannot accept.  The Turing Machine can accept it, given the right rule set.  My solution involves the double application of the even-length string algorithm, with the erasure semantics of the multiplication algorithm.  It may not be necessary to erase as we go, but it seemed like an obvious way to compute the answer.

m3 = () ->
 ruleSet = [
  createRule 0, 'B', createResult 1, 'B', 'L' # accept empty string
  createRule 0, 'a', createResult 2, 'X', 'R' # replace all a with X
  createRule 2, 'a', createResult 2, 'X', 'R'
  createRule 2, 'b', createResult 3, 'b', 'L' # until we find a 'b'
  createRule 3, 'X', createResult 3, 'X', 'L' # scan left until Blank
  createRule 3, 'Y', createResult 3, 'Y', 'L'
  createRule 3, 'b', createResult 3, 'b', 'L'
  createRule 3, 'c', createResult 3, 'c', 'L'
  createRule 3, 'B', createResult 4, 'B', 'R'
  createRule 4, 'X', createResult 5, 'B', 'R' # Find and erase an X
  createRule 4, 'Y', createResult 7, 'B', 'R' # Find and erase a Y... done with X
  createRule 4, 'Z', createResult 9, 'Z', 'R' # Found Z, check that string is all Z
  createRule 5, 'X', createResult 5, 'X', 'R' # scan right until { c, Y }
  createRule 5, 'b', createResult 5, 'b', 'R'
  createRule 5, 'c', createResult 6, 'c', 'L'
  createRule 5, 'Y', createResult 6, 'Y', 'L'
  createRule 6, 'b', createResult 3, 'Y', 'L' # scan left to b, write Y, repeat X search
  createRule 7, 'Y', createResult 7, 'Y', 'R' # Scan right past {Y, c} until { B, Z }
  createRule 7, 'c', createResult 7, 'c', 'R'
  createRule 7, 'Z', createResult 8, 'Z', 'L'
  createRule 7, 'B', createResult 8, 'B', 'L'
  createRule 8, 'c', createResult 3, 'Z', 'L' # Scan left to c, Write Z, repeat Y search
  createRule 9, 'Z', createResult 9, 'Z', 'R' # scan right past Z until B
  createRule 9, 'B', createResult 1, 'B', 'L' # accept
 ]
 createMachine ruleSet, 0, 'B', [ 1 ]

We start by treating the c characters as a left side boundary, effectively ignoring them.  We don’t care how many cs there are unless we can first prove that there are an equal number of as and bs.  We can prove there are an equal number of as and bs by converting our “a” characters to a “stack” of Xs on the tape. Every time we pop (erase) an X, we should be able to find a b and replace it with a Y.  If we are unable to empty the stack of Xs, then we didn’t have enough bs.  If we are unable to replace all the bs with Ys, then we had too many bs.

If we are able to empty the stack of Xs, and we have no more bs, then we know that |a| == |b|, and we have a stack of Ys on the tape in the same quantity.  So, |a| == |b| == |Y|.  We will also have zero or more cs to the right of the Ys.  We can now use the same technique to start popping Ys, and converting cs to Zs.   If we cant pop all the Ys, that’s a fail.   If we run out of Ys before converting the last c, that’s a fail too.  If we pop the last Y right before converting the last remaining c, then we have a balanced string.  We scan past the Zs one last time, and accept the string once we confirm there are no stray cs.

runMachine m3, ""          # valid n = 0
runMachine m3, "a"         # invalid
runMachine m3, "ab"        # invalid
runMachine m3, "abc"       # valid n = 1

There’s a few examples, there are more in the gist.  I hope you enjoyed reading about my little CoffeeScript machines.  I had quite a bit of fun working on them, especially on the Turing Machine.  For some reason, the Turing Machine gave me the same sense of wonder that I felt when I first started programming.  I think that in working from Turing’s blueprints I felt connected in some corny way to an individual who played a critical role in making what I do every day possible.

I hope you’ll play with the machines and if you see any room for improvement, let me know.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s