CS385, Fall 2010
Theory of Computation
Problem Set 10 (due Dec. 7)

This page is located at http://www.cs.bc.edu/~alvarez/Theory/PS10/

  1. Suppose that M is a Turing machine that recognizes language L, and that M' is a Turing machine that recognizes language L'. The languages L and L' are not necessarily related to each other in any way, except that they have the same alphabet. Consider the following algorithm: 
    A = on input w:
	feed w to M
	if M accepts w
		feed w to M'
		if M' accepts w
			accept w
		else reject w
		end if
	else
		reject w
	end if

    a) In terms of L and L', what language is recognized by A? Explain.

    b) Is A a decision procedure (decider)? Explain.

  2. Is the concatenation of two decidable languages also decidable? (Refer to our earlier discussion of regular languages for a definition of the concatenation of two languages.) State your answer clearly, and give a convincing explanation. If you answer "yes", specify, in detail, a general decision procedure for the concatenation of two decidable languages. If you answer no, carefully describe a specific example of two decidable languages for which the concatenation is not decidable.

  3. (Solve but do not submit)

    Suppose that L is a Turing-enumerable language and that its complement L' is also Turing-enumerable.

    a) Give a detailed high-level pseudocode description of a decider Turing machine D that recognizes L. Your description should state what steps D goes through in order to carry out its computation on a generic input string w. The operation of your machine should be based directly on the use of enumerator machines for L and L', without relying on the fact (proven in class) that a language is Turing-recognizable if and only if it is Turing-enumerable.

    b) Provide explanations for each of the following based on your design from part a):

    1. Why the machine you described is a decider

      and

    2. Why your machine recognizes L.

  4. Regular languages and context-free languages satisfy appropriate pumping lemmas. We consider here a correspondingly more complex version for decidable languages.

    Decidable Pumping Lemma (DPL)

    Let L be a decidable language. There exists a finite integer p, called a pumping length of L, such that if w is any string that belongs to L that has length p or greater, then w may be expressed as a concatenation of the form w = rquvxyz so that the following conditions hold:

    1. |quvxy| ≤ p.
    2. qvy is nonempty.
    3. for every non-negative integer i, the pumped string rqiuvixyiz belongs to L.
    Is the above DPL correct, that is, do all decidable languages have the property stated in the DPL? Answer either yes or no, and provide a convincing justification for your answer. If you answer yes, give a general, complete, argument that shows that the property stated in the DPL holds for all decidable languages. If you answer no, give a specific example, with detailed explanations, of a decidable language for which the stated property does not hold.

  5. Read my notes on diagonalization on the web and do the exercise stated at the end of the notes, namely, use diagonalization to prove that the number of binary sequences of length n is strictly greater than n, for every positive integer n.

  6. (Solve but do not submit) The Turing machine finiteness problem (TMFP) consists of determining, given a Turing machine M, whether the language recognized by M is finite or not. Show that the TMFP is undecidable. Hint: assume that D is a decider for TMFP, and construct from D a decider for the Turing machine acceptance problem that was discussed in class.