mikeg@c3.c3.lanl.gov (Michael P. Gerlek) (08/09/90)
In article <MIKEG.90Aug6095554@c3.c3.lanl.gov>, I (Michael P. Gerlek) wrote: > I'm looking for reccomendations for texts for an independent study I'm > doing this fall in Logic and Computability. I'm a Computer Science > major with not-a-hack-of-a-lot-of formal mathematical training [no > flames please], so I'd like to concentrate on concepts and results > rather than proofs and lemmas. Being a CS major, though, I already > know basic propositional and predicate calculus, so I don't want to > start at the very bottom -- but on the other hand, I can't find many > good non-math sources that go beyond this.... > > Can anyone suggest some good sources for any of the following topics? > (Yes, I'm covering a wide base here, but I can afford to be > flexible... since I'm writing the syllabus :-) > > - Godel's Theorem > - Computability, Turing machines > - Church's Thesis > - Completeness & Consistency of formal languages > - Lambda Calculus > - higher-order logics > - (anything I missed?) I received many, many responses to this question, and numerous requests for a summary, so I'm posting it rather than emailing individually. I dug up many of the referenced texts, and most were what I was looking for, at least in part. For the record, I've chosen two texts as my principal sources: - Boolos and Jeffrey's "Computability and Logic" This covers all the material I had listed (plus some others, e.g. Skolem's theories) except lambda calculus. It was the most recommended text, and is currently in it's 3rd edition. It's long on theory and short on proofs. - Ruth E. Davis' "Truth, Deduction, and Computation" This is a semantic (denotaional, axiomatic, *and* operational) approach to the comparison of four formal languages: propositional and predicate calculus, elementary number theory, and lambda calculus. It's brand-new (1989), which probably explains why it received only one recommendation. To the kind person who suggested I get Boolos and Jeffrey's *3rd* edition, I lost your address summarizing this - please drop me a note and tell me what's different? I could only find the 2nd edition... Thanks very much to all who responded, especially those who suggested ideas for my syllabus. Best quote from your responses, on the subject of my chosen topic: "Such topics cannot be merely learned, they must be digested and absorbed into one's being." - Frank Silbermann <fs@rex.cs.tulane.edu> I'll keep that in mind this fall. Summary and selected, edited quotes follow. +++ Hopcroft & Ullman, "Introduction to Automata Theory, Languages, and Computation" (a.k.a. the spinning wheel book) [2 recommendations] "Lots of concepts and theorems, but tersely written. It is the definitive work on the subject, but there are many more recent texts, intended to be more ammeanable to students." "People say this is more readable than Lewis and Papadimitriou, so it might be better for teaching yourself." +++ Gurari(sp?) , (title unknown) "Gurari recently published a book that has received rave reviews. Unofrtunately, he is unequivacally the worst instructor I have ever had, and his spoken English is horrible." +++ "Computability and Logic", by George Boolos and Richard Jeffrey. [8 recommendations] "This is pretty much the standard text in the field, and is very complete. It also works from first principles, so it's all the text you need for the most part. It does not cover the Lambda calculus, though." "...written for students in philosophy and hence is more readable than books highly steeped in formalism." "...a very nice text: it is written primarily for first-year grad students in Philosophy, so it stresses concepts and results about as much as proofs. You might take a look at it (be sure to get the 3rd edition, with the green cover, not the 2nd with the brown one)." +++ Lewis and Papadimitriou, "Elements of the theory of computing" [3 recommendations] +++ Brainerd and Landwebber, "The Theory of Computation" "...one of the definitions of 'computable' was expressed in terms of a simple programming language called PL. I thought this was a nifty book - even though it was written for CS majors and I was in mathematical logic." +++ Martin Gardner and (unknown), (title unknown) "...a small book about Godel's Incompleteness Proof, written for the non-specialist." +++ Martin Davis, "The Undecidable" "An interesting anthology of papers... including a translation of Godel's incompleteness proof. This paper is only about 40 pages long (if memory serves), and once you get past the baroque notation (capital sigmas for OR, pis for AND), surprisingly readable." +++ (author unknown), "From Frege to Godel" "...a history of mathematical logic... which has many seminal papers in the area." +++ Nigel Cutland (?), "Computability: An introduction to recursive function theory" +++ J. Stoy, "Denotational Semantics" [2 recommendations] "As to Lambda Calculus, as an undergraduate I found *Denotational Semantics* a BEAUTIFUL book. The basics of Lambda Calculus are covered in the first 190pp. that are definitely worth reading. It is more semantical than proof-theoretical though, and you might look at something else if you want proofs rather than meaning. But I think there's nothing like semantics to give you an idea of what's going on." [Note: excellent book, but too heavy - If I was just doing lambda calculus, I could use this, but I want to hit computability and logic and such as well... I think Davis's book covers the same ideas but in less depth and detail. -mpg] "If you are ready to go further and tie these ideas to programming language design, I would recommend Stoy's _Denotational Semantics_." +++ Ruth E. Davis, "Truth, Deduction and Computability" "The _only_ book I'd recommend for the Lambda Calculus... After giving a good review of logic, deduction, and the relation between deduction and computation (including completeness issues), it gives the best introduction to the lambda calculus I've seen, emphasizing concepts rather thank proofs, which is what you want...Most writings treat the lambda calculus as a mere syntactic term-rewriting system, and just wave their hands about the relationship between lambda expressions and function definition. Davis' is the only text I've seen that explains this relationship properly." +++ Thomas Sudkamp, (title unknownm 1988?) "...on Formal Languages... approaches these from the standpoint of automata and languages rather than Peano's postulates embedded in first order predicate logic." +++ Haskell B. Curry, "Combinatory Logic, v. 1" (about 1960) "The math might be messy depending on your tastes." +++ Rosenbloom, "Elements of Mathematical Logic" +++ Lemmon, "Introduction to Logic" [Not sure of the exact title, but thought I'd include it here. It's the text I used for my intro logic class last semester. Covers propositonal and predicate calculus with proofs and derivations, aimed towards the philosophy (i.e. non-math) student... Touches on consistency, completeness issues.] [ M.P.Gerlek (mikeg@lanl.gov) - [ Los Alamos Nat'l Lab / Merrimack College - [ Disclaimer: Yes, Mom, I'll play nice. - [ "My other machine's a multi-threaded YMP." -