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."

Signature:___________________________________________

1. (1 pt) Choose the best answer: The set of all functions from the natural numbers to the natural numbers is (a) empty, (b) nonempty but finite, (c) countably infinite, (d) uncountably infinite.
   
   
   
2. (1 pt) Consider the function f that takes as input a description of a program P and an input X for P, and produces as output a 1 if P halts when executed on input X, and a 0 if P does not halt when executed on input X. Is f computable or uncomputable?
   
   
   
3. (1 pt) True or False: Suppose we know that there is a many-one reduction from problem P1 to problem P2. If P2 is undecidable, then P1 is undecidable.
   
   
   
4. (2 pts) In order to apply Rice's theorem to show that a property about programs is undecidable, what must be shown about the property?