CSU390 08F: Homework 07

Created: Wed 12 Nov 2008
Last modified: 

Assigned: Wed 12 Nov 2008
Due: Wed 19 Nov 2008

General Instructions

  1. Please review the grading policy outlined in the course information page.

  2. On the first page of each part of your solution write-up, you must make explicit which problems are to be graded for "regular credit", which problems are to be graded for "extra credit", and which problems you did not attempt. Please use a table something like the following

    Problem01020304 0506070809...
    CreditRCRCRCECRC RCNARCRC...

    where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.

  3. You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.

Specific Instructions

Note: It is quite possible to solve the questions on this assignment in many correct ways. In particular, one can reduce from many undecidable problems to show that any of the languages given below are undecidable; however, choosing the "wrong" reduction will result in a complicated solution.

In the hints that follow, I will describe particularly simple reductions that result in simle solutions. Your solutions need not follow these hints; many correct solutions reducing from different languages exist.

Each hint below corresponds to a matching problem (Hint 1 for Problem 1; Hint 2 for Problem 2, etc.)

  1. Reduce from ATM. Your reduction will be similar to the reduction we used to show that REGTM was undecidable: M' will filter its inputs and take one action if the input string is "000" and another if the input string is not.

  2. Again, reduce from ATM. Note that |L(M)| >= 2 means that the size of the language accepted by M must be at least two; i.e., M accepts at least two strings. In your reduction, have M' always accept one string (pick your favorite), and let it accept a second (or more)strings if and only if M accepts w.

  3. Reduce from ATM. Your reduction will be similar to the reduction we used to show that REGTM was undecidable: M' will filter its inputs and take one action if the input string is of the form 0*1* and another if the input string is not. You may need to "flip" the output bit...

  4. Reduce from EINTTM. Think about how you should set k and whether you should flip the output bit or not. This is perhaps the easiest problem on this assignment.

  5. Again, reduce from ATM. M' should accept some particular string which is not its own reverse (pick your favorite), and it should accept all other strings if and only if M accepts w. Think about the consequences of such a reduction.

  6. This problem is not a reduction in our usual sense. What you need to think about is this: How could you solve ETM using a subroutine which minimizes Turing Machines? If you could do that, then such a subroutine can't exist... So, you have to build a program which solves ETM from the subroutine which minimizes TMs. ETM questions are of the form, "Here's a TM, does it accept the empty language, i.e., no strings?" Suppose I give you a TM which accepts no stings, and you minimize it; what will it look like? Suppose I give you a TM which accepts some strings and you minimize it; what will it look like? Can you tell the difference? If so, you can solve ETM using the subroutine in question...

    Describe carefully how you would solve ETM using the subroutine in question, and that in and of itself will demonstrate that the subroutine cannot exist.

Problems

Required: 4 of the following 6 problems
Points: 25 pts per problem

  1. Prove that the following language is undecidable.

    L = {<M> | M is a Turing machine, and M accepts the string "000"}

  2. Prove that the following language is undecidable.

    L = {<M> | M is a Turing machine and |L(M)| >= 2}

  3. Prove that the following language is undecidable.

    L = {<M> | M is a Turing machine, and L(M) = 0*1*}

  4. Prove that the following language is undecidable.

    L = {<M1,M2,k> | M1 and M2 are Turing machines, and |L(M1) int L(M2)| >= k}

    Here "int" is set intersection.

  5. Problem 5.9

  6. As we have mentioned in class, an algorithm for minimizing finite automata exists: Given as input a DFA D, the algorithm returns a DFA D' where L(D) = L(D') and D' contains as few states as possible.

    Show that no such procedure for minimizing Turing Machines can exist; i.e., show that a procedure which takes as input a Turing Machine and returns as output the minimum equivalent Turing Machine cannot exist.

    Hint: We have shown that ETM is undecidable. What is the smallest TM which accepts the empty language? Could you recognize such a TM if it were handed to you? Show how you could solve ETM if you had a procedure for minimizing TMs; thus, such a procedure cannot exist.

    Note: This result essentially implies that one cannot write a procedure which takes as input a program and returns as output the smallest equivalent program. Such a procedure could be extremely useful, if it existed; think about the ramifications of such a procedure for the software industry.

Switch to:

jaa@ccs.neu.edu