[sci.logic] Logic/Computability texts for CS types - SUMMARY

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."  -