COMPUTING SETS A NEW MATHS

Ad infinitum : The Von Koch Snowflake
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-maze-ing :The Peano Curve The Mandelbrot set:Not as good in monotone
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.


Further Reading

The Creative Computer, Donald Michie and Rory Johnston, Pelican 1985
The Problems of Mathematics, Ian Stewart, Oxford University Press 1987
Mathematics: the New Golden Age, Keith Devin, Penguin Books 1988
The Fractal Geometry of Nature, Benoit Mandelbrot, Freeman 1985
The Science of Fractal Images, Peitgen and Saupe, Springer 1988:
Chaos:Making a New Science , James Gleick, Heinemann 1987
Chaos, Arun Holden, Manchester University Press 1986
The Recursive Universe, William Poundston, Oxford University Press 1987

Author

Jeffrey Johnson is a research fellow at the Centre for Configurational Studies, The Open University.

MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

GLOSSARY

Chaos Quantum Logic Cosmos Conscious Belief Elect. Art Chem. Maths


COMPUTER WEEKLY, March 30,1989 File Info: Created 1/9/2000 Updated 25/5/2001 Page Address: http://www.fortunecity.com/emachines/e11/86/newmath.html