Introduction to the Theory of Computation

Category: Computer Science
Author: Michael Sipser
This Year Hacker News 2
This Month Reddit 4


by mindcrime   2021-11-25
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.


by ArthurAutomaton   2019-11-17

It's Problem 7.29 in the third edition of Michael Sipser's Introduction to the Theory of Computation (you can find it by searching for "coloring" when using the preview function on Amazon). It's also in The design and analysis of computer algorithms by Aho, Hopcroft and Ullman as Theorem 10.12, though the proof there seems a little different from what you've sketched. (I hope that the Google Books link works. Sometimes it won't show the right preview.)

by cbarrick   2019-11-17

Sipser's Introduction to the Theory of Computation is the standard textbook. The book is fairly small and quite well written, though it can be pretty dense at times. (Sipser is Dean of Science at MIT.)

You may need an introduction to discrete math before you get started. In my udergrad, I used Rosen's Discrete Mathematics and Its Applications. That book is very comprehensive, but that also means it's quite big.

Rosen is a great reference, while Sipser is more focused.

by jhanschoo   2019-08-24

Google hasn't been helpful because no such algorithm exists. Check out Rice's Theorem for the impossibility.


Let S be the set of languages that you can reduce SAT to in polynomial time.

SAT is clearly in S, and we know some machine recognizes it.

The empty language is not in S (even if P=NP, so that SAT is P-complete), and we know some machine recognizes it.

By Rice's Theorem, no machine decides, when given a machine as input, whether that machine recognizes a language in S.

(we assume that the "any custom problem" input is as a machine encoding)


I see that you make a lot of questions about computational complexity, but do not have a good foundation. Many things you propose or ask already have known impossibility results. May I suggest you have a look at Sipser ( That will give you a better understanding of computability and complexity to understand the feedback you're getting.

by ice109   2019-08-24

this is the canonical undergrad book

by mlevental   2019-08-21
>Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation

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

by formalsystem   2019-08-21
There's so much more to CS theory than big O notation and you're in for a treat if you check out any of the below - happy to share more if people are interested.





by mwerty   2019-08-21
Mike Sipser's book:
by sixstringtheory   2019-08-15
For anyone who'd want to know more, this is the textbook I used in a CS theory class where I first learned about the Chomsky connection: Introduction to the Theory of Computation by Michael Sipser (

(Edit: added the title and author name in my post)

by gt565k   2017-09-21
Intro to theory of computation by Sipser is good.

by trishankkarthik   2017-09-13
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.