Handbook of Computability and Complexity in Analysis (Theory and Applications of Computability)

✍ Scribed by Vasco Brattka (editor), Peter Hertling (editor)

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 444
• Edition: 1st ed. 2021
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Preface
A Very Short History of Computable Analysis in the Previous Century
Overview of the Chapters
Computability in Analysis
Complexity, Dynamics, and Randomness
Constructivity, Logic, and Descriptive Complexity
Outlook
References
Contents
List of Contributors
Part I Computability in Analysis
Chapter 1 Computability of Real Numbers
1.1 Introduction
1.2 Computable Real Numbers
1.3 A Finite Hierarchy of Computably Approximable Real Numbers
1.4 Differences of C.E. Real Numbers
1.5 Divergence Bounded Computable Real Numbers
1.6 Turing Degrees of Computably Approximable Real Numbers
References
Chapter 2 Computability of Subsets of Metric Spaces
2.1 Introduction
2.2 Computable Subsets of Euclidean Space
2.3 Computable Metric Spaces
2.3.1 Computable Compact and Closed Sets
2.4 Noncomputability of Points in Co-C.E. Closed Sets
2.4.1 Basis Theorems in Computability Theory
2.4.2 Basis Theorems in Computable Analysis
2.5 Represented Spaces and Uniform Computability
2.5.1 Represented Hyperspaces
2.5.2 Represented Function Spaces
2.5.3 Borel Codes
2.6 Computability of Connectedness Notions
2.6.1 Effective Connectivity Properties
2.6.2 Computable Graph Theorem
2.6.3 Degrees of Difficulty
2.7 Classification of Polish Spaces
2.7.1 Borel Isomorphism Theorem
2.7.2 Continuous Degree Theory
2.7.3 Computable Aspects of Infinite Dimensionality
2.8 Computability of Semicomputable Sets
2.8.1 Semicomputable Chainable and Circularly Chainable Continua
2.8.2 Semicomputable Manifolds
2.8.3 Inner Approximation
2.8.4 Density of Computable Points in Semicomputable Sets
2.9 Computable Images of a Segment
2.10 Computability Structures
References
Chapter 3 Computability of Differential Equations
3.1 Introduction
3.2 Computability of the Solutions of Ordinary Differential Equations
3.2.1 Computability over Compact Sets
3.2.2 Computability over Non-compact Sets
3.3 Computational Complexity of the Solutions of Ordinary Differential Equations
3.3.1 Results for Compact Sets
3.3.2 Results for Non-compact Sets
3.4 Computability of Qualitative Behaviors of Ordinary Differential Equations
3.5 Computability of Partial Differential Equations
3.6 Some Open Problems
References
Chapter 4 Computable Complex Analysis
4.1 Introduction
4.2 Preliminaries from Complex Analysis
4.3 Computability on the Complex Plane and Extended Complex Plane
4.3.1 Computability of Differentiation, Computably Analytic Functions
4.3.2 Series
4.3.3 Zeros
4.3.4 Open Mapping
4.4 Computable Conformal Mapping of Simply Connected Domains
4.4.1 Classical Background
4.4.2 Computability Results
4.4.3 Complexity Results
4.5 Boundary Extensions
4.5.1 Classical Background
4.5.2 Computability Results
4.6 Harmonic Functions
4.6.1 Classical Background
4.6.2 Computability Results
4.7 Conformal Mapping of Multiply Connected Domains
4.7.1 Classical Background
4.7.2 Computability Results
4.8 Infinite Products
4.8.1 Classical Background
4.8.2 Computability Results
4.9 Constants
4.9.1 Classical Background
4.9.2 Computability Results
4.9.3 Complexity Results
4.10 Open Problems
4.10.1 The Hayman-Wu Constant
4.10.2 Parameterized Complexity Riemann Mapping Theorem
4.10.3 Computability Conformal Mapping onto Infinitely Connected Domains
References
Part II Complexity, Dynamics, and Randomness
Chapter 5 Computable Geometric Complex Analysis and Complex Dynamics
5.1 Introduction
5.2 Required Computability Notions
5.2.1 Computable Metric Spaces
5.2.2 Computability of Probability Measures
5.2.3 Time Complexity of a Problem
5.2.4 Computational Complexity of Two-Dimensional Images
5.3 Computability and Complexity of Conformal Mappings
5.4 Computable Carath´eodory Theory
5.4.1 Carath´eodory Extension Theorem
5.4.2 Computational Representation of Prime Ends
5.4.3 Structure of a Computable Metric Space on the Carath´eodory Compactification
5.4.4 Moduli of Locally Connected Domains
5.4.5 Computable Carath´eodory Theory
5.5 Computability in Complex Dynamics: Julia Sets
5.5.1 Basic Properties of Julia Sets
5.5.2 Occurrence of Siegel Disks and Cremer Points in the Quadratic Family
5.5.3 Computability of Julia Sets
5.5.4 Computational Complexity of Julia Sets
5.5.5 Computing Julia Sets in Statistical Terms
5.5.6 Applications of Computable Carath´eodory Theory to Julia Sets: External Rays and Their Impressions
5.5.7 On the Computability of the Mandelbrot Set
References
Chapter 6 A Survey on Analog Models of Computation
6.1 Introduction
6.2 Various Analog Machines and Models
6.2.1 Historical Accounts
6.2.2 Differential Analyzers
6.2.3 Neural Networks and Deep Learning Models
6.2.4 Models from Verification
6.2.5 Blum-Shub-Smale’s Model
6.2.6 Natural Computing
6.2.7 Solving Various Problems Using Dynamical Systems
6.2.8 Distributed Computing
6.2.9 Black Hole Models
6.2.10 Spatial Models
6.2.11 Various Other Models
6.3 Dynamical Systems and Computations
6.3.1 Arbitrary Versus Rational/Computable Reals
6.3.2 Static Undecidability
6.3.3 Dynamic Undecidability
6.4 Philosophical, Mathematical and Physics-Related Aspects
6.4.1 Mathematical Models Versus Systems
6.4.2 Church-Turing Thesis and Variants
6.4.3 Are Analog Systems Capable of Hypercomputations?
6.4.4 Can Analog Machines Compute Faster?
6.4.5 Some Philosophical Aspects
6.5 Theory of Analog Systems
6.5.1 Generic Formalizations of Analog Computations
6.5.2 R-recursion Theory
6.5.3 Analog Automata Theories
6.6 Analyzing the Power and Limitations of Analog Computations
6.6.1 Neural Networks
6.6.2 Physical Oracles
6.6.3 On the Effect of Noise on Computations
6.6.4 Complexity Theories for Analog Computations
6.6.5 Chemical Reaction Networks
6.7 Computations by Polynomial Ordinary Differential Equations
6.7.1 GPAC and Polynomial Ordinary Differential Equations
6.7.2 GPAC Generable Functions
6.7.3 GPAC Computability
References
Chapter 7 Computable Measure Theory and Algorithmic Randomness
7.1 Introduction
7.2 Computable Measure Theory
7.2.1 Background from Computable Analysis
7.2.2 Framework
7.2.3 Results in Computable Measure and Probability Theory
7.3 Algorithmic Randomness
7.3.1 Effective Null Sets
7.3.2 Effective Convergence Theorems
7.3.3 Randomness Preservation
7.3.4 Product Spaces
7.4 Pointwise Computable Measure Theory
7.4.1 Effective Tightness
7.4.2 Effective Egorov’s Theorem
7.4.3 Effective Lusin Theorem
7.4.4 Effective Absolute Continuity
7.4.5 Properties of Layerwise Computable Functions
7.4.6 Randomness via Encoding
7.4.7 Recovering a Distribution from a Sample
References
Chapter 8 Algorithmic Fractal Dimensions in Geometric Measure Theory
8.1 Introduction
8.2 Algorithmic Information in Euclidean Spaces
8.3 Algorithmic Dimensions
8.3.1 Dimensions of Points
8.3.2 The Correspondence Principle
8.3.3 Self-Similar Fractals
8.3.4 Dimension Level Sets
8.3.5 Dimensions of Points on Lines
8.4 Mutual and Conditional Dimensions
8.4.1 Mutual Dimensions
8.4.2 Data Processing Inequalities
8.4.3 Conditional Dimensions
8.5 Algorithmic Discovery of New Classical Theorems
8.5.1 The Point-to-Set Principle
8.5.2 Plane Kakeya Sets
8.5.3 Intersections and Products of Fractals
8.5.4 Generalized Furstenberg Sets
8.6 Research Directions
8.6.1 Beyond Self-Similarity
8.6.2 Beyond Euclidean Spaces
8.6.3 Beyond Computability
8.6.4 Beyond Fractals
References
Part III Constructivity, Logic, and Descriptive Complexity
Chapter 9 Admissibly Represented Spaces and Qcb-Spaces
9.1 Introduction
9.2 Represented Spaces
9.2.1 Representations
9.2.2 The Baire Space
9.2.3 Computability on the Baire Space
9.2.4 Represented Spaces
9.2.5 Computable Elements of Represented Spaces
9.2.6 Computable Realizability
9.2.7 The Cauchy Representation of the Real Numbers
9.2.8 The Signed-Digit Representation
9.2.9 Continuous Realizability
9.2.10 Reducibility and Equivalence of Representations
9.2.11 The Category of Represented Spaces
9.2.12 Closure Properties of Represented Spaces
9.2.13 Multivalued Functions
9.2.14 Multirepresentations
9.3 Admissible Representations of Topological Spaces
9.3.1 The Topology of a Represented Space
9.3.2 Sequential Topological Spaces
9.3.3 Sequentialisation of Topological Spaces
9.3.4 Topological Admissibility
9.3.5 Examples of Admissible Representations
9.3.6 The Admissibility Notion of Kreitz and Weihrauch
9.3.7 Constructing Admissible Representations
9.3.8 Pseudobases
9.4 Qcb-Spaces
9.4.1 Qcb-Spaces
9.4.2 Operators on Qcb-Spaces
9.4.3 Powerspaces in QCB0
9.4.4 Qcb-Spaces and Admissibility
9.4.5 Effectively Admissible Representations
9.4.6 Effective Qcb-Spaces
9.4.7 Basic Computable Functions on Effective Qcb-Spaces
9.4.8 Effective Hausdorff Spaces
9.4.9 Quasi-normal Qcb-Spaces
9.5 Relationship to Other Relevant Categories
9.5.1 Represented Spaces
9.5.2 Equilogical Spaces
9.5.3 Limit Spaces
9.5.4 Cartesian Closed Subcategories of Topological Spaces
References
Chapter 10 Bishop-Style Constructive Reverse Mathematics
10.1 Introduction
10.2 Preliminaries
10.3 Omniscience Principles: LPO, WLPO, and LLPO
10.4 Markov’s Principle and Related Principles: MP, WMP, and MP
10.5 A Continuity Principle, the Fan Theorem, and Church’s Thesis
10.6 The Boundedness Principle: BD-N
10.7 Relationships Between Principles
10.8 Separation Techniques
References
Chapter 11 Weihrauch Complexity in Computable Analysis
11.1 The Algebra of Problems
11.2 Represented Spaces
11.3 The Weihrauch Lattice
11.4 Algebraic and Topological Properties
11.5 Completeness, Composition and Implication
11.6 Limits and Jumps
11.7 Choice
11.7.1 Composition and Non-determinism
11.7.2 Choice on Natural Numbers
11.7.3 Choice on the Cantor Space
11.7.4 Choice on Euclidean Space
11.7.5 Choice on the Baire Space
11.7.6 Jumps of Choice
11.7.7 All-or-Unique Choice
11.8 Classifications
11.9 Relations to Other Theories
11.9.1 Linear Logic
11.9.2 Medvedev Lattice, Many-One and Turing Semilattices
11.9.3 Reverse Mathematics
11.9.4 Constructive Reverse Mathematics
11.9.5 Other Reducibilities
11.9.6 Descriptive Set Theory
11.9.7 Other Models of Computability
References
Index