WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4123 Theory of Computation 
Homework 3 - B 2004

Due Date: Friday, December 3rd at 12:00 noon.
NO SUBMISSIONS WILL BE ACCEPTED AFTER 12:05 PM.
 
------------------------------------------

  1. Consider the following language:

    SUBSETTM = { <M1,M2> | M1 and M2 are Turing machines, and L(M1) is a subset of L(M2)}.

    1. (10 points) Prove that the language SUBSETTM is undecidable. In other words, prove that there is no Turing machine (i.e. algorithm) that solves the following problem:
      • Input: Two Turing machines M1 and M2
      • Output:
        • accept, If L(M1) is a subset of L(M2). That is, every word accepted by M1 is also accepted by M2.
        • reject, otherwise. That is, there is a word w in Sigma* such that w belongs to L(M1), but it doesn't belong to L(M2)

    2. (10 points) Prove that the language SUBSETTM is not semi-decidable.

    3. (10 points) Prove that the language SUBSETTM is not co-semi-decidable. That is, prove that its complement, SUBSETCTM, is not semi-decidable.

    Hint: Prove both of the following two parts:

    Explain clearly and in detail why the two parts above imply that SUBSETTM is undecidable, not semi-decidable, and not co-semi-decidable.

  2. Consider the following language:

    LOOPSTM = { <M> | M is a Turing machine and there is at least one word w in Sigma* such that M doesn't halt (i.e. it loops) when it is run on input w}.

    1. (10 points) Prove that the language LOOPSTM is undecidable. In other words, prove that there is no Turing machine (i.e. algorithm) that solves the following problem:
      • Input: A Turing machine M
      • Output:
        • accept, If there is a word w in Sigma* such that M loops (doesn't halt) on input w.
        • reject, otherwise. That is, M halts on each and every input string.

    2. (10 points) Prove that the language LOOPSTM is not semi-decidable.

    3. OPTIONAL (10 points): Is the language LOOPSTM co-semi-decidable or is it not co-semi-decidable? That is, determine whether this language's complement, LOOPSCTM, is semi-decidable or is not semi-decidable. Prove your answer.

    Hint: Prove that HALTCTM <=m LOOPSTM (or equivalently that ACTM <=m LOOPSTM). Explain in detail why this implies that LOOPSTM is undecidable and also that it is not semi-decidable.


  3. Let A and B be two languages on the same Sigma alphabet. Assume that A <=m B, that is A is mapping reducible to B.
    For each of the following pair of statements:

    Pair of statements:

      • 1.1. If A is decidable then B is decidable

      • 1.2. If B is decidable then A is decidable

      • 2.1. If A is semi-decidable then B is semi-decidable

      • 2.2. If B is semi-decidable then A is semi-decidable

      • 3.1. If A is undecidable then B is undecidable

      • 3.2. If B is undecidable then A is undecidable

      • 4.1. If A is not semi-decidable then B is not semi-decidable

      • 4.2. If B is not semi-decidable then A is not semi-decidable

Additional Problem for Students taking the course for Graduate Credit

  1. (10 points) Problem 5.22 from textbook (Rice's Theorem).

Homework Submission

Bring your homework solutions to the beginning of the class period. The HW is due on Friday, December 3rd at 12:00 noon. NO SUBMISSION WILL BE ACCEPTED AFTER 12:05 PM.