CPSC 411
Fall 2008

General Instructions:
  1. The numbers refer to the textbook. Don't get confused between Exercises, at the end of each section, and Problems, at the end of each chapter.

  2. Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length. If your handwriting is deemed too illegible, you may be asked to type your homeworks.

  3. Don't forget to acknowledge all sources of assistance. Unless otherwise instructed, you must write up your homework on your own. Turn in your homework together with this cover sheet.

  4. Homework is always due at the beginning of class.

[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7] [Homework 8]

Homework 8: Due Tuesday, Dec 2, 2:20 PM

  1. Explain in your own words what the Church-Turing thesis says and why it is significant.

  2. Consider the language L that consists of encodings of all programs P such that P accepts input 0. Show using a reduction from H (the halting set) that L is undecidable. (Do not use Rice's theorem.) You will get generous partial credit for setting up the problem correctly and explaining what you have to do.

  3. State Rice's theorem and explain its significance.

  4. Use Rice's theorem to prove that language L from problem 2 is undecidable.

Homework 7: Due Tuesday, Nov 18, 2:20 PM

Homework 6: Due Tuesday, Nov 11, 2:20 PM

Homework 5: Due Tuesday, Nov 4, 2:20 PM

Homework 4: Due Thursday, Oct 23, 2:20 PM

Homework 3: Due Thursday, Oct 9, 2:20 PM

Homework 2: Due Tuesday, Sep 23, 2:20 PM

Homework 1: Due Thursday, Sep 4, 2:20 PM