Bøger i Theory and Applications of Computability serien

This book presents a theory of apartness encompassing both point-set topology and the theory of uniform spaces. The first book on the apartness approach to constructive topology, it is a valuable addition to the literature on topology in computer science.

This book questions the relevance of computation to the physical universe.

This book offers a self-contained exposition of the theory of computability in a higher-order context, where 'computable operations' may themselves be passed as arguments to other computable operations.

This book emphasizes three very important concepts: computability, as opposed to recursion or induction; classical computability; and the art of computability, a skill to be practiced but also important in an esthetic sense of beauty and taste in mathematics.

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.

This book questions the relevance of computation to the physical universe.

Intuitively, a sequence such as 101010101010101010... does not seem random, whereas 101101011101010100..., obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object such as a real number is random, or to say that one real is more random than another? And what is the relationship between randomness and computational power. The theory of algorithmic randomness uses tools from computability theory and algorithmic information theory to address questions such as these. Much of this theory can be seen as exploring the relationships between three fundamental concepts: relative computability, as measured by notions such as Turing reducibility; information content, as measured by notions such as Kolmogorov complexity; and randomness of individual objects, as first successfully defined by Martin-Löf. Although algorithmic randomness has been studied for several decades, a dramatic upsurge of interest in the area, starting in the late 1990s, has led to significant advances. This is the first comprehensive treatment of this important field, designed to be both a reference tool for experts and a guide for newcomers. It surveys a broad section of work in the area, and presents most of its major results and techniques in depth. Its organization is designed to guide the reader through this large body of work, providing context for its many concepts and theorems, discussing their significance, and highlighting their interactions. It includes a discussion of effective dimension, which allows us to assign concepts like Hausdorff dimension to individual reals, and a focused but detailed introduction to computability theory. It will be of interest to researchers and students in computability theory, algorithmic information theory, and theoretical computer science.

Reverse mathematics studies the complexity of proving mathematical theorems and solving mathematical problems. Typical questions include: Can we prove this result without first proving that one? Can a computer solve this problem? A highly active part of mathematical logic and computability theory, the subject offers beautiful results as well as significant foundational insights.This text provides a modern treatment of reverse mathematics that combines computability theoretic reductions and proofs in formal arithmetic to measure the complexity of theorems and problems from all areas of mathematics. It includes detailed introductions to techniques from computable mathematics, Weihrauch style analysis, and other parts of computability that have become integral to research in the field. Topics and features:Provides a complete introduction to reverse mathematics, including necessary background from computability theory, second order arithmetic, forcing, induction, and model constructionOffers a comprehensive treatment of the reverse mathematics of combinatorics, including Ramsey's theorem, Hindman's theorem, and many other resultsProvides central results and methods from the past two decades, appearing in book form for the first time and including preservation techniques and applications of probabilistic argumentsIncludes a large number of exercises of varying levels of difficulty, supplementing each chapterThe text will be accessible to students with a standard first year course in mathematical logic. It will also be a useful reference for researchers in reverse mathematics, computability theory, proof theory, and related areas.Damir D. Dzhafarov is an Associate Professor of Mathematics at the University of Connecticut, CT, USA. Carl Mummert is a Professor of Computer and Information Technology at Marshall University, WV, USA.

It is not always clear what computer programs mean in the various languages in which they can be written, yet a picture can be worth 1000 words, a diagram 1000 instructions.In this unique textbook/reference, programs are drawn as string diagrams in the language of categories, which display a universal syntax of mathematics (Computer scientists use them to analyze the program semantics; programmers to display the syntax of computations). Here, the string-diagrammatic depictions of computations are construed as programs in a single-instruction programming language. Such programs as diagrams show how functions are packed in boxes and tied by strings. Readers familiar with categories will learn about the foundations of computability; readers familiar with computability gain access to category theory. Additionally, readers familiar with both are offered many opportunities to improve the approach.Topics and features:Delivers a ¿crash¿ diagram-based course in theory of computationUses single-instruction diagrammatic programming languageOffers a practical introduction into categories and string diagrams as computational toolsReveals how computability is programmability, rather than an ¿ether¿ permeating computers Provides a categorical model of intensional computation is unique up to isomorphismServes as a stepping stone into research of computable categoriesIn addition to its early chapters introducing computability for beginners, this flexible textbook/resource also contains both middle chapters that expand for suitability to a graduate course as well as final chapters opening up new research. Dusko Pavlovic is a professor at the Department of Information and Computer Sciences at the University of Hawaii at Manoa, and by courtesy at the Department of Mathematics and the College of Engineering. He completed this book as an Excellence Professor at Radboud University in Nijmegen, The Netherlands.