{-

Turing Machine to decide if a string is
an element of the language consisting of
an equal number of a's, b's, and c's, i.e.
anbncn

States:

1. If head = B then halt with true

2. If head != a then halt with false

3. Write X, move right

4. While head = a or head = X move right

5. If head != b then halt with false

6. Write X, move right

7. While head = b or head = X move right

8. If head != c then halt with false

9. Write X, move left

10. While head != B move left

11. Move right

12. While head = X move right

13. Goto 1.

-}

tm :: String -> Bool
tm s | s == "" =  state1 "" 'B' ""
tm s | otherwise = state1 "B" (head s) ((tail s) ++ "B")

state1 x h y  | h == 'B' = True
state1 x h y  | otherwise = state2 x h y

state2 x h y  | h /= 'a' = False
state2 x h y  | otherwise = state3 x h y

state3 x h y  = state4 (x++"X") (head y) (tail y) 

state4 x h y  | h == 'a' = state4 (x++[h]) (head y) (tail y)
state4 x h y  | h == 'X' = state4 (x++[h]) (head y) (tail y)
state4 x h y  | otherwise = state5 x h y

state5 x h y  | h /= 'b' = False
state5 x h y  | otherwise = state6 x h y

state6 x h y  = state7 (x++"X") (head y) (tail y)

state7 x h y  | h == 'b' = state7 (x++[h]) (head y) (tail y)
state7 x h y  | h == 'X' = state7 (x++[h]) (head y) (tail y)
state7 x h y  | otherwise = state8 x h y

state8 x h y  | h /= 'c' = False
state8 x h y  | otherwise = state9 x h y

state9 x h y  =  state10 (init x) (last x) ("X" ++ y)

state10 x h y  | h /= 'B' = state10 (init x) (last x) (h:y)
state10 x h y  | otherwise = state11 x h y

state11 x h y  = state12 (x++[h]) (head y) (tail y)

state12 x h y  | h == 'X' = state12 (x++[h]) (head y) (tail y)
state12 x h y  | otherwise = state13 x h y

state13 x h y  = state1 x h y

-- Tests

t1 = tm "aabbcc" 		-- returns True

t2 = tm "abbcc" 		-- returns False

t3 = tm "aabbccc"		-- returns False

t4 = tm "aaaaaabbbbbbcccccc" 	-- returns True

t5 = tm ""			-- returns True