Skip to main content
main-content

Über dieses Buch

Computable analysis is the modern theory of computability and complexity in analysis that arose out of Turing's seminal work in the 1930s. This was motivated by questions such as: which real numbers and real number functions are computable, and which mathematical tasks in analysis can be solved by algorithmic means?

Nowadays this theory has many different facets that embrace topics from computability theory, algorithmic randomness, computational complexity, dynamical systems, fractals, and analog computers, up to logic, descriptive set theory, constructivism, and reverse mathematics. In recent decades computable analysis has invaded many branches of analysis, and researchers have studied computability and complexity questions arising from real and complex analysis, functional analysis, and the theory of differential equations, up to (geometric) measure theory and topology.

This handbook represents the first coherent cross-section through most active research topics on the more theoretical side of the field. It contains 11 chapters grouped into parts on computability in analysis; complexity, dynamics, and randomness; and constructivity, logic, and descriptive complexity. All chapters are written by leading experts working at the cutting edge of the respective topic. Researchers and graduate students in the areas of theoretical computer science and mathematical logic will find systematic introductions into many branches of computable analysis, and a wealth of information and references that will help them to navigate the modern research literature in this field.

Inhaltsverzeichnis

Frontmatter

Computability in Analysis

Frontmatter

Chapter 1. Computability of Real Numbers

Abstract
In scientific computation and engineering real numbers are typically approximated by rational numbers which approximate, in principle, the real numbers up to any given precision. This means that they are treated as the limits of computable sequences of rational numbers where an effective error estimation is often expected. Although such approximations exist for many constants, they do not exist for all constants. More precisely, approximations with an effective control over the approximation error exist only for the computable real numbers. As long as we are interested in approximations of real numbers, the weakest condition we can ask for is that a real number can be approximated by a computable sequence of rational numbers without any information about the approximation error. These real numbers are called computably approximable. By relaxing and varying conditions on the knowledge one has about the approximation, one gets several natural classes between these two classes of real numbers. In this paper we review the most natural classes which have been investigated over the past decades with respect to this viewpoint. Most of these classes can be characterized in different ways, partly by purely mathematical properties and partly by their computational properties.
Robert Rettinger, Xizhong Zheng

Chapter 2. Computability of Subsets of Metric Spaces

Abstract
We present a survey on computability of subsets of Euclidean space and, more generally, computability concepts on metric spaces and their subsets. In particular, we discuss computability of points in co-c.e. closed sets, representations of hyperspaces, Borel codes, computability of connectedness notions, classification of Polish spaces, computability of semicomputable sets, continua and manifolds, properties of computable images of a segment, and computability structures.
Zvonko Iljazović, Takayuki Kihara

Chapter 3. Computability of Differential Equations

Abstract
In this chapter, we provide a survey of results concerning the computability and computational complexity of differential equations. In particular, we study the conditions which ensure computability of the solution to an initial value problem for an ordinary differential equation (ODE) and analyze the computational complexity of a computable solution. We also present computability results concerning the asymptotic behaviors of ODEs as well as several classically important partial differential equations.
Daniel S. GraÇa, Ning Zhong

Chapter 4. Computable Complex Analysis

Abstract
We give an introduction to the field of computable complex analysis and survey results on conformal mapping, harmonic functions, infinite products, and constants. We also suggest problems for further investigation.
Valentin V. Andreev, Timothy H. McNicholl

Complexity, Dynamics, and Randomness

Frontmatter

Chapter 5. Computable Geometric Complex Analysis and Complex Dynamics

Abstract
We discuss computability and computational complexity of conformal mappings and their boundary extensions. As applications, we review the state of the art regarding computability and complexity of Julia sets, their invariant measures, and external ray impressions.
Cristóbal Rojas, Michael Yampolsky

Chapter 6. A Survey on Analog Models of Computation

Abstract
We present a survey on analog models of computation. Analog can be understood both as computing by analogy, or as working on the continuum. We consider both approaches, often intertwined, with a point of view mostly oriented by computation theory.
Olivier Bournez, Amaury Pouly

Chapter 7. Computable Measure Theory and Algorithmic Randomness

Abstract
We provide a survey of recent results in computable measure and probability theory, from the perspectives of both computable analysis and algorithmic randomness, and discuss the relations between them.
Mathieu Hoyrup, Jason Rute

Chapter 8. Algorithmic Fractal Dimensions in Geometric Measure Theory

Abstract
The development of algorithmic fractal dimensions in this century has had many fruitful interactions with geometric measure theory, especially fractal geometry in Euclidean spaces. We survey these developments, with emphasis on connections with computable functions on the reals, recent uses of algorithmic dimensions in proving new theorems in classical (non-algorithmic) fractal geometry, and directions for future research.
Jack H. Lutz, Elvira Mayordomo

Constructivity, Logic, and Descriptive Complexity

Frontmatter

Chapter 9. Admissibly Represented Spaces and Qcb-Spaces

Abstract
A basic concept of Type Two Theory of Effectivity (TTE) is the notion of an admissibly represented space. Admissibly represented spaces are closely related to qcb-spaces. The latter form a well-behaved subclass of topological spaces. In this chapter we give a survey of basic facts about Type Two Theory of Effectivity, admissibly represented spaces, qcb-spaces and effective qcb-spaces. Moreover, we discuss the relationship of qcb-spaces to other categories relevant to Computable Analysis.
Matthias Schröder

Chapter 10. Bishop-Style Constructive Reverse Mathematics

Abstract
We give a self-contained overview of the current state of Constructive Reverse Mathematics.
Hannes Diener, Hajime Ishihara

Chapter 11. Weihrauch Complexity in Computable Analysis

Abstract
We provide a self-contained introduction toWeihrauch complexity and its applications to computable analysis. This includes a survey on some classification results and a discussion of its relation to other approaches.
Vasco Brattka, Guido Gherardi, Arno Pauly

Backmatter

Weitere Informationen