What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$? Note: I have not studied theoretical computer science, so this may be a trivial question.

I am interested in the general question: what restrictions are put on a machine $m$ (boolean circuit, TM, ...), by the assumption that $m$ solves a certain problem or class of problems? The question I'm asking in this post is: What field of theoretical CS should I read up on for this?

For example:


Can all problems be solved by a lookup table? Or does assuming that $m$ solves problem $X$ tell us that $m$ has to do particular types of computations?
If we have a boolean circuit $C$ that computes problem $f$, can we then always construct a boolean circuit $\tilde C$ that also computes $f$ but has only a depth of 2 layers (or something like this).


What should I look in to to get an insight in questions like this? (I'm not asking for answers to these specific two questions).
The computational power of machines / automata / programming languages and similar computational models, is usually studied in these theoretical fields:


Computability (for what can be computed at all)
Complexity (for what can be computed efficiently)
Formal languages (several kinds of automata exist, with different expressiveness)


You will find many textbooks about these topics, as well as university courses (some video lectures could even be available on the 'net)