S Barry Cooper

This book aims to provide a unique introduction to the mathematics of computing with imperfect information. This rapidly developing field has been represented by a growing number of diverse contributions to academic journals and the proceedings of international conferences. The aim here is to bring a new coherence and clarity to this complex and expanding body of research, and to give a comprehensive overview that will be invaluable to both experts and research students new to the area.In many real-world contexts, it is necessary to make decisions based on incomplete information. This book deals with the mathematics underlying the practical computations that it entails. The theory impacts on a wide range of fields, within mathematics and beyond, and has given rise to unexpected connections and deep and interesting ongoing research. This book is essential reading for mathematicians and computer scientists concerned with the computational structure of information, and many others for whom computing in a real context involves working on emergent data.

Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way.