Try Michael Sipser's excellent book "Introduction to the Theory of Computation". The automata and Turing machines are all expressed as state diagrams, with sufficient text explanation to help you interpret and implement them.
This was our course text at Uni about 4 years ago, just before the 2nd edition came out; it was a real rock, I heartily recommend it!
Definitely take a look at computational theory. A couple great books are:
I would also take a look at projecteuler.net and work out some of those problems. Avoid solving the problems using brute force... instead, look at the mathematics and try to learn common algorithms and concepts that would be discussed in a CS theory class.