Well, I (for one) like reading/learning stuff just for the heck of it, but I agree: for the purpose of recommending something, it is valuable to know where your curiosity comes from… do you (Joanna) want to jump into technical work about recursion theory and the lambda calculus or want an overview of what computational theory in mathematics/CS is (Turing Machines and such)? (I would love to recommend my teacher Ann Yasuhara’s book, but I don’t see it in print any longer :-(). Or perhaps you might find more interesting the highlights of the field, culminating in that much abused beast: Gödel’s Incompleteness Theorem(s)? (Nagel and Newman’s book does a decent job of that; but for a more idiosyncratic approach, see the first few chapters of Penrose’s Emperor’s New Mind).
Some more suggestions to add to Tayssir’s:
Computability and Unsolvability — Martin Davis (Davis needs no introduction, take my word for it :-))
This one’s pretty decent, if you skip the technical parts: http://www.diku.dk/hjemmesider/ansatte/neil/comp2book2007/book-whole.pdf
Stephen Simpson’s course material (technical): http://www.math.psu.edu/simpson/courses/math558/fom.pdf
If you want to get knee deep into the importance of Chomsky’s work for the Theory of Computation see Section 1.2, others, in this fairly technical book: http://www.cse.ohio-state.edu/~gurari/tpf/zip-bk/pic/theory-bk.zip
My old boss Al Aho’s semi-bible also has some sections of interest: http://infolab.stanford.edu/~ullman/focs.html
I also found these interesting bit of notes: http://infolab.stanford.edu/~ullman/fcsc-notes.html If you decide to read it: you can safely skip chapters 3 (unless you like Complexity Theory), 4, 5, 6, 8, 9, 13. Read chapter 10 for Automata Theory (if interested). Read chapter 11 (skip note 3) for Grammars.
A little farther afield:
Chaitin is always a fun if controversial read: http://www.umcs.maine.edu/~chaitin/unknowable/ch1.html (on FoM, Gödel’s results, Turing machines, etc)
Pretty good coverage of basic ideas of Logic in particular terms and methods: http://www.cl.cam.ac.uk/teaching/2002/LogicProof/notes.pdf
—ravi