Elements of the Theory of Computation

I don't think there is a definitive answer for your question because computer science is a relative new area of knowledge and “fundamental books” are still being published. If I had to say one text that is the fundamental one, I would go with a paper: “On Computable Numbers, with an Application to the Entscheidungsproblem” [1], by Alan Turing. --- But if you just started your course in Computer Science, then I will give you some “bookshelf advice" based on my experience. I had the pleasure to study all the books I am going to recommend you, and most of them I was able to read cover-to-cover during the university years. And they are also in my bookshelf for reference. The book order does not represent rank of importance. * “Introduction to the Theory of Computation”, by Michael Sipser. * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou. * Another good complement is “Introduction to Automata Theory, Languages and Computation”, by Hopcroft and Ullman. (Thanks, @reacweb, for the reminder.) * “Graph Theory”, by Reinhard Diestel.…

A few suggestions (if only we all had more time): Do ProjectEuler.net, as it provides a great mesh between algorithm design and mathematics; it might be within your expertise already, however. Look in to getting a good discrete math book or two. My circumstances led me to not use my discrete math book very much for class, so I won't give you a recommendation that I do not have. Go through Scholarpedia. They are doing cool work over there. Get some text(s) on statistical inference, especially Bayesian learning. If you have access to a good library system (say, state-wide library loan), you ought to have no problem getting most textbooks. Seeing as how you're into NLP and AI, look at concurrency and what, say, Google is doing with MapReduce and PageRank (they publish reasonably-understandable papers). In general, push yourself to read peer-reviewed journal articles on the topics of your interest.…