Computable Calculus, Oliver Aberth, Academic Press 2001, ISBN
0-12-041752-9, 192+xiv, with compact disk 0-12-141753-7
Constructive mathematics is a marriage of computation and pure mathematics.
The basic idea is that all mathematics should be grounded in computation. That
may seem pretty uncontroversial, especially to the general public, but
mathematicians do lots of things that have no apparent computational basis.
The subject here, however, is calculus, which, one would think, is firmly
based on computation. Not so. As the theory of calculus is ordinarily taught,
the highly noncomputational least upper bound principle is freely invoked and
the question of the equality of two given real numbers, which cannot be
settled by a computation, is taken as unproblematic. Aberth's book attempts to
Heyting  contrasted two approaches to constructive mathematics:
It is necessary to distinguish between theories of the constructible and
constructive theories; the main difference being that in a constructive theory
an object exists only after it has been constructed while in theories of the
constructible one defines a certain class of mathematical objects to be
Heyting was an intuitionist, a student of L.E.J. Brouwer. The
intuitionists, and those of us who practice constructive mathematics after the
manner of Errett Bishop , develop constructive theories without
defining a class of constructible objects. The rules of constructive proof
were spelled out, stripped of their philosophical context, by Heyting's
formulation of intuitionistic logic. By restricting ourselves to
intuitionistic logic, we can be assured that our theories will be constructive.
On the other hand, those who study recursive functions or Turing machines, and
related concepts such as computable real numbers, deal with constructible
objects, but not usually from a constructive point of view (see, for example,
). The Russian school of constructivism, which inspired Aberth,
incorporates both of these approaches---it is a constructive theory of
constructible objects. Boris Kushner  stated the three principles of
this school (see also Sanin ):
The "constructive objects" studied by this school are finite
strings of symbols taken from a finite alphabet. Strings of digits can be
interpreted directly as natural numbers; other strings can be interpreted as
programs in a programming language---in particular, a real number a can be
identified with a program that computes arbitrarily close rational
approximations to a. The "precise concept of algorithm" was introduced by
Markov . Various other models of computation, such as Turing machines
and recursive functions, have been shown to be translatable into Markov
algorithms, and vice versa . The "special interpretation of
mathematical judgments" is intuitionistic logic, a logic that does not use
the law of excluded middle.
The objects of study are constructive objects.
- The intuitive concept of computability is replaced by the precise
concept of algorithm.
- A special interpretation of mathematical judgments is used which takes
into account the specific nature of constructive objects.
Why would anyone reject the law of excluded middle? One consequence of that
law is that, for each real number a, either a=0 or a¹0. From a
thoroughgoing computational point of view, that should mean that we can
calculate whether or not a equals 0. But this is exactly Aberth's
Nonsolvable Problem 3.1: "For any real number a, decide whether or
not a equals 0." Intuitively, Problem 3.1 is unsolvable because there is
clearly no way to figure out from a rational approximation to a, no matter
how close, whether or not a is 0. Technically, the unsolvability of the
halting problem for Turing machines says that you can't figure it out even if
you look at a program that computes arbitrarily close rational approximations
to a. Thus, grounding all of our mathematics in computation leads to
rejecting the law of excluded middle.
Aberth draws a distinction between "there exists a number such that ...
," and "there cannot fail to exist a number such that ...." His
statement of the intermediate value theorem is, "If f(0)<0<f(1) then a
number r between 0 and 1 such that f(r)=0 cannot fail to exist."
(Kushner  also employs the phrase "cannot fail to exist", but
phrases this particular theorem in terms of the impossibility that f(r)¹0
for all r.) Thus Aberth appears to reject classical logic, and so to
subscribe to the third principle in Kushner's list. However, instead of
adopting a constructive logic, Aberth simply says,
Rather than say "a number x0 exists" or "a number x0 can be
found," when x0 sometimes cannot be determined accurately by finite
means, it is less confusing to say "the number x0 cannot fail to exist."
Nevertheless, Aberth often uses the word "exists" in a
noncomputational sense, as when he says, "A computable way of obtaining
K0 as a function of E is not required, only the certainty that for
every E an integer K0 exists." Similarly, despite Nonsolvable Problem
3.1, he claims that "for any two real number a and b, we have exactly one
of the three possibilities: a=b, a<b, or a>b." This suggests that his
point of view is more that of a classical recursive function theorist than a
Another aspect of the Russian school is that it has a philosophical commitment
to constructive objects---those are the only objects on the table. A
constructive real number is not thought of as a special type of real number.
As Sanin [9, page 11] put it, "Concepts of this kind will not be
considered here. They lie outside the scope of the constructive approach to
mathematics since they are based upon the nonconstructive concept of real
number used in classical mathematics." Aberth does not take this position. He
defines computable real numbers as "real numbers for which arbitrarily
precise approximations can be computed by a machine".
In spite of these differences, I found that Aberth's previous book,
Computable Analysis , provides a much better way for the
average reader to get acquainted with the ideas of Russian constructivism than
do the translations of the formidable Russian sources, and is much more in the
spirit of Russian constructivism than is the recursive analysis developed by
recursive function theorists. The same can be said of the present book, which
is addressed to a less sophisticated audience and is even more user friendly.
The commitment to machine computability has consequences that seem bizarre to
the uninitiated. An example is the Specker sequence---an ascending sequence of
rational numbers in (0,1) that is eventually bounded away from any
(computable) real number. Because of this sequence, the least upper bound
principle is not only unprovable, it is demonstrably false, as is the theorem
that a continuous function on a compact interval is uniformly continuous. This
gives the subject quite a different flavor from bare-bones intuitionism, or
Bishop-style constructive mathematics, in which no classical theorem is
refutable and every proof can be read as a classical proof. Another surprise
is Ceitin's theorem that every function that is defined for all real
numbers is continuous, which is also a theorem in full-blown intuitionism for
The standard examples of discontinuous functions turn out not to be defined
everywhere from a computational point of view. If the function f that is 0
on (-¥,0] and 1 on (0,¥) were defined everywhere, then we
could use it to decide, for any real number a, whether | a|
£0 or | a| >0; that is, we could solve Nonsolvable Problem
3.1. Aberth argues that, in fact, f is not defined at 0. That seems odd
because f(0) is defined to be 0. I would be more inclined to say that f
is defined on (-¥,0]È(0,¥), but not necessarily on
(-¥,¥). That distinction makes sense in the context of
intuitionistic logic because you can't prove that (-¥,0]È
(0,¥)=(-¥,¥) without using some form of the law of excluded
middle. Aberth, who subscribes to classical logic, has difficulty
distinguishing between (-¥,0]È(0,¥) and (-¥,¥) , so
if f is defined on the former set, then he considers f to be defined everywhere.
Bishop, in his development of Lebesgue measure on the line , uses
functions like f all the time. Why does Bishop believe that f is a
legitimate function? Suppose we want to calculate f(a) for a in
(-¥,0]È(0,¥). Because a is in the union, either a is in
(-¥,0] or a is in (0,¥). That's what it means to be in the
union. In the former case, we set f(a)=0, in the latter we set f(a)=1.
This very straightforward argument is hard to reject, but it can be
rejected from Aberth's point of view. The reason is that in order to calculate
f(a), we need more information about a than is provided by a program
Pa that calculates rational approximations to a; we need the
information as to whether a is in (-¥,0] or a is in (0,¥).
For Bishop, that information is available: an element of (-¥
,0]È(0,¥) comes with that information by definition. After all, if we
wanted to show that a was in (-¥,0]È(0,¥), we would
have to supply that information. But the programs that Aberth uses to
calculate f(a) are only allowed to look at the program Pa; they can
accept as input only real numbers, not real numbers that are given as
belonging to some subset. That's a restriction that makes for simpler
programming but less natural mathematics.
Chapters 5 and 12 of the book are devoted to a particular model of computation
in the form of a simple random access machine similar to the RAM of .
Software is included with the book in case you want to simulate this machine
on your PC. These chapters illustrate a few rudimentary ideas of computable
calculus in a concrete computational setting, but the rest of the text can be
read independently of them.
- Aberth, Oliver, Computable analysis, McGraw-Hill 1980.
- Bishop, Errett, Foundations of constructive
analysis, McGraw-Hill 1967.
- Bishop, Errett and Henry Cheng, Constructive
measure theory, AMS Memoirs 116, 1972..
- Heyting, Arend, Some remarks on intuitionism,
Constructivity in mathematics: Proceedings of the colloquium held at
Amsterdam, 1957 (A. Heyting, ed.) 69--71, North-Holland 1959
- Kushner, Boris A., Lectures on constructive
mathematical analysis, 1973, AMS Translations, 60, 1985
- Machtey, Michael and Paul Young, An introduction
to the general theory of algorithms, North-Holland 1978.
- Markov, A. A., The theory of algorithms, 1954,
Israel Program for Scientific Translations 1962
- Pour-El, Marian B. and Jonathan I. Richards,
Computability in analysis and physics, Springer 1989
- Sanin, N. A., Constructive real numbers and
function spaces, 1962, AMS Translations, 21, 1968
- Turing, Alan, M., On computable numbers, with an
application to the Entscheidungsproblem, Proc. London Math. Soc.,
42 (1936/37) 230--265, correction 43 (1937) 544-546.
This document was translated from LATEX by