As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. I

As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory. Sipser also has corresponding lectures that are available for free on YouTube here: https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzpXIFFbyGrWkqXXVj0BztDcTF https://www.youtube.com/watch?v=9syvZr-9xwk&list=PLidiQIHRzp....