One can say computational complexity is just computability theory with resource bounds but the fields feel quite different.
- Complexity theorists consider themselves part of the theoretical computer science community and find themselves mostly in CS departments. Recursion theorists consider themselves logicians and find themselves mostly in math departments.
- Complexity theorists try to understand efficient computation analogous to theoretical physicists trying to understand how the universe works, where computability theorists consider more ethereal questions of logical definability. Consider the example of quantum computing: Many complexity theorists analyze the computational power of these machines where quantum has had virtually no effect on computability theory.
- Outside of diagonalization, the tools and techniques used in the fields are completely different. Rare does one see a priority or finite injury argument in complexity, whereas algebra and combinatorics don't appear in most computability proofs.
The difference in thinking hit me during a logic seminar where the speaker asked "How do we usually show that a language is computable?" I thought find an algorithm. The speaker answered his own question "Show that the language is c.e. and co-c.e."