I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P?
Would I have to come up with an algorithm that runs in deterministic polynomial time?
Turing recognizable languages are not (generally) in P, as the time hierarchy theorem implies. To show that a class $L_1$ is contained in a class $L_2$, you need to show that every language in $L_1$ belongs to $L_2$. For example, to show that $L$ (logspace) is contained in $P$ (polytime), you argue as follows: every language in $L$ is decided by some machine running in logarithmic space; this machine must run in polynomial time; so the language is in $P$. In this example, the same machine was used, but this is not necessary. For example, Savitch's theorem shows that $\mathrm{NSPACE}(s(n)) \subseteq \mathrm{DSPACE}(s(n)^2)$, and here the same machine cannot be used (since a non-deterministic Turing machine is not necessarily deterministic).
