CPSC 433: Quiz 11
April 18, 2006

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."


  1. (2 pts) True or False. Suppose problem P1 reduces to problem P2 and P2 is decidable. Then P1 is decidable.

  2. (1 pt) What is the definition of a nontrivial property of the recursively enumerable languages?

  3. (2 pts) What is the statement of Rice's theorem?