CSC 363 Winter 2007 — Assignment 2

Due: 2pm on February 21st. See course webpage for up-to-date information on due date.
Worth: 10% of your course grade.

  1. [20 marks]

    This is problem 3.18 in the textbook. Show that a language is decidable iff some enumerator enumerates it in lexicographical order.

  2. [20 marks]

    The power set P(S) of a set S is the set consisting of all subsets of S. For example, the empty set ∅, {1}, {2,5,8}, the set of even natural numers, 2N, and the set of natural numbers, N, are all elements of P(N), the power set of natural numbers.

    Is P(N) countable? Prove your claim.

  3. [20 marks]

    Let WBTM be the language of all ⟨M⟩ such that M is a TM and there exists some input string w such that M when run on input w writes a blank symbol to the tape. Clarification: we say that the machine writes a blank if it reaches a transition δ(q,a)=(q′,b,D) where the b is the blank character, regardless of whether a is blank or not.

    For both languages WBTM and its complement WBTMc, classify them as either decidable, or undecidable but recognizable, or not recognizable. Prove your claims.

  4. [20 marks]

    Let PLFINTM be the language of all ⟨M⟩ such that M is a TM that accepts finitely many strings of prime length. In other words, M has the property that the set { w : M accepts w and |w| is a prime number } is finite.

    Is PLFINTM recognizable? Is it decidable? Prove your claim.