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

(b) State and prove Rice's theorem.

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

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

(d) Show there exists some $m \in \mathbb{N}_{0}$ such that $W_{m}$ has exactly $m^{2}$ elements.

(e) Given $n \in \mathbb{N}_{0}$, is it possible to compute whether or not the number of elements of $W_{n}$ is a (finite) perfect square? Justify your answer.

[In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers. Any use of Church's thesis in your answers should be explicitly stated.]