×

Computability in analysis and physics. (English) Zbl 0678.03027

Perspectives in Mathematical Logic, Berlin etc.: Springer-Verlag. x, 206 p. DM 128.00 (1989).
Recursive analysis has a long and rich history dating back to Turing’s original work on recursive functions. Basically one studies the “effective content” of analysis in the sense that we specify the objects “effectively” and then analyses how results from classical analysis behave from an effective (computable) viewpoint. Although related to Bishop’s constructivist school it is nevertheless quite different since (for example) in constructive mathematics one needs to specify which algorithm might perform a process, yet in recursive mathematics one only needs to argue that there merely exists an algorithm. Recursive analysis is also strongly related to various recent investigations into reverse mathematics [e.g. S. Simpson, J. Symb. Logic 49, 783–802 (1984; Zbl 0584.03039)], where effectiveness results are hidden into measurements of the logical strength of classical theorems. In particular, a reverse mathematics result usually implies a relevant recursive analysis result by specializing to a standard model. Finally, recursive analysis has another modern development as feasible mathematics [e.g. Ker-I Ko, Studies in complexity theory, 1–62 (1986; Zbl 0663.68009), H. Friedman and Ker-I Ko, Theor. Comput. Sci. 20, 323–352 (1982; Zbl 0498.03047) or L. Blum, M. Shub and S. Smale [Bull. Am. Math. Soc., New Ser. 21, No. 1, 1–46 (1989; Zbl 0681.03020)]. In feasible mathematics one has close ties with numerical mathematics, and one is concerned with bounding the resources used in computation.
The concern of the present book is traditional recursive analysis. Most of what was in this area up to the 70’s was given in the well-known book of O. Aberth [Computable analysis. New York etc.: McGraw-Hill (1980; Zbl 0461.03015)].
In the last decade, the authors have made a series of major contributions to recursive analysis in papers such as: “The eigenvalues of an effectively determined self-adjoint operator are computable, but the sequence of eigenvalues is not” [Adv. Math. 63, 1–41 (1987; Zbl 0616.47018)], “A computable ordinary differential equation which possesses no computable solution” [Ann. Math. Logic 17, 61–90 (1979; Zbl 0424.68028)], \(``L^ p\) computability in recursive analysis” [Proc. Am. Math. Soc. 92, 93–97 (1984; Zbl 0558.03030)], “Computability and noncomputability in classical analysis” [Trans. Am. Math. Soc. 275, 539–560 (1983; Zbl 0513.03031)], “Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators” [Adv. Math. 48, 43–74 (1983; Zbl 0519.03045)], and “Computability in a Banach space – the eigenvector theorem” (to appear)].
This book is a monograph devoted to giving a coherent exposition of the high points of these contributions.
The book is split into two parts. The first part gives an introduction into recursive analysis beginning with the basic definitions (where the presentation would have been simpler if a little more coding were used) and proceeding to a slight extension of Myhill’s hallmark construction of a computable \(C^ 1\) function defined on a compact interval whose derivative fails to be computable [J. Myhill, A recursive function, defined on a compact interval and having a continuous derivative that is not recursive, Mich. Math. J. 18, 97–98 (1971; Zbl 0218.02029)]. It is fair to say that this result had a major impact on the proof techniques of much of the subsequent research in this area.
The second (and major) part of the book is devoted to presenting the authors’ research. Here they often closely follow their papers. The relevant setting is a ‘computable’ Banach space where this notion is defined axiomatically. In this main part, the presentation is built around three major results: (1) The result from the authors’ paper [loc. cit., 1987] that for a computable self-adjoint operator although the eigenvalues are computable, the sequence is not (merely \(\Sigma_ 2)\), (2) the eigenvector theorem from the authors’ forthcoming paper [loc. cit.], and (3) the very attractive and surprising result (from the authors’ paper [loc. cit., 1983]) that “computable \(=\) bounded” for operators. Result (3) was especially surprising since not only is it rare for a classical condition to correspond to an effective one, but the proof of (3) is so easy (once you see how to do it!).
The book is totally self contained. The book is enthusiastically written and needs essentially no logical prerequisites. This makes the book easily accessible to the classical analyst who is interested in computability issues. The proofs are given very clearly and carefully although the reviewer finds the presentation a little too formal, particularly in the motivation in the proofs. Here the style is similar to the authors’ papers and could be described as ‘classical’.
The counterexamples are recursion theoretically simple in the sense that they use analytic techniques to code r.e. nonrecursive sets or inseparable pairs. As one would expect the positive results usually involve careful analytic approximations and can be quite intricate. (For the reader unfamiliar with this area, it is rather like the difference between a classical analysis proof and a numerical analysis algorithm to implement the result. The latter is often much harder than the former).
It is perhaps unfortunate that the authors have chosen not to give an exposition of other contemporary work in this area and set their results in such a context. For example, as well as the schools mentioned earlier, there is some lovely related work by Rubel, Lipshitz and Singer on analogue computability and gaps in power series, and work by Metakides, Nerode, Shore and others using \(\Pi^ 0_ 1\) classes/priority methods, work by Kreiz and Weihrauch on combining recursive and constructive analysis, and quite a lot of work in the Russian recursive/constructive analysis schools. Unfortunately, a book integrating all of this work remains to be written and would clearly constitute a major and rather difficult project.
Nevertheless, the authors have obviously achieved their goals by presenting a clearly written and accessible account containing both the basic results of recursive analysis and a careful selection of the authors’ own substantial and important results from the last decade. This book is clearly a must of anybody whose research is in this area and would constitute a good addition to the library of anybody interested in computability issues.
Reviewer: R.Downey

MSC:

03F60 Constructive and recursive analysis
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
46S30 Constructive functional analysis
46-02 Research exposition (monographs, survey articles) pertaining to functional analysis
03D80 Applications of computability and recursion theory
PDFBibTeX XMLCite