For the first two questions, I recommend Sipser’s Introduction To The Theory Of Computation. It goes through the mathematical basis underlying computation and is the relevant introductory textbook for those questions. To answer your questions about computation and physics, I would suggest studying computation complexity. That topic is usually covered in the opening chapters of an algorithms textbook. Cormen, Leicerson, Rivest and Stein’s Introduction to Algorithms is the standard book for that, but I’d actually recommend Skiena’s Algorithm Design Manual as a more readable introduction to the topic. For more on the relation between physics and computation, I’d also recommend looking into information theory, starting with Claude Shannon’s original paper, which is remarkably readable and still relevant, even 74 years later.
For the first two questions, I recommend Sipser’s Introduction To The Theory Of Computation. It goes through the mathematical basis underlying computation and is the relevant introductory textbook for those questions. To answer your questions about computation and physics, I would suggest studying computation complexity. That topic is usually covered in the opening chapters of an algorithms textbook. Cormen, Leicerson, Rivest and Stein’s Introduction to Algorithms is the standard book for that, but I’d actually recommend Skiena’s Algorithm Design Manual as a more readable introduction to the topic. For more on the relation between physics and computation, I’d also recommend looking into information theory, starting with Claude Shannon’s original paper, which is remarkably readable and still relevant, even 74 years later.