CSU390 04F: Homework 07

Created: Wed 12 Nov 2004
Last modified: 

Instructions

  1. I have decided to hold off on assigning another homework until Tue, Nov 16. The next assignment will be on reductions to prove undecidability, and it will be useful to see a few more examples before the assignment is given.

    If you feel confortable with the material and would like to get started, the problems given below are a subset of the assignment that will be handed out on Tuesday.

Problems

Required: None (See the instructions above.)
Points: None (See the instructions above.)

  1. Exercise 5.12

  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 M is a decider}

  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.

Switch to:

jaa@ccs.neu.edu