It sounds like what you're talking about is the very basics of recursion theory, particularly the Turing degrees and even more specifically the degree 0' that contains the complete set K (defined as the set of all $e$ such that $e \in W_{e}$ using some standard enumeration $W_{e}$ of the recursive sets). While it doesn't really provide a good jumping-off point for the rest of the field, Smullyan's book Recursion Theory for Metamathematics is a good book with a solid elementary approach to the subject and might make interesting reading if you can track down a copy.
And to confirm your intuition, there's quite a bit of overlap between recursion theory and complexity theory; there's a recursion-theoretic hierarchy that's an exact analog to the polynomial hierarchy (with the important distinction that it's explicitly known not to collapse) and the two subjects share a lot of common concepts (e.g., oracles). I'm actually a bit surprised that there isn't more work 'reflecting' from recursion theory down to complexity theory, but my (novice's) understanding is that there are a number of complications in the approach (obviously I suppose, since the reflection of the easy result $0 \ne 0'$ is the $P \ne NP$ claim...)
