December 2, 2008

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

- (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?

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

- (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?