Computable analysis. An introduction
computabilitycomputable analysiscomputable metric spacesnaming systemsTuring machinestype-2 theory of effectivity
Complexity of computation (including implicit computational complexity) (03D15) Constructive and recursive analysis (03F60) Continuity and related questions (modulus of continuity, semicontinuity, discontinuities, etc.) for real functions in one variable (26A15) Constructive real analysis (26E40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
The increasing demand for reliable and efficient software in science and engineering requires a sound and broad foundation not only of the analytical/numerical but also of the computational aspects of real number computation. Computable analysis studies those functions on the real numbers and related sets which can be computed by digital computers. Although it has a long and rich history going back to Turing's fundamental paper [Proc. Lond. Math. Soc. II. Ser. 42, 230-265 (1936; Zbl 0016.09701)], computable analysis (including constructive analysis) still appears as a juxtaposition of several partly overlapping, more or less developed approaches. For the interested newcomer this situation is bewildering and learning the state of the art is a laborious undertaking, since there are not even generally accepted basic definitions. This book is a new attempt to present a coherent foundation for computable analysis. It connects the two classical disciplines analysis/numerical analysis and computability/complexity theory merging concepts from both of them, in particular, the central concepts of limit and approximation on the one hand and of machine models and discrete computation on the other hand. The central subject of the book is ``Type-2 Theory of Effectivity (TTE), one of the approaches to effective analysis being discussed today. It is based on definitions of computable real numbers and functions by \textit{A. Turing} and \textit{A. Grzegorczyk} [Fundamenta Math. 42, 232-239 (1955; Zbl 0067.00301)] and the theory of representations initiated by \textit{J. Hauck} [Z. Math. Logik Grundlagen Math. 26, 565-576 (1980; Zbl 0455.03025)]. In TTE, computable functions on infinite sequences of symbols are defined by means of Turing machines, and computability is transferred to other sets by representations, where infinite sequences of symbols serve as names of abstract objects like real numbers. After an informal introduction to central concepts, computability on infinite sequences with its topological properties is studied. Computability induced by representations is discussed in Chapter 3, where, in particular, the important class of ``admissible representations is introduced. Chapter 4 is devoted to computable real numbers and functions. Computability on spaces of subsets of \(\mathbb{R}^n\) and on spaces of real functions are introduced and discussed in Chapters 5 and 6, respectively. As a refinement of computability, the computational complexity of real functions is introduced in Chapter 7. Computable metric spaces and degrees of discontinuity are extensions of the basic theory which are discussed in Chapter 8. Finally in Chapter 9, some of the other approaches to computable analysis are compared with TTE, and the author expounds his reasons to choose the representation approach for his foundation of computable analysis. The book is intended as a textbook suitable for graduate students in computer science and mathematics. More than 400 exercises provide the instructor with sufficient material for homework and tests. Although many parts offer themselves for straightforward extension or generalization, the author has tried to concentrate on the most important elementary topics and to remain at a homogeneous moderate ``level of abstraction in order to keep the text short and make it accessible to a broader readership. This book provides straightforward and sound access to a fundamental field which has been neglected so far in academic education. I strongly recommend it to everyone, who wants to learn computable analysis or to teach a course on this topic.
- The metamathematics of ergodic theory
- A computable version of Banach's inverse mapping theorem
- Operational domain theory and topology of sequential programming languages
- Coinduction for exact real number computation
- Classification of computably approximable real numbers
- A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties
- A computable approach to measure and integration theory
- Computing fundamental domains for Fuchsian groups
- Computing the uncomputable; or, the discrete charm of second-order simulacra
- Computations via Newtonian and relativistic kinematic systems
- The influence of domain interpretations on computational models
- What is a universal computing machine?
- Computational bounds on polynomial differential equations
- Unifying computers and dynamical systems using the theory of synchronous concurrent algorithms
- Problems, solutions, and completions
- Constructing locally connected non-computable Julia sets
- Effective symbolic dynamics, random points, statistical behavior, complexity and entropy
- An effective Riemann Mapping Theorem
- Online computations of differentiable functions
- Handbook of computability theory
- Random elements in effective topological spaces with measure.
- A blend of methods of recursion theory and topology.
- On the hierarchy and extension of monotonically computable real numbers.
- Recursive quasi-metric spaces.
- Computability on subsets of metric spaces.
- A constructive theory of point-set nearness.
- Hierarchies of total functionals over the reals
- Real computations with fake numbers
- Quantified constraints under perturbation
- Domain representations of partial functions, with applications to spatial objects and constructive volume geometry.
- Topological properties of real number representations.
- Effectively closed sets and graphs of computable real functions.
- Real number computation through Gray code embedding.
- The closure properties on real numbers under limits and computable operators.
- Extended admissibility.
- On the uniform computational content of the Baire category theorem
- Comparing representations for function spaces in computable analysis
- Abstract geometrical computation. VIII: Small machines, accumulations \& rationality
- The Hausdorff and dynamical dimensions of self-affine sponges: a dimension gap result
- A topological view on algebraic computation models
- On the information carried by programs about the objects they compute
- On the uniform computational content of computability theory
- Reducibility of computable metrics on the real line
- Semicomputable manifolds in computable topological spaces
- On constructive number fields and computability of solutions of PDEs
- Warsaw discs and semicomputability
- \(\Sigma\)-definability in hereditarily finite superstructures and computable analysis
- Algorithmic identification of probabilities is hard
- Abstract geometrical computation. V: Embedding computable analysis
- Computability in planar dynamical systems
- A survey of recursive analysis and Moore's notion of real computation
- A blend of methods of recursion theory and topology: a _1⁰ tree of shadow points
- Computable total functions on metric algebras, universal algebraic specifications and dynamical systems
- A Banach-Mazur computable but not Markov computable function on the computable real numbers
- Computing the solution of the Korteweg-de Vries equation with arbitrary precision on Turing machines
- Some computational aspects of metric fixed-point theory
- An optical model of computation
- Efficient exact computation of iterated maps
- Real number computation with committed choice logic programming languages
- Recent progress in exact geometric computation
- Non computable Mandelbrot-like sets for a one-parameter complex family
- Bounded Turing reductions and data processing inequalities for sequences
- Effective Hausdorff dimension in general metric spaces
- Generated quasi-metric hyper and function spaces.
- An analog characterization of the Grzegorczyk hierarchy
- Proof mining in \(L_{1}\)-approximation
- Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
- The rate of convergence of the walk on spheres algorithm
- Learning figures with the Hausdorff metric by fractals -- towards computable binary classification
- Characterization of Kurtz randomness by a differentiation theorem
- Algorithmic randomness and Fourier analysis
- On approximations for functions in the space of uniformly convergent Fourier series
- Outline of partial computability in computable topology
- Towards computable analysis on the generalised real line
- On higher effective descriptive set theory
- Game characterizations and lower cones in the Weihrauch degrees
- Computability, noncomputability, and hyperbolic systems
- A note on computable distinguishing colorings
- Computable metrics above the standard real metric
- Computability of products of chainable continua
- Precomplete numberings
- Polynomial time over the reals with parsimony
- Dense computability structures
- Highness properties close to PA completeness
- The \texttt{ksmt} calculus is a \(\delta \)-complete decision procedure for non-linear constraints
- On the computability of the set of automorphisms of the unit square
- Language equations
- Constructive hybrid games
- Irrational-based computability of functions
- Computable topological abelian groups
- A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations
- On envelopes and backward approximations
- Computational complexity of classical solutions of partial differential equations
- Effective compactness and orbits of points under the isometry group
- Metric spaces are universal for bi-interpretation with metric structures
- Some notes on spaces of ideals and computable topology
- Liouville numbers and the computational complexity of changing bases
- On the complexity of conversion between classic real number representations
- Computable analysis and classification problems
- Degrees of non-computability of homeomorphism types of Polish spaces
This page was built for publication: Computable analysis. An introduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4485693)
