Hopcroft & Ullman[1] is generally widely recommended. I only just got my copy a couple of days ago, so haven't had a chance to dig in yet.

The Sipser book[2] is also generally recommended as being very good.

[1]: https://www.amazon.com/gp/product/0201441241/

[2]: https://www.amazon.com/Introduction-Theory-Computation-Micha...

I'm assuming this was the Ullman book you took a look at - https://www.amazon.com/Introduction-Automata-Languages-Compu...

If not, it's good but pretty dense. If you didn't like that, then I would recommend this one - https://www.amazon.com/Introduction-Theory-Computation-Micha...

Sipser has a lot less notation and more english explanations of the concepts. I picked it up and read most of it after graduating - it's pretty easy to follow (though if I recall, I think some of the terminology around Turing complete languages differed slightly from the Ullman text).

Yes, agreed! You'd think most of the CS people in a room listening to a Lamport lecture, of all things, would've at some point in their education taken a theory of computation or similar course. The notation Lamport was asking about is already taught by page 7 of chapter 0 in Sipser [1].

[1. https://www.amazon.com/Introduction-Theory-Computation-Micha...]

Sipser's undergraduate textbook on the theory of computation[1] has a single, very nice, introductory chapter on the topic.

If you want to get technical and deep, you probably want [2] (An introduction to Kolmogorov complexity and its applications). It's pretty hard, though. Not for the faint of heart.

[1] http://www.amazon.com/Introduction-Theory-Computation-Michae...

[2] http://www.amazon.com/Introduction-Kolmogorov-Complexity-App...

Unfortunately, not much. I was pondering that after my post. It's been a long time since I was a math student, and professionally it's had zero to do with my career. A lot of books ended up boxed up at my parents' home as I moved around a number of times right after college. I'll check my own home tonight to see what I still have, but my shelves these days are mostly filled with fiction, programming, RPG, and history books.

EDIT:

Off the top of my head, for CS:

Introduction to Algorithms: https://mitpress.mit.edu/books/introduction-algorithms

Introduction to the Theory of Computation: http://www.amazon.com/Introduction-Theory-Computation-Michae...

Math:

Calculus Made Easy: http://www.amazon.com/gp/product/0312185480?ref_=cm_lmf_tit_... - I'm really not sure how good this one is for a beginner, I picked it up while assisting my sister in refreshing her calculus skills for grad school (Aerospace Engineering)

I can't remember the algebra and geometry textbooks (my dad's or my grandfather's) that I used, in addition to the assigned text, in high school.

Anything by Knuth. Seriously, one summer a professor and I just picked up copies of Concrete Mathematics and worked through large portions of it for fun. Technically I got some math credits for it, but it was really just because we wanted to. Actually, this one helped me a lot with understanding calculus. Somehow, up to that point while I knew calculus, may brain had never made the connection that integration was summation until I saw the discrete counterpart to continuous integration. I had a mechanical understanding, but no deep understanding until that moment.

What do you want to learn? Programming or CS? CS is more than just programming, and CS theory is more than just Algorithms & Data Structures.

If you want to learn about Algorithms and Data Structures and you have a strong math background, then CLRS is the book to get: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...

An undergraduate CS curriculum will mostly cover the parts I-VI of the book (that's around 768 pages) plus a few chapters from the "Selected Topics Chapter" (we covered Linear Programming and String Matching). Mind you, this book is very theoretical, and all algorithms are given in pseudocode, so if you don't know any programming language, you might have to go with a an algorithms textbook that is more practical. In my DS course we had to implement a Red-Black tree and a binomial heap in Java, and in my Algorithms course we only wrote pseudocode.

Maybe Sedgewick's (Knuth was his PhD advisor!) "Algorithms (4th ed)" will be a better choice for a beginner, as it shows you algorithm implementations in Java: http://www.amazon.com/Algorithms-4th-Edition-Robert-Sedgewic... (If you decide to go this route, you might as well take his two Algorithms courses on Coursera, they will really help).

There are also a bunch of Python-based introductions to computer science which have a broader focus than just teaching specific data structures and algorithms. Some of them emphasize proper program design, debugging and problem solving. I haven't read any of them, so I can't vouch for them, but here are a few of the more popular ones:

* http://www.amazon.com/Introduction-Computation-Programming-U...

This book was written to go along with John's edX course: https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-co...

* http://www.amazon.com/Python-Programming-Introduction-Comput...

Oh and btw, there's also the Theory of Computation, which is a major part of CS theory. Here are a few MOOCs and recommended books on the subject:

MOOCS:

* https://www.coursera.org/course/automata

* https://www.udacity.com/course/cs313

Books:

* http://www.amazon.com/Introduction-Theory-Computation-Michae...

Sipser's book is probably the best introduction to the theory of computation, and I believe its last chapter deals with Complexity theory as well.

* http://www.amazon.com/The-Nature-Computation-Cristopher-Moor...

I loved this book very much. It has a very informal and conversational style (don't let it fool you, the problem sets can be HARD).

* http://www.amazon.com/Computational-Complexity-A-Modern-Appr...

Once you are familiar with some computation models, its time to study computational complexity and this is one of the best books on the subjects. It is used both for graduate and undergraduate courses.

Fraleigh's abstract algebra text [1]. Sipser's Introduction to the Theory of Computation [2] is also excellent, and possibly of special interest to HN.

[1] http://www.amazon.com/First-Course-Abstract-Algebra-Edition/...

[2] http://www.amazon.com/Introduction-Theory-Computation-Michae...

If you're OK learning on your own, you might try buying a book before committing to the cost of tuition, also. If you really mean "theoretical CS" I don't think you can go wrong with Sipser. The latest edition[1] is expensive, but a used copy of the second edition [2] isn't TOO bad, considering the cost of another few years of education.

[1] http://www.amazon.com/Introduction-Theory-Computation-Michae...

[2] http://www.amazon.com/Introduction-Theory-Computation-Michae...

If someone asked for my recommendations for reading on state machines I would point them to Michael Sipser's Introduction to Theory of Computation.

http://www.amazon.com/Introduction-Theory-Computation-Michae...

Though I get the impression you're looking for something a bit more like an oreilly cookbook or nutshell book.

This book is a good start http://www.amazon.com/Introduction-Theory-Computation-Michae...

Try to work with books which have exercises - such as "Structure and Interpretation of Computer Programs" (http://mitpress.mit.edu/sicp/full-text/book/book.html), "Introduction to Theory of Computation" (http://www.amazon.com/Introduction-Theory-Computation-Michae...) or "How To Design Programs" (http://www.htdp.org/).

Keyword here is _work_.