How to test the usefulness of computation
for understanding and predicting
BY maRK BRaVERman
real nUMbers are at the center of our mathematical
reasoning about the world around us. Computational
problems, from computing the number π to
predicting an asteroid’s trajectory, all deal with
real numbers. Despite the abundance of inherently
continuous problems, computers are discrete,
finite-precision devices. The need to reason about
computing with real numbers gives rise to the kind of
fascinating challenges explored here.
We are so immersed in numbers in
our daily lives it is difficult to imagine
humans once got by without them.
When numbers were finally introduced in ancient times, they were
used to represent specific quantities (such as commodities, land, and
time); for example “four apples” is
just a convenient way to rephrase “an
apple and an apple and an apple and
an apple”; that is, numbers had algorithmic meaning millennia before
computers and algorithmic thinking
became as pervasive as it is today. The
natural numbers 1, 2, 3, . . . are the
easiest to define and “algorithmize.”
Given enough time (and apples), one
can easily produce a pile with any natural number of apples.
Fractions are not as easy to produce
as whole natural numbers, yet the algorithm for them is fairly straightforward.
To produce 2/3 of an apple, one can
slice an apple into three equal parts,
then take two of them. If one considers positive rational numbers, there is
little divergence between the symbolic
representation of the number and the
algorithm one needs to “construct”
this number out of apples; the number
practically shouts a way to construct it.
These numbers were the ones that populated the world of the ancient Greeks
(in Archimedes's time) who often
viewed numbers and fractions through
the lens of geometry, identifying them
with geometric quantities. In the geometric language, natural numbers are
just integer multiples of the unit inter-
the study of algorithms dealing with real
numbers and functions over the reals
requires extending the reach of traditional
computability theory but is a notable
challenge for mathematicians and
the theory of computation over the
reals can be applied to the study of
computational hardness of dynamical
systems involving a range of natural
and artificial phenomena.
Predicting a system’s long-term
properties is easy in some cases; in
others it can be as hard as trying to
solve the undecidable halting Problem.