Classical Recursion Theory, Volume II
- ISBN-10
- 044450205X
- ISBN-13
- 9780444502056
- Category
- Mathematics / Logic
- Pages
- 949
- Language
- English
- Published
- 1999-09-07
- Publisher
- Elsevier Science
- Author
- P. Odifreddi
Description
Volume II of Classical Recursion Theory describes the universe from a local (bottom-up
or synthetical) point of view, and covers the whole spectrum, from the
recursive to the arithmetical sets.
The first half of the book provides a detailed picture of the computable
sets from the perspective of Theoretical Computer Science. Besides giving a
detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity
classes, ranging from small time and space bounds to the elementary functions,
with a particular attention to polynomial time and space computability. It also
deals with primitive recursive functions and larger classes, which are of
interest to the proof theorist.
The second half of the book starts with the classical theory of recursively
enumerable sets and degrees, which constitutes the core of Recursion or
Computability Theory. Unlike other texts, usually confined to the Turing
degrees, the book covers a variety of other strong reducibilities, studying
both their individual structures and their mutual relationships. The last
chapters extend the theory to limit sets and arithmetical sets. The volume
ends with the first textbook treatment of the enumeration degrees, which
admit a number of applications from algebra to the Lambda Calculus.
The book is a valuable source of information for anyone interested in
Complexity and Computability Theory. The student will appreciate the detailed
but informal account of a wide variety of basic topics, while the specialist
will find a wealth of material sketched in exercises and asides. A massive
bibliography of more than a thousand titles completes the treatment on the
historical side.
Get the book
Similar books
-
Differentiability of Six Operators on Nonsmooth Functions and P-Variation
By R. M. Dudley, R. NorvaišaFor a class of cases where Theorem 5.3 applies , with its somewhat unusual hypothesis on uog- , let N = { 0 , 1 ) , H = U ( 0,1 ) , let H be the distribution function of a random variable X having a strictly positive density on R and E ...
-
逻辑思维游戏大全集
By 于雷_著本__取了近千__典有趣的__思_游_，按照思_方法分_，___解了十七大___思_方法的定_、特_和_用。 ...
-
数学与逻辑
By 于雷_著.本_包含_美等西方_家_行__思_能力___常用的七_方面的___容，即___算、概念与定_判_、__判_与推理、言_理解与表_、 ...
-
Interactive Relational Database Design: A Logic Programming Implementation
By Tapan P. Bagchi, Vinay K. ChaudhriRelational databases have quickly come to be regarded as a natural and efficient way of organizing information. Duplicate data can be eliminated and powerful set-theoretic operations can be used to...
-
Fuzzy Set Theory: Foundations and Applications
By George J. Klir, Bo Yuan, Ute H. St. ClairThis book is designed to help anyone understand the basics of fuzzy sets, whether or not they have a mathematical background. The book first presents a basic grounding...
-
Logic for Computer Science
By Michael Clarke, Steve ReevesAn understanding of logic is essential to computer science. This book provides a highly accessible account of the logical basis required for reasoning about computer programs and applying logic in...
-
A Profile of Mathematical Logic
By Howard DeLongAnyone seeking a readable and relatively brief guide to logic can do no better than this classic introduction. A treat for both the intellect and the imagination, it profiles the...
-
Pulling Up the Ladder: The Metaphysical Roots of Wittgenstein's Tractatus Logico-philosophicus
By Richard R. BrockhausPulling up the Ladder discusses how Wittgenstein's early philosophy became widely known largely through the efforts of Russell and other empirically-minded British philosophers, and to a lesser extent, the scientifically-oriented...
-
Godel's Theorem Simplified
By Harry J. GenslerThis helpful volume explains and proves Godel's theorem, which states that arithmetic cannot be reduced to any axiomatic system. Written simply and directly, this book is intended for the student...
-
Recursion Theory Week: Proceedings of a Conference Held in Oberwolfach, FRG, March 19-25, 1989
By Klaus Ambos-Spies, Gert H. MüllerThese proceedings contain research and survey papers from many subfields of recursion theory, with emphasis on degree theory, in particular the development of frameworks for current techniques in this field....