[Haskell-beginners] Turing machine that decides if a string is an element of an-bn-cn

[Nick Vanderweit]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 295 bytes
Desc: OpenPGP digital signature
URL: <http://www.haskell.org/pipermail/beginners/attachments/20131013/ba68b297/attachment.sig>