Introduction to the Theory of Computation

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


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.