Introduction to Theory of Computation [pdf] | Hacker News Reader

Introduction to Theory of Computation [pdf]

cg.scs.carleton.ca

65 pointsmindcrime18 comments

I believe Brian Cantwell Smith should be mentioned here.

    Which leads me to say something about computing. I have repeatedly
    mentioned computation as one of the intentional sciences. Some of you will
    know that for almost 30 years I have been engaged in a foundational inquiry
    into the basic nature of computing—trying to figure out what it is, where it
    came from, what its intellectual importance is, what it augers for the future. I
    have spent 30 years, the project is largely complete ... and I have failed. Or
    rather: I have succeeded, I believe, in coming up with the answer. But the
    answer is: there’s nothing there.[0]

[0]: http://www.ageofsignificance.org/people/bcsmith/papers/smith...

Very bracing read. Thanks!

I feel like if you want a good introductory theory text you need to focus less on everything up to (and including) decidability and get as quickly as you can to complexity theory. There are certainly a few central milestones, but to spend 200 pages and only get to P/NP seems like a crime. There are so many other topics to whet one's appetite for theoretical computer science!

Then again, this text appears to have been written for the kind of readers who have never written a proof before. So I expect this would fill a semester of puzzling over the minute details of the pumping lemma and various closure properties (but again, to what end?).

I disagree. Automata theory has important practical applications -- most string processing turns out to be finite automata (hence regular expressions), and push-down automata are very important to understand if you're writing a compiler.

You disagree with what? I never said anything about practical applications. And you'd better bet that complexity theory (and the world of topics that basic familiarity with complexity theory opens) has more important applications. Cryptography, combinatorial optimization, approximation algorithms, communication complexity, machine learning theory, need I go on?

All I'm saying is that automata theory doesn't give the glimpse into theoretical computer science that every "introductory theory" textbook ought to.

but again, to what end?

Not everybody is coming from the same place. I was just looking for a freely available text that covered automata stuff, so I could brush up on a few things that I ran across reading an AI book. This one caught my eye as being both very recent and licensed under a CC license, which is a sweet spot to me.

Is it the best possible book for some particular class, or for any particular student? Who's to say? But I reckon a few HN users might find this useful.

I see your point but, from my limited experience, I've found the material on decidability crucial to get a good working grasp of many of the core abstractions central to both complexity theory and theory of computation in general such as languages, non-constructive proofs, reductions, etc. I feel that without such exposure, it would be hard for a newcomer to appreciate the subtleties of the discipline...

Big fan of your math \cap programming series, by the way. Keep it up.

There are quite a few important insights along the way:

http://cstheory.stackexchange.com/questions/14811/what-is-th...

I think very few of these are actually revealed in such an introductory course, and you can gain the same insights from other topics in complexity theory (for example PSPACE = NPSPACE).

The authors are two of my favorite profs from undergrad. The curriculum at the time had some problems. This book is written for a course that helps fix some of those problems.

So yes, this is written for people who have never written a proof before-undergrads in first or second year.

From the title I thought it would be this one:

http://en.wikipedia.org/wiki/Introduction_to_the_Theory_of_C...

(It's also a good book so recommended, the part on automata is useful even for those not interested in theory, and being theory-averse myself, I didn't find it to be too dense --- although the later chapters certainly are.)

I second this. The Sipser text was one of my favorites from my university career. It's very short and covers a lot of material. There's no fluff at all, but it still manages to do a good job explaining the topics. Solid textbooks like that are very rare. It's one of only 3 books I elected to keep after the course was over (the others being an 8086 assembly language reference and an intro to computer security).

when I took this course in college, this is what helped me get through. Guy is awesome https://www.youtube.com/watch?v=HyUK5RAJg1c&list=PL601FC994B...

It makes me sad to read the introduction and see that their course has become only an elective now. I'm sure it was replaced by some trivial course about a new fad language.

More likely more electives. Because having 1/3 of the credits be non-CS and non-Math wasn't quite enough.

glares at his Carleton CS degree

I'd have assumed this was Sipser's book as well, except that I was recently at a university bookstore and saw the third edition of his book priced at over $200. Sipser's a great writer, but that's an outrageous price. When I was in school, it was still expensive at a bit over $100.

I am grateful this free alternative exists, because the subject matter is really fun.

Happy to see book released under Creative Commonns license. A quick glance made me think that book is heavily influenced by Sipsers book. Should have used custom LaTeX template for books (https://www.sharelatex.com/templates/books/)

"The course as we teach it today has been influenced by the following two textbooks: • Introduction to the Theory of Computation (second edition), by Michael Sipser, Thomson Course Technnology, Boston, 2006."

Reply on news.ycombinator.com