(a) State the $s-m-n$ theorem, the recursion theorem, and Rice's theorem.

(b) Show that if $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ is partial recursive, then there is some $e \in \mathbb{N}$ such that

$$f_{e, 1}(y)=g(e, y) \quad \forall y \in \mathbb{N}$$

(c) By considering the partial function $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ given by

$$g(x, y)= \begin{cases}0 & \text { if } y<x \\ \uparrow & \text { otherwise }\end{cases}$$

show there exists some $m \in \mathbb{N}$ such that $W_{m}$ has exactly $m$ elements.

(d) Given $n \in \mathbb{N}$, is it possible to compute whether or not $W_{n}$ has exactly 9 elements? Justify your answer.

[Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]