My interest in the mathematical theory of computation is primarily due to the work of the brilliant logician Jean-Yves Girard on linear logic. Below is a (not very comprehensive) list of references for the parts of the theory of computation that I either know a little about, or am interested in. The books can generally be downloaded in PDF form from bookzz, but do buy a copy as well.
General “big picture” references on computation and logic:
Some references on lambda-calculus, System F and proof theory:
Some references on computational complexity theory:
Relations between computation and category theory:
Relations between computation and physics:
Some interesting videos: