# The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can.

First, here is an hypothesis: diagonalization is syatematically used to prove that a set is a proper subset of another set by constructing an object that exists in the latter but not in the former.

Following Peter Smith in An Introduction to Gödel's Theorems, let's call this "diagonalizing out". And, please, feel free to object to this first hypothesis if needed be.

In recursion theory, we diagonalize out at a "sub-computable level". By this, I mean that the diagonalization is used to separate two classes that are both computable, i.e. the p.r. functions and the \mu-recursive functions. On the contrary, with Turing machines, we systematically diagonalize out at a "supra-computable level", whether it is to show that there are languages that are not Turing-recognizable (using Cantor's diagonalization) or to show that there are Turing-recognizable languages that are not decidable (e.g. halting problem). I don't recall ever seeing any diagonalization having to do with two computable classes of languages.

This asymmetry surprises me. Do you have an explanation for it? Can we find the equivalent of the non p.r. diagonal function with TM theory, maybe using Linear Bounded Automata?