===========================================================================
CSC 363                    Homework Assignment 2                Winter 2008
===========================================================================

Due: Mar 7 in tutorial

For each question, please write up your answer 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.

EXTRA REQUIREMENT:
For full marks, you must use mapping reductions (<=m) in all of your proofs
of undecidability or unrecognizability.  As I mentioned in class,
reductions will be a central concept in this course and you will have to be
very familiar with them later on, so you may as well start practicing now.


1.  The set {1}^* = {\epsilon,1,11,111,...} contains all strings over the
    alphabet {1}.

    (a) How many languages are there over alphabet {1}, i.e., how many
        subsets of {1}^* are there?  Prove your claim.

    (b) Prove or disprove: "All languages over alphabet {1} are decidable".


2.  State whether the following language is decidable, undecidable but
    recognizable, or unrecognizable, and prove your claim.

        PI = { w (- {3}^* : the string of digits w occurs somewhere
                            in the decimal expansion of \pi }

    For example, 3 is in PI and 33 is in PI because the decimal expansion of \pi
    starts with: 3.14159265358979323846264_33_83279...  (I've emphasized
    the string "33" by inserting underscores around it.)

    Notes/Hints:

     -  It is NOT known whether or not the decimal expansion of \pi
        contains every possible string of decimal digits!

     -  This question does NOT require you to argue about ways to compute
        the digits in the decimal expansion of \pi.

     -  Think about the following questions:  If 3^k is in PI for some k>0,
        what can you conclude about other strings?  What if 3^k is not in PI?

     -  Despite all these hints, the solution is actually quite short.


3.  State whether the following language is decidable, undecidable but
    recognizable, or unrecognizable, and prove your claim.

        ESS_TM = { <M> : M is a TM in which every state is "essential"
                         (see below) }

    A state q in a TM M is called "essential" if there are at least 3
    different input strings for which M enters state q during its
    computation.


4.  State whether the following language is decidable, undecidable but
    recognizable, or unrecognizable, and prove your claim.

        PLEN_TM = { <M> : M is a TM that accepts every input string
                          whose length is a prime number }


5.  **BONUS!**

    Let A be a recognizable language consisting of descriptions of TMs,
    A = { <M_1>, <M_2>, ... }, such that each <M_i> in A is a decider.
    Prove that there is a decidable language L such that L != L(M_i) for
    all <M_i> in A.

    Hint:  Use a form of diagonalization and consider an enumerator for A.