lewis@endor.uucp (Harry Lewis) (01/15/91)
RE: Lewis and Papadimitriou, ELEMENTS OF THE THEORY OF COMPUTATION Christos Papadimitriou and Harry Lewis are in the process of revising their text on the theory of computation and would like the advice of the theory community on changes, deletions, and additions it would like to see made. What are your pet peeves? [Mine is the use of funny terms for the classes that everyone else calls the recursive and r.e. sets.] What results do you always teach but have to do from notes because L&P does not include them? [My favorite example is Rice's Theorem.] What Theorems do you consider to be misstated, and what proofs would you like to see done differently? [One of my votes goes for the proof that the languages accepted by finite automata are regular, which can be done much more cleanly via automata with regular expressions on the transitions.] What computational ideas ought to be introduced that are not, or ought to be omitted that are currently included? [Probabilism, Parallelism, Alternation, ...?] Anything else? [Don't be shy about asking for a solution manual --- after all this time we suspect it might be useful!] Please respond to lewis@das.harvard.edu and/or christos@cs.ucsd.edu. We can't promise to make all the changes that everyone wants, but we would like to create a new edition that meets the expectations of the many teachers who have used the book in the past. Many thanks for your help!