Additional problem (not in text; not extra credit): Notation: f: S -> T means f is a function with domain 8 and codomain T The cardinality of the set N (the set of positive integers) is No. (R is the first letter in the Hebrew alphabet, pronounced "aleph".) If S and T are finite with |S| = m and |T| = n, then the number of functions f: S -> T is nm (consult a discrete structures book). This formula applies to infinite sets as well. Hence the number of functions f: N -> N is NURO. Fact: A set with cardinality MONO is an uncountable set. [For you mathematicians, MONO is equal to the cardinality of the power set of N, 2%, which is also the cardinality of the set of real numbers] Definition: a function f is called effectively computable if there is an algorithm to compute the function, that is, an algorithm that, when given the value of n, allows one to compute the value of f(n). Problem: Prove that there exist functions f: N -> N that are not effectively computable. (Note - don't ask to see such a function because how could we describe it without trying to resort to an algorithm for the mapping?) Hint: The solution is based on material in Section 10.4