Turing machine.

TuringMachine.hs

import Data.Map ((!), fromList, Map)

data Direction  = L | R 
type Symbol     = Char
type State      = Maybe Int
type Rules      = Map (State, Symbol) (Symbol, Direction, State)

turingMachine :: Rules -> Symbol -> [Symbol] -> [Symbol]
turingMachine rules blank tape = let

    extend [] = [blank]
    extend x  = x

    step Nothing (l, r) = reverse l ++ r
    step state   (l, r) = let
        b:bs = extend r
        (b', dir, state') = rules ! (state, b)
        in step state' $ case dir of
            L -> let a:as = extend l in (as, a:b':bs)
            R -> (b':l, bs)

    in step (Just 0) ([], tape)

add :: Rules
add = fromList [
    ((Just 0, '1'), ('1', R, Just 0)),
    ((Just 0, '+'), ('1', R, Just 1)),
    ((Just 1, '1'), ('1', R, Just 1)),
    ((Just 1, '_'), ('_', L, Just 2)),
    ((Just 2, '1'), ('_', L, Nothing))]

main :: IO ()
main = print $ turingMachine add '_' "11+11111"