COMPUTING SETS A NEW MATHS
 |
| Von Koch's snowflake: when its border is infinite, its area is equal to that of a circle drawn around the original triangle. |
Mathematicians helped to establish computer science, but it is now bringing revolution to their own subject. Jeffrey Johnson looks at its dramatic contribution.
Many mathematicians appear in the history computing include
Charles Babbage, who designed a true forerunner of the modern digital
computer in the 1830s (this is finally being built for an exhibition at the
Science Museum in London).
In the 1930s Alan Turing
defined the abstract Turing Machine which
clarified the concepts of computability and universality in computation.
John von Neumann extended these ideas to develop the phenomenally
successful sequential architecture found in most of today's computers.
What is not generally realised is the turbulent change that
computers bring to mathematics itself. With their capacity for crunching
through vast numbers of equations, examining millions of possibilities, and
the use of graphics to give new conceptual insights, mathematicians are coming
to use computers as essential tools. Some mathematicians, however, believe
that this compromises the nature of their subject or undermines its fundamental
values.
For instance, in 1976 Kenneth Appel
and Wolfgang Haken proved the notorious Four
Colour Theorem. This says that four colours are sufficient to
colour any map in such a way that no two
adjacent areas are the same colour. Since 1852 many great mathematicians
had tried and failed to prove it, and the announcement that a correct proof
had been found caused great excitement. To many mathematicians, however,
the victory seemed hollow: the proof required
the use of a computer! An IBM 360 had played a crucial role by
computing many thousands of cases, and mathematicians
were left wondering what really constitutes a proof.
No human can check the calculations but most mathematicians
accept it as valid, even though it requires an act of faith that the
computer has not made an error. Despite these difficulties at the foundations
of their subject, 20th century mathematicians are being extraordinarily creative.
In their book The creative computer, Donald Michie and Rory Johnston
say, "It has long been wrongly assumed that you can get out of a computer
what you put into it ... Now, however, it has been demonstrated incontrovertibly
that something new can come out of computers, and that something is
knowledge. That knowledge, in turn, can be original ideas, strategies
and solutions to real problems."
Nowhere is this more true than in mathematics. Computing is
creating a new form of experimental mathematics, generating new mathematical
structures and problems and allowing new ways of modelling complex systems
through databases and computation.
Fractal geometry is one of the best known branches of new mathematics nurtured
by computing. Its antecedents include the snowflake described by the Swedish
mathematician Helge von Koch in 1904. This can
be formed from a simple triangle by repeated "self-similar" operations on
the edges. Eventually the border of the snowflake can be proved mathematically
to have infinite length, but the snowflake has a finite area equal to that
of a circle drawn around the original triangle.
Benoit Mandelbrot, IBM research fellow and the
father of fractals, puts them in the historical perspective of what he calls
a crisis in mathematics, prompted by the work of Giuseppe Peano.
 |
 |
| A finite approximation to the Peano curve (left): as construction proceeds, the edges get smaller and the square is filled. Above : the Mandelbrot Set, in which constants giving convergent behaviour in his iterative formula lie within a beetle - like shape. |
In 1890 Peano defined a curve that is continuous and goes
through every point of a square. Peano's curve allows a point to be specified
by a single number, its distance from the end of the curve. The definition
of dimension as the number of variables required to specify a point became
untenable.
The crisis ended in 1922 when Besicovitch gave the final form to what is
now called the Hausdorff Besicovitch or fractal dimension For a continuous
curve this is related to the fraction of the area of the plane it covers.
Mandelbrot defines a fractal set as one which has
Hausdorff-Besicovitch dimension greater than its topological dimension. The
topological dimension usually corresponds to one's intuitive idea of dimension;
wire is one-dimensional, discs are two-dimensional, blocks are three-dimensional
and so on. The Peano-Hilbert curve has fractal dimension two and,
counter-intuitively, its topological dimension is two.
In 1979 Mandelbrot was experimenting with a single iterative formula: take
a complex number, square it, add a constant, square the result, add the constant
to that, square the result, add the constant to that and so on. Would the
end result diverge to infinity, converge to a fixed number, or have some
intermediate behaviour?
The answer is that the constants giving convergent behaviour lie within the
beetle-like shape known as
the Mandelbrot
Set. The story is even more remarkable, because when the Mandelbrot Set
is computed and displayed on finite computer screens one sees islands which
appear distinct from the main body of the set. However a mathematical theorem
shows they are indeed connected to the main body of the set by what Mandelbrot
calls "devil's polymers".
A related feature of these sets is that of self-similarity;
as the computer zooms in to look at the set in more detail one finds structures
which are similar to structures seen at coarser levels of magnification.
One of the most fashionable branches of mathematics at the moment is the
theory of chaos. Although it is closely related
to fractals and the Mandelbrot Set, chaos was discovered independently
by Edward Lorentz in 1980. He was surprised
to find that changing his starting values very slightly in a
weather simulation resulted in wide divergence
over time. This kind of behaviour is called chaotic. Assuming the equations
are correct it means that very small errors in observation may have dramatic
consequences. This has been described as the Butterfly
Effect - a butterfly stirring its wings today in Peking can form the
storm systems next month in New York.
Yet paradoxically, chaos has structure. The set of points
in which the chaotic trajectory exists is called
a strange
attractor: attractor because the system does not escape from it but strange
because some trajectories are not periodic and because of the way they weave
around each other so intimately.
The computer-enabled mathematics of fractals and chaos may have significant
applications in a new kind of science for modelling complex systems which
have hitherto defied deterministic explanation. Automata
theory is another area rich in interest for mathematics, as illustrated
by John Conway's splendid
Game of Life. Life, in which
generations of coloured pixel configurations uncannily evolve over time,
can be played happily (or obsessively) on a PC.
There has been an amazing shift in mathematics towards becoming
an experimental science. Computer packages now exist to help mathematicians
in their everyday work, rather like the word processor as a tool for writers.
The requirements of computer science have also stimulated new areas of
mathematics. Computer science has come full circle since the days when all
programmers had to know how to write code in
binary.
The recent concern in software engineering for correctness is subjecting
program design and implementation to the same mathematical rigour which underpins
all physical engineering design. Reliability of code which can be demonstrated
and proved is becoming more and more important to the software industry.
The new specification languages such as Z and VDM are very close to mathematics
and are based on mathematical theories .
The nature of metrics in software engineering is another area
receiving attention from mathematicians, as is the idea of program structure.
Apart from all this computing is beginning to have an impact on the teaching
of mathematics. Colourful interactive graphics can bring to life traditionally
dull or dry areas of study, motivate and illustrate complex ideas and reduce
the frustration of incorrect answers through trivial calculation errors.
In the 21st century mathematicians will live happily with their computers:
the amplification of mathematical imagination and brainpower will be as natural
and welcome a part of their lives as blackboard and chalk.