Building a Turing Machine Simulator With Ruby (Part 1)

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)