Additional problem $($not in text; not extra credit$)$:

Notation:

$f$:$S->T$ means $f$ is a function with domain $S$ and codomain $T$

The cardinality of the set $N($the set of positive integers$)$ is $().($ 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$

is $n^m($consult a discrete structures book$).$ This formula applies to infinite sets as

well. Hence the number of functions $f$:$N->N$ is $x_0^{}0.$

Fact: A set with cardinality $N_0^{{}_0}$ is an uncountable set. $[$For you mathematicians,

$N_0{x}_0$ is equal to the cardinality of the power set of $N,2^{N}0,$ 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\mathrm{.}4.$