===========================================================================
CSC 363                    Homework Assignment 2                  Fall 2008
===========================================================================

Due: by 2pm on Wed 29 Oct
Worth: 8%

For each question, please write up detailed 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.  (a) Prove that not all functions f : \Sigma* -> \Sigma* are computable.
        (Hint:  How many total functions are there?)

    (b) Prove or disprove: there are countably many functions
        f : \Sigma* -> {0,1}.

    (c) Prove or disprove: there are countably many functions
        f : {0,1} -> \Sigma*.


2.  For each language L (_ {0,1}* below, state whether L is decidable,
    undecidable but recognizable, undecidable but co-recognizable, or
    unrecognizable and co-unrecognizable, then prove your claim.  (Recall
    that a language L is "co-recognizable" iff ~L is recognizable, and
    similarly for "co-unrecognizable".)

    *Note*:  For full marks, please use mapping reductions (<=m) for all
    your proofs of undecidability or unrecognizability.

    (a) L_1 = { <M,w> : M is a TM that never modifies the portion of the
                        tape that contains input w }

    (b) L_2 = { <M> : |L(M)| = 363 }

    (c) L_3 = { <M> : M is a decider }

    (d) L_4 = { 0x : x (- A_TM } u { 1y : y (- ~A_TM }, i.e.,
        \-/ w (- {0,1}*, w (- L_4 iff (w = 0x for some x (- A_TM or
        w = 1y for some y (- ~A_TM)


3.  (a) Prove that a language L is decidable iff there is an enumerator for
        L that prints the strings of L in lexicographic order.

    (b) Prove that every infinite recognizable language contains an
        infinite decidable subset.

    (c) Suppose that L is a language such that L <=m ~L.  What can we
        conclude about the decidability and recognizability of L?  Prove
        your claims.

    (d) Let A and B be disjoint languages over the same alphabet \Sigma
        (i.e., A n B = {}).  A language C over \Sigma "separates" A and B
        if A (_ C and B (_ ~C.
        Show that if A and B are disjoint co-recognizable languages, they
        are separated by some decidable language.