Hi Roger, This is an interesting way to represent the machine. At first, I didn't see why the states had types like: state1 :: String -> Char -> String -> Bool But now I see that, in: state1 x h y = ... x is the portion of the tape left of the head, h is the character under the head, and y is the portion of the tape to the right. One idea would be to represent the left part of the tape backwards. That is, if the tape looks like: [..., 0, 1, 2, 3, 4, ...] ^ Instead of representing the tape state as the tuple ([..., 0, 1], 2, [3, 4, ...]), use ([1, 0, ...], 2, [3, 4, ...]). This will let you avoid walking the entire left part of the tape to match patterns like: (x++"X") For instance, your state3 would look like: state3 x h y = state4 ('X':x) (head y) (tail y) It's neat that you represent state transitions as tail calls to other states. I wrote a Turing Machine representation recently [1] which I believe is a bit more traditional. It allows you to parameterize the machine over any type of symbols or states, and gives a general way to represent tapes. There, the transitions are represented by a function of type: state -> sym -> Maybe (state, sym, Shift) Nick [1] https://gist.github.com/nvanderw/6821856 On 10/12/2013 01:55 PM, Costello, Roger L. wrote:

Hi Folks,

I implemented, in Haskell, a Turing Machine that decides if a string is a member of the language consisting of an equal number of a's, b's, and c's, i.e., anbncn.

http://www.xfront.com/Turing-Machines/an-bn-cn/TM.hs.txt

/Roger _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners