Assignment 5

Home

Turing Machines

Related Reading: Omnibus Chapters 31, SOE Chapters 5 and 9.

Due:  Midnight Sunday Feb 24, 2008

  1. Define functions to do the following tasks.  Do not use recursion -- instead, use higher-order functions, such as map, foldl, foldr, zipWith, and so on.
    bulletAdd pairwise the elements of two lists. 
    For example, addPairs [1,2,3] [4,5,6] => [5,7,9].
    bulletApply pairwise functions in one list to values in another.
    For example, applyAll [(+1),(*2),(/3)] [4,5,6] => [5,10,2].
    bulletApply the elements of a list (which are functions) to a given value. 
    For example, applyEach [(+1),(+2),(+3)] 42 => [43,44,45].
    bulletDetermine the maximum element in a non-empty list.
    For example, maxList [1,3,2] => 3.
    bulletAdd the sublists of a list, and then add the results.
    For example: addLists [[1,2,3],[4,5,6],[7,8,9]] => 45.
     
  2. The tape on a Turing Machine can be represented in Haskell as the following data type:

        data Tape a = Tape [a] a [a]

    The idea is that a tape of the form "Tape xs y zs" has the symbol y under the head, the symbols xs (an infinite list) to the left, and the symbols zs (also infinite) to the right.  Define three functions:

        moveLeft, moveRight :: Tape a -> Tape a
        write :: Tape a -> a -> Tape a

    that do what their names and types implicitly suggest.
     
  3. A Turing Machine can be captured by the following data type:

        data TM a s = TM [a]                                 -- alphabet
                         [s]                                 -- set of states
                         s                                   -- initial state
                         (Tape a)                            -- initial tape
                         (s -> Tape a -> Maybe (s, Tape a))  -- transition function

    If the transition function returns Nothing, we consider the Turing Machine to have halted.  Define a function runTM :: TM a s -> Tape a  that "runs" a Turing Machine until it halts, returning the tape as its result.  If the TM does not halt, then neither will runTM.  Note the following:
    bulletThe multiplication program in the text is buggy -- in fact I found two errors!  For extra credit, find these two bugs.
    bulletTo help debug TM programs I found it useful to define a version of runTM that returns each of the intermediate states and tapes as it runs -- I just return all these in a list that I can then inspect.
     
  4. Design a Turing Machine that recognizes palindromes involving only the symbols a and b.  A palindrome is a string that reads the same forwards as it does backwards.  Thus "aabbaa", "aba" and "" are all palindromes (the last being the empty string), whereas "abab" is not a palindrome.  Assume that the machine begins with its head lined up with the left-most symbol on the tape, and assume that it ends with the head position over the character "Y" if the input was a palindrome, or "N" if it wasn't.  Test your program using your Haskell TM Simulator from above.


Solutions.