Homework Assignment 2

Due: by 6pm on Wed 5 Mar
Worth: 8%

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}* = {ε,1,11,111,...} contains all strings over the alphabet {1}.

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

    2. 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 π }

    For example, 3 ∈ PI and 33 ∈ PI because the decimal expansion of π starts with: 3.141592653589793238462643383279...

    Notes:

    • It is NOT known whether or not the decimal expansion of π 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 π.

    • Think about the following questions: If 3k ∈ PI for some k ∈ N, what can you conclude about other strings? What if 3k ∉ 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.

    ESSTM = { <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.

    PLENTM = { <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 = { <M1>, <M2>, ... }, such that each <Mi> ∈ A is a decider. Prove that there is a decidable language L such that L ≠ L(Mi) for all <Mi> ∈ A.

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