Foundations of Logic and Theory of Computation
- ISBN-10
- 1904987885
- ISBN-13
- 9781904987888
- Category
- Computational complexity
- Language
- English
- Published
- 2008
- Authors
- Cristina Sernadas, A. Sernadas
Description
The book provides a self-contained introduction to mathematical logic and computability theory for students of mathematics or computer science. It is organized around the failures and successes of Hilbert's programme for the formalization of Mathematics. It is widely known that the programme failed with Gödel's incompleteness theorems and related negative results about arithmetic. Unfortunately, the positive outcomes of the programme are less well known, even among mathematicians. The book covers key successes, like Gödel's proof of the completeness of first-order logic, Gentzen's proof of its consistency by purely symbolic means, and the decidability of a couple of useful theories. The book also tries to convey the message that Hilbert's programme made a significant contribution to the advent of the computer as it is nowadays understood and, thus, to the latest industrial revolution. Part I of the book addresses Hilbert's programme and computability. Part II presents first-order logic, including Gödel's completeness theorem and Gentzen's consistency theorem. Part III is focused on arithmetic, representability of computable maps, Gödel's incompleteness theorems and decidability of Presburger arithmetic. Part IV provides detailed answers to selected exercises. The book can be used at late undergraduate level or early graduate level. An undergraduate course would concentrate on Parts I and II, leaving out the Gentzen calculus, and sketching the way to the 1st incompleteness theorem. A more advanced course might skip early material already known to the students and concentrate on the positive and negative results of Hilbert's programme, thus covering Gentzen's proof of consistency and Part III in full.
Get the book
Similar books
-
Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis
By Iris van Rooij, Mark Blokpoel, Johan KwisthoutCognition and Intractability is the first book to provide an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science.
-
Theory Of Automata, Formal Languages And Computation (As Per Uptu Syllabus)
By S.P.Eugene XavierConsider the toy shown in Fig. 1.222. A marble is dropped at A or B. Levers x1,x2,x3 cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble ...
-
Introduction to Automata Theory, Languages, and Computation
By John E. HopcroftIntroduction to Automata Theory, Languages, and Computation
-
Kolmogorov Complexity and Algorithmic Randomness
By A. Shen, V. A. Uspensky, N. VereshchaginLooking at a sequence of zeros and ones, we often feel that it is not random, that is, it is not plausible as an outcome of fair coin tossing. Why?...
-
Classical and Quantum Computation
By Alexander Shen, Alexei Yu. Kitaev, Mikhail N. VyalyiAn introduction to a rapidly developing topic: the theory of quantum computing. Following the basics of classical theory of computation, the book provides an exposition of quantum computation theory.
-
Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition
By John E. Hopcroft, Jeffrey D. Ullman, Rajeev MotwaniThis new edition comes with Gradiance, an online assessment tool developed for computer science. Please note, Gradiance is no longer available with this book, as we no longer support this product.
-
Introduction to the Theory of Computation
By Michael Sipser"Intended as an upper-level undergraduate or introductory graduate text in computer science theory," this book lucidly covers the key concepts and theorems of the theory of computation.
-
Proceedings The 2008 International Conference on Computational Science and Its Applications: ICCSA 2008
By ICCSA 2008Proceedings The 2008 International Conference on Computational Science and Its Applications: ICCSA 2008
-
What Is a Complex System?
By James Ladyman, K. WiesnerA clear, concise introduction to the quickly growing field of complexity science that explains its conceptual and mathematical foundations What is a complex system?
-
Introduction to the Theory of Computation
By Michael SipserThe number one choice for today's computational theory course, this revision continues the book's well-known, approachable style with timely revisions, additional practice, and more memorable examples in key areas.