Computable analysis. An introduction.

*(English)*Zbl 0956.68056
Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer. x, 281 p. (2000).

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 A. Turing and A. Grzegorczyk [Fundamenta Math. 42, 232-239 (1955; Zbl 0067.00301)] and the theory of representations initiated by 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.

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 A. Turing and A. Grzegorczyk [Fundamenta Math. 42, 232-239 (1955; Zbl 0067.00301)] and the theory of representations initiated by 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.

Reviewer: Zheng Xizhong (Cottbus)

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

03F60 | Constructive and recursive analysis |

03D15 | Complexity of computation (including implicit computational complexity) |

26E40 | Constructive real analysis |

26A15 | Continuity and related questions (modulus of continuity, semicontinuity, discontinuities, etc.) for real functions in one variable |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |