So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of diagonalization to get non-recursive sets / classes. So there's a lot of existence proofs.
Are there "limits" to our applications of diagonalization? In other words, is there a point at which our diagonalizations fail to carry us from one class to another?
Thanks!
If we consider the set $R_0$ of computable fonctions, you can obtain a new function by diagonalisation that will solve the halt problem of this set. Adding such a function as a atomic function (and get the closure by composition) will lead you to a new set of function $R_1$.
So basically we obtain $R_1$ from $R_0$ by adding the possibility to solve the halting problem on $R_0$. This is a called a jump.
Then from $R_1$ you can jump again, and again, and again. Once you get all $R_i$ for any $i\in\mathbb N$, you can jump again : $$R_\omega=\mbox{jump}\left(\bigcup_{i\in\mathbb N} R_i\right)$$
And go on jumping to compute $R_\alpha$ for a lots of ordinals $\alpha$. But you are stuck under $\omega_1^{CK}$ the first non computable ordinal. So by jumping, you can't define constructively any function not in $\bigcup_{i<\omega_1^{CK}} R_i$. As it is a countable union of countable sets, you only obtain a zero-measure set of all functions from $\mathbb N$ to $\mathbb N$. So most functions are unreachable using that kind of tools even if extensions exist to reach far beyond that...