An Introduction to Computable Analysis

Introduction This chapter is, in a sense, a primer of computable real analysis. We present here most of the basic methods needed to decide standard questions about the computability of real valued functions. Thus the chapter deals in a systematic way with the computability theory of real numbers, real sequences, continuous functions, uniform convergence, integration, maxima and minima, the intermediate value theorem, and several other topics. In fact, most of the usual topics from the standard undergraduate real variables course are treated within the context of computability. There is one conspicuous omission. We postpone the treatment of derivatives until Chapter 1. This is because the computability theory of derivatives is a bit more complicated. Section 1 deals with computable real numbers. A real number is computable if it is the effective limit of a computable sequence of rationals. All of these terms are defined at the beginning of the section. Surprisingly enough, many of the questions concerning individual computable reals require the consideration of computable sequences of reals. This topic is postponed until Section 2. However, a few questions can be answered at this preliminary stage. For example, the definition of “computable real” involves the notion of effective convergence for rational sequences. We show that the hypothesis of effective convergence is not redundant, by showing that there exist computable sequences of rationals which converge, but not effectively (Rice [1954], Specker [1949]). This is done by means of the Waiting Lemma, a standard recursion-theoretic result, which for the sake of completeness we prove. The Waiting Lemma is used repeatedly throughout the book. The section concludes with a brief discussion of some alternative definitions of “computable real number”. Section 2 deals with computable sequences of real numbers. This notion is essential for the entire book. To do work in computable analysis, one has to be totally fluent with all of the nuances related to computable sequences. [The importance of sequences, rather than individual elements, reappears in Part II of this book. Thus in Chapter 2, where we lay down axioms for computability on a Banach space, the concept which is axiomatized is “computable sequence of vectors” in the Banach space.]