Homework Assignment 2

Due: by 2pm on Web 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. Prove that not all functions f : Σ* → Σ* are computable.
      (Hint: How many total functions are there?)

    2. Prove or disprove: there are countably many functions f : Σ* → {0,1}.

    3. Prove or disprove: there are countably many functions f : {0,1} → Σ*.

  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.

    1. L1 = { <M,w> : M is a TM that never modifies the portion of the tape that contains input w }

    2. L2 = { <M> : |L(M)| = 363 }

    3. L3 = { <M> : M is a decider }

    4. L4 = { 0x : x ∈ ATM } ∪ { 1y : y ∈ ATM }, i.e., ∀ w ∈ {0,1}*, w ∈ L4 iff (w = 0x for some x ∈ ATM or w = 1y for some y ∈ ATM)

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

    2. Prove that every infinite recognizable language contains an infinite decidable subset.

    3. Suppose that L is a language such that L ≤m L. What can we conclude about the decidability and recognizability of L? Justify.

    4. Let A and B be disjoint languages over the same alphabet Σ (i.e., A ∩ B = ∅). A language C over Σ "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.