The theory of computation asks what can be computed at all, and how much it costs when it can. Those are two different questions, and the books that answer them assume you have met the first before the second. Automata and formal languages come first because they give you the machines; computability tells you their limits; complexity measures the price of the answers you can get.
This is a subject where order is not a preference but a prerequisite chain. A reduction argument in complexity theory only lands if you already trust that the halting problem is undecidable, and that trust is built one careful proof at a time. Read in sequence and each result feels inevitable; skip ahead and you are memorizing symbols.
Start with the foundations
Introduction to the Theory of Computation by Michael Sipser is the standard first book for good reason: it walks from finite automata to Turing machines to NP-completeness with proofs you can actually follow, and its exercises are calibrated for a first pass. Read it cover to cover before anything else.
For a second angle on the same ground, Introduction to automata theory, languages, and computation by Hopcroft and company is denser and more formal, and it rewards a reader who wants the automata and grammar material pinned down precisely.
Move into complexity
Once the machines are second nature, Computational complexity by Sanjeev Arora and Boaz Barak is the modern graduate text, covering everything from the classic classes to interactive proofs and PCPs. Pair its early chapters with Computers and intractability by Michael Garey and David Johnson, the enduring field guide to NP-completeness and the art of proving a problem hard.
The older Computational complexity by Christos Papadimitriou is worth reading alongside for its logician's clarity about the definitions themselves.
Go deeper: randomness, approximation, and the big picture
When exact and efficient is impossible, you relax one constraint. Randomized algorithms by Motwani and Raghavan shows what tossing coins buys you, and Approximation algorithms by Vijay Vazirani shows how to settle for provably-close answers. Both assume the complexity vocabulary the earlier books gave you.
Close with Mathematics and Computation by Avi Wigderson, a sweeping account of how computation reshaped mathematics itself, best read once the technical scaffolding is already in place.
Work these in order and the field stops being a pile of theorems and becomes a single argument. Follow the full path to keep the sequence honest.
