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
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
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
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.
The Creative Computer, Donald Michie and Rory Johnston,
Jeffrey Johnson is a research fellow at the Centre for
Configurational Studies, The Open