(i) What does it mean for a function from $\mathbb{N}^{k}$ to $\mathbb{N}$ to be recursive? Write down a function that is not recursive. You should include a proof that your example is not recursive.

(ii) What does it mean for a subset of $\mathbb{N}^{k}$ to be recursive, and what does it mean for it to be recursively enumerable? Give, with proof, an example of a set that is recursively enumerable but not recursive. Prove that a set is recursive if and only if both it and its complement are recursively enumerable. If a set is recursively enumerable, must its complement be recursively enumerable?

[You may assume the existence of any universal recursive functions or universal register machine programs that you wish.]