===========================================================================
CSC 363                     Homework Exercise 2                 Winter 2008
===========================================================================

Due: by 6pm on Wed 23 Jan
Worth: 1.5%

For each question, please write up your answers carefully: make sure that
you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  For any alphabet \Sigma, say that a function f : \Sigma* -> \Sigma*
    is "computable" if there exists a TM M such that for all strings
    w (- \Sigma*, M accepts w with final configuration q_A f(w), where q_A
    is the accepting state of M.  In other words, when M is started with w
    on its tape, it eventually enters its accepting state with only f(w) on
    the tape and its head on the leftmost symbol of f(w).

    Prove that a function f is computable (as defined above) iff the
    language L_f = { w#f(w) : w (- \Sigma* } is decidable (where
    # !(- \Sigma).
    Give implementation-level descriptions in your proofs.

Notes:

 -  There is only one question for this exercise, because it is a little
    trickier than the typical level of difficulty for exercises.

 -  This is an "if and only if": don't forget to prove both directions!

 -  You are likely to find it helpful to write down a clear and precise
    definition of what it means for L_f to be decidable.

 -  For one direction, note that the assumption that L_f is decidable (with
    decider M_L) does *not* mean that M must somehow compute f.  It is your
    responsibility to describe explicitly a TM that computes f (by making
    judicious use of M_L).

    *Hint:* You may make use of the fact that it is possible for a TM to
    iterate on all of the strings over alphabet \Sigma.