Computation Theory Perspectives [2]

Computers not only provide practical tools for mathematical science, but also suggest new conceptual approaches that can be taken. Cellular automata and other models for physical systems can themselves be considered as computational systems, which process information given as initial conditions to yield final state output. One can use ideas from the mathematical theory of computation to develop principles for the overall behaviour of complex physical systems.

One question which can be addressed by computation theory methods is the fundamental basis for experimental mathematics. The outcome of the evolution of a physical system can always be deduced by experimental observation, or by explicit simulation, as in the experimental mathematics method. But there remains the question of whether it is, in principle, always possible to find a short-cut predictive procedure that obviates the need for explicit simulation.

All predictions must be made by some form of computer. But the system itself can be considered as a computer. Effective prediction is only possible if the predicting device can outrun the system itself, essentially by performing a more sophisticated computation. However, there is increasing evidence that many physical systems can act as universal computers, as powerful in their computational capabilities as any computer built from physical components can be. In such cases, the behaviour of the system can indeed in general be found essentially only by explicit simulation: the evolution of the system is ``computationally irreducible''.

[ Figure 4 ] Evolution of a cellular automaton that is thought to be computationally irreducible, so that its outcome can essentially be found only by explicit simulation.

There are in fact many systems, even with rather simple construction, which seem to be computationally irreducible. Cellular automata provide many examples, one of which is shown in figure 4. Conventional theoretical physics has tended to concentrate on computationally reducible systems (such as the two-body problem) for which exact mathematical formulae can be derived. But one suspects that the vast majority of complex systems are computationally irreducible. And for these systems explicit simulation following the experimental mathematics method is not only convenient, but actually necessary as a matter of principle.

As one further example of the application of computation theory to physics, I mention a problem with which I have recently been concerned: What are the basic mathematical mechanisms for the apparent randomness in such phenomena as turbulent fluid flow? One theory is that random behaviour results from amplification of external noise introduced through boundary conditions or thermal fluctuations. Another related possibility, extensively investigated in dynamical systems theory, is that the flow is sensitively dependent on in its initial conditions. Most arbitrarily-chosen initial conditions, it is argued, involve real numbers whose digit sequences are random, and are progressively ``excavate'' by the evolution of the system. However, as examples of cellular automata (such as those of figure 3) clearly show, very complicated and seemingly random behaviour can be generated even with simple initial conditions. This phenomenon is analogous to the process of pseudorandom number generation, in which a formula applied to a simple seed produces a sequence of apparently random digits. It is indeed common for a comparatively simple mathematical process to yield a sequence that seems random; the digits of or are examples.

In general one suspects that the evolution of many complex physical systems corresponds to a sufficiently sophisticated computation that it ``encrypts'' the initial conditions to produce output indistinguishable from random, at least in practical physics experiments. The phenomenon of turbulence could then be understood in computation theory terms.

previous  l  next