I'm not sure of the purpose of spending the first article on something as irrelevant as parsing when he could just be using Ruby's rich support for data literal

I'm not sure of the purpose of spending the first article on something as irrelevant as parsing when he could just be using Ruby's rich support for data literals. One mildly interesting aspect of simulating a Turing machine is how you deal with the doubly-infinite tape. Haskell already has support for singly-infinite lists, so you can implement it very easily: data Command s v = Halt | GoLeft s v | GoRight s v type Tape v = ([v], [v]) -- Both lists must be infinite. type Next s v = s -> v -> Command s v turing :: Next s v -> s -> Tape v -> Tape v turing f s t@(l:ls, r:rs) = case f s r of GoLeft s' v -> turing f s' (ls, l:v:rs) GoRight s' v -> turing f s' (v:l:ls, rs) Halt -> t If your Turing machine simulator is much more verbose than this, you are probably doing it wrong. As an example, here's a Turing machine that counts the parity of the rightward run of 1s from the tape head's starting position, writes it to the tape, and halts: data Bit = Zero | One deriving Show data ParityState = Even | Odd | Done parityTM = turing next Even where next Even One = GoRight Odd Zero next Odd One = GoRight Even Zero next Even Zero = GoRight Done Zero next Odd Zero = GoRight Done One next Done _ = Halt To test it, here's a helper function that converts a Haskell integer into a tape containing all 0s to the left, a run of n 1s to the right, followed by all 0s, and runs the Turing machine on it: parity :: Int -> Bit parity n = head $ fst $ parityTM (repeat Zero, replicate n One ++ repeat Zero)