Can you give me some suggestions about a good introductory (but comprehensive) book
about Logic and Computation?
Some fuzzy topics that I have in mind are:
- Presburger artihm., PA, ZF, ZFC, HOL
- Set theory, Type theory
- Modeling Computation (Turing machines) in different theories
- Links with computational complexity (FMT, descriptive complexity)
Asked By : Vor
Answered By : Vor
I suggest one of the book I recently bought:
I had not ("still haven't" :-) a strong background on logic and this book is helping me to better understand some "fundamental" aspects of logic and its relation with computation and complexity. Doubtless a good introductory book.
The TOC and preface of the book are downloadable from the Pudlak's home page and you can also find some excerpts of the book on http://books.google.com.
From the Introduction:
... The first two chapters are an introduction to the foundations of mathematics and mathematical logic. The material is explained very informally and more detailed presentation is deferred to later chapters....
Chapter 3 is devoted to set theory, which is the most important part of the foundations of mathematics. The two main themes in this chapter are: (1) higher infinities as a source of powerful axioms, and (2) alternative axioms, such as the Axiom of Determinacy...
Proofs of impossibility, the topic of Chapter 4, are proofs that certain tasks are impossible, contrary to the original intuition. Nowadays we tend to equate impossibility with unprovability and non-computability, which is a rather narrow view. Therefore, it is worth recalling that the first important impossibility results were obtained in different contexts: geometry and algebra. The most important result presented in this chapter is the Incompleteness Theorem of Kurt Godel...
Proofs of impossibility are, clearly, important in foundations. One field in which the most basic problems are about proving impossibility is computational complexity theory, the topic of Chapter 5. But there are more connections between computational complexity and the foundations....
In fact, there is a field of research that studies connections between computational complexity and logic. It is called 'Proof Complexity' and it is presented in Chapter 6. Although we do have indications that complexity should play a relevant role in the foundations, we do not have any results proving this connection. ...
Every book about the foundations of mathematics should mention the basic philosophical approaches to the foundations of mathematics. I also do it in Chapter 7, but as I am not a philosopher, the main part of the chapter rather concentrates on mathematical results and problems that are at the border of mathematics and philosophy ...
It doesn't cover FMT and descriptive complexity, but there are a few good books that are focused on those topics (e.g. Leonid Libkin: Elements of Finite Model Theory; Texts in Theoretical Computer Science. An EATCS Series; 2004 )
I accept my answer because I hadn't the opportunity to read the book suggested by Trung Ta, yet.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24761
0 comments:
Post a Comment
Let us know your responses and feedback