For $k \geqslant 1$ give the definition of a partial recursive function $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ in terms of basic functions, composition, recursion and minimisation.

Show that the following partial functions from $\mathbb{N}$ to $\mathbb{N}$ are partial recursive: (i) $s(n)= \begin{cases}1 & n=0 \\ 0 & n \geqslant 1\end{cases}$ (ii) $r(n)= \begin{cases}1 & n \text { odd } \\ 0 & n \text { even } \text {, }\end{cases}$ (iii) $p(n)=\left\{\begin{array}{l}\text { undefined if } n \text { is odd } \\ 0 \text { if } n \text { is even }\end{array}\right.$

Which of these can be defined without using minimisation?

What is the class of functions $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ that can be defined using only basic functions and composition? [Hint: See which functions you can obtain and then show that these form a class that is closed with respect to the above.]

Show directly that every function in this class is computable.