Found in 19 comments on Hacker News
mlevental · 2019-08-18 · Original thread
>Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation

i've seen some ridiculous virtue signaling recommendations on hn before but this takes the cake. have you actually read the book? wigderson is an IAS professor (for those that don't know, einstein and godel were IAS professors) and this book is a research survey (most of the theorems have refs to papers). i've read both sipser and hopcroft ullman and i'm still pretty far away from being able to easily read it. and you're recommending this to someone that learned js from a bootcamp. you think maybe she's not the target audience?

so that i'm not labeled as just a critic: the standard formal languages book is sipser

it's colloquial and has a lot of diagrams and "intuition". people really like it but i actually think hopcruft ullman is better because it's more structured

gt565k · 2017-09-19 · Original thread
Intro to theory of computation by Sipser is good.

I conjecture that hypercomputation is impossible for the following simple reason. If you could solve the Halting Problem [1], then you could build a "living" contradiction, where a machine halts if and only if it does not halt. (See proof in [2]). It won't be a mere description of a paradox, it would be an actual one. If contradictions are possible (something we implicitly believe to be impossible), then Reality is far stranger than we ever suspected or observed.



What you're looking at is the theory of computational complexity.

Here's a short-ish overview:

For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous:, Google Books link otherwise:

mac01021 · 2016-05-18 · Original thread
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.



Jtsummers · 2015-11-19 · Original thread
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.


Off the top of my head, for CS:

Introduction to Algorithms:

Introduction to the Theory of Computation:


Calculus Made Easy: - 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.

rifung · 2015-08-20 · Original thread
This is the book that was used when I was an undergrad.

It is also used for the graduate course.

I highly recommend Sipser's "Introduction to the Theory of Computation" if you want to learn more. Here's a link to the edition I had in college (around 2002):

It's used at MIT (, the U of MN (where I used it), and—I'm sure—most other schools.

You can buy the newest edition, but you'll spend an extra $150 for not much gain.

gte910h · 2014-06-24 · Original thread
1> Do you have a "Real" CS degree?

If not, doing a good portion of the exercises in some books on [compilers](, [DFAs/State Machines](, Algorithms ( and theoretical programming ( can give you some common foundational lenses with which to see these articles

2> Learning the history of your field

Nothing informs the current state of the field more than how we got here! Learn the foundation of your field from people who lived it. The podcast [Debug]( is Guy English (Creator of Napkin and other apps) along with Rene Ritchie interviewing people about the history of Cocoa and CocoaTouch

I found [this episode about AutoLayout and Key Ferry illuminating](

3> Go through early versions. Few systems START complex. Look at OLD books for EARLY versions of systems, and why old php made such silly choices is obvious (hint, they weren't that silly for what it was doing). Read books and commentary through the timeline. Understand the history of what's happening to the language, then you'll understand why you are where you are.

4> Go DOWN the stack. Understand the bottom of Objective C by reading [the open source implementation of Core Foundation and more]( Also available elsewhere (and I think somewhere on Apple's Site still).

5> Do what you shouldn't! Don't ship it, but really use those implementation details to do something awesome and amazing. You'll learn tons about what's happening.

PS: To the mods, those aren't affiliate links

mikevm · 2013-12-06 · Original thread
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:

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: (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:


This book was written to go along with John's edX course:


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:






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.


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).


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.

picomancer · 2013-10-21 · Original thread
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.



evanb · 2013-09-07 · Original thread
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.



evanb · 2013-09-07 · Original thread
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.



Goladus · 2012-12-24 · Original thread
If someone asked for my recommendations for reading on state machines I would point them to Michael Sipser's Introduction to Theory of Computation.

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

samdk · 2011-08-24 · Original thread
There's really not a whole lot abstracted about it. It is really hard and impractical for actually accomplishing anything, but it's also pretty easy to see how it maps to a Turing machine if you know what the actual definition of a Turing machine is.

That kind of thing I learned in a class: a textbook on computational theory is probably what you want, and as far as I know there are only a couple of those. I used this one:

veyron · 2011-06-05 · Original thread
I'd recommend you start from Sipser [] or Papadimitriou [] to learn more about complexity theory (then we can discuss why your response is nonsense)
dm3 · 2010-12-14 · Original thread
Try to work with books which have exercises - such as "Structure and Interpretation of Computer Programs" (, "Introduction to Theory of Computation" ( or "How To Design Programs" (

Keyword here is _work_.

mitko · 2009-07-04 · Original thread
No it doesn't! Justify your claim. I just stated the definition of the P?=NP problem. You can find it in any good book on complexity theory. For example:

Fresh book recommendations delivered straight to your inbox every Thursday.