 |
|
| COMPUTABILITY, COMPLEXITY, LOGIC
| |
| | |
|
|
 Buy online with a credit card in the Elsevier Science & Technology Bookstore:  http://books.elsevier.com/elsevier/?isbn=0444874062
By
E. Börger
Included in series
Studies in Logic and the Foundations of Mathematics, 128
Description
The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning,
facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described
questions and problems.
The book is a unified introduction to the modern theory of these concepts, to the way in which they developed
first in mathematical logic and computability theory and later in automata theory, and to the theory of formal languages and complexity
theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give
priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge
of computer science and particularly of complexity theory.
It is both a textbook for introductory courses in the above-mentioned disciplines
as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit
the connections and analogies between a variety of concepts and constructions.
Contents
Elementary Theory of Computation.
The Mathematical Concept of Algorithm. Church's Thesis. Universal Programs and the Recursion
Theorem.
Complexity of Algorithmic Unsolvability. Recursively Unsolvable Problems. The Arithmetical Hierarchy and Degrees of Unsolvability.
Abstract Complexity of Computation.
Recursiveness and Complexity. Complexity Classes of Recursive Functions. Complexity Classes of Primitive
Recursive Functions. Polynomially- and Exponentially-Bounded Complexity Classes. Finite Automata. Context-Free Languages.
Elementary
Predicate Logic.
Logical Analysis of the Truth Concept. Syntax and Semantics. Completeness Theorem. Consequences of the Completeness
Theorem.
Logical Analysis of the Concept of Proof. Gentzen's Calculus LK. Cut Elimination for LK. Consequences of the Cut Elimination
Theorem.
Complexity of Logical Decision Problems. Undecidability and Reduction Classes. Incompleteness of Arithmetic. Recursive Lower
Complexity Bounds.
Bibliography. Index.
Bibliographic & ordering Information
Hardbound, xx + 592 pages, publication date: JUL-1989
ISBN-13: 978-0-444-87406-1
ISBN-10: 0-444-87406-2
Imprint: NORTH-HOLLAND
Price: Order form
GBP 111
USD 166
EUR 166
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
See also information about conditions of sale & ordering procedures, and links to our regional sales offices.
050/500
Last update: 18 Jul 2008
|
|
| |
| | |
|
|
| |
