Elements of the Theory of Computation

Name: Elements of the Theory of Computation
ISBN: 9780132734172

by Lewis, Harry R., and Christos H. Papadimitriou · first published 1981

7mentions

5recommended by

6HN commenters

2007–2019first – last mentioned

83% recommend17% neutral

Why HN recommends it

A rigorous, formal treatment of automata, formal languages, computability and complexity; a standard theory text for students and engineers who want the fundamentals of what computers can and cannot do.

Summarised by Claude from recommending comments

Computer Science

BuyBookshop.org Amazon

Affiliate links. As an Amazon Associate I earn from qualifying purchases.

View on Open Library ISBN 9780132734172

Mentions per year

What Hacker News says

guiraldelli · Oct 21, 2019 · Recommends

…And they are also in my bookshelf for reference. The book order does not represent rank of importance. * “Introduction to the Theory of Computation”, by Michael Sipser. * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou. * Another good complement is “Introduction to Automata Theory, Languages and Computation”, by Hopcroft and Ullman. (Thanks, @reacweb, for the reminder.) * “Graph Theory”,…
on “Ask HN: What are the most fundamental books on computer science?” ↗
Autre · Aug 22, 2007 · Recommends

…UNIX Programming Environment Kernighan & Pike, The Practice Of Programming (Really, anything written by Kernighan is pure joy, even a man page) Jon Bentley, Programming Pearls Papadimitriou &Lewis, Elements of the theory of computation
on “News.YC Library” ↗
rw · May 15, 2009 · Recommends

…(Parberry, Gasarch): A slim volume containing ~700 exercises on proving various properties of algorithms. And it teaches you most of what is needed. Download it from: http://www.eng.unt.edu/ian/books/free/ "Elements of the Theory of Computation" (Papadimitriou): Classic text. Sure you've heard of Turing machines before, but what do you know about mu-recursive functions? It's very beautiful and if you have a person with whom to read the book…
on “Ask HN: After SICP, what next?” ↗
rw · Jun 19, 2009 · Recommends

…(Parberry, Gasarch): A slim volume containing ~700 exercises on proving various properties of algorithms. And it teaches you most of what is needed. Download it from: http://www.eng.unt.edu/ian/books/free/ "Elements of the Theory of Computation" (Papadimitriou): Classic text. Sure you've heard of Turing machines before, but what do you know about mu-recursive functions? It's very beautiful and if you have a person with whom to read the book…
on “Ask HN: good math books” ↗
nandemo · Dec 23, 2011 · Recommends

Yes. I also like Papadimitriou's textbooks: Elements of the Theory of Computation and Computational Complexity.
on “Technical Papers Every Programmer Should Read (At Least Twice)” ↗
Turing_Machine · Feb 10, 2018 · Recommends

…is to understand computers at the most fundamental level, you might as well study the theory of computation rather than learning the quirks of a particular machine's instruction set. Recommended book: Elements of the Theory of Computation, Lewis and Papadimitriou (spendy). 4) The Javascript/HTML/CSS hodgepodge. Not anyone's choice for the greatest language ecosystem in the world, but probably the most employable one. Recommended book:…
on “Ask HN: How would you relearn programming?” ↗
dahart · Nov 9, 2015 · Mentions

…having to remember quotient digits, and nothing more. I'm curious where the DFA for divisibility by 7 might have originally come from, but I'm pretty sure it was a homework problem in the text I used, "Elements of the theory of Computation" by Lewis and Papdimitriou, Prentice Hall, 1981.
on “Divisibility by 7 is a Walk on a Graph (2009)” ↗