Complexity, Logic, and Recursion Theory

by Andrea Sorbi

Overview

"Integrates two classical approaches to computability. Offers detailed coverage of recent research at the interface of logic, computability theory, nd theoretical computer science. Presents new, never-before-published results and provides informtion not easily accessible in the literature."

Product Details

ISBN-13:	9781138404106
Publisher:	CRC Press
Publication date:	06/07/2019
Series:	Lecture Notes in Pure and Applied Mathematics , #187
Pages:	380
Product dimensions:	7.00(w) x 10.00(h) x (d)

About the Author

Andrea Sorbi is Associate Professor in the Department of Mathematics at the University of Siena, Italy. The author or coauthor of several key professional papers and book chapters on computability theory and mathematical logic, he is a member of the American Mathematical Society and the Association for Symbolic Logic, among other organizations. Dr. Sorbi received the Ph.D. degree (1987) in mathematics from the City University of New York, New York.

Table of Contents

Preface, Contributors, Resource-Bounded Measure and Randomness, Degree Structures in Local Degree Theory, Compressibility of Infinite Binary Sequences, Beyond Gödel’s Theorem: The Failure to Capture Information Content, Progressions of Theories of Bounded Arithmetic, On Presentations of Algebraic Structures, Witness-Isomorphic Reductions and Local Search, A Survey of Inductive Inference with an Emphasis on Queries, A Uniformity of Degree Structures, Short Course on Logic, Algebra, and Topology, The Enumeration Degrees of the ∑02 Sets, The Convenience of Tilings

Editorial Reviews

Integrates two classical approaches to computability, recursion and complexity, to examine recent research and results at the interface of logic, computability theory, and theoretical computer science. Among the topics are resource-bounded measure and randomness, degree structures in local degree theory, presentations of algebraic structures, inductive inference emphasizing queries, and the convenience of tilings. The 12 lectures were presented at three workshops between the beginning of 1994 and the end of 1996. No index. Annotation c. by Book News, Inc., Portland, Or.

Booknews