Beyond chaos: ultimate unpredictability.

Beyond chaos: Ultimate unpredictability

To predict the future course of a dynamical system such as a swinging pendulum, physicists have traditionally counted on solving a suitable equation to find a formula describing the system's position or state at any time. However, many of the equations used to model physical systems do not yield such formulas. In such cases, researchers turn to methods that produce approximate answers, which usually offer only a limited degree of predictability.

Indeed, the course of so-called chaotic dynamical systems depends so sensitively on initial conditions that a prediction's accuracy is strictly limited by the amount of information available. The farther into the future one wants to predict, the more precisely one needs to know the initial conditions.

But for some dynamical systems, the future seems even more clouded. Graduate student Cristopher Moore of Cornell University in Ithaca, N.Y., has constructed a mathematical scheme corresponding to dynamical systems that are, in a sense, more unpredictable than chaotic systems. "Even if the initial conditions are known exactly, virtually any question about their long-term dynamics is undecidable," Moore states in the May 14 PHYSICAL REVIEW LETTERS.

His discovery means that researchers studying physical systems that happen to correspond to such a mathematical scheme would have no way of determining the system's future, not just in the long term but also in the short run. Moreover, the system would behave so irregularly that reliable, statistical measures of its average or overall behavior would be impossible to obtain.

"There isn't a serious physical application for these ideas yet," says Cornell's Philip J. Holmes. Nonetheless, he says, Moore has shown that "a class of mathematical objects, which are used to describe physical systems, can have this property."

One approach to studying dynamical systems involves converting a differential equation or some other complicated mathematical expression into a kind of game played with specific rules for manipulating sequences of symbols or digits--often just zeros and ones. Moore turned that idea on its head by first inventing a new type of game with interesting characteristics, then searching for connections with dynamical systems.

Moore was able to show that his games, which he calls "generalized shifts," correspond to dynamical systems known as iterated maps, which researchers sometimes use to model physical systems. An iterated map represents the results of substituting each of a set of initial values into a mathematical expression, calculating the answer, then substituting that answer back into the original expression to calculate a new answer, and so on.

Moore also demonstrated that, in certain cases, his games are equivalent to abstract models of computation known as Turing machines. "Various properties of Turing machines can therefore be transferred to iterated mappings," Holmes says. "So they [the maps] inherit all the sorts of complexities that Turing machines have--complexities very different from those that one generally has in chaos."

A properly constructed Turing machine, operating under rules that specify its step-by-step behavior, can perform any computation that a computer can do. However, a particular Turing machine might be saddled with a problem that takes an inordinate -- perhaps infinite -- amount of time to solve. For a given initial state, such a machine may never stop once it gets going, and therefore may never come up with an answer.

Chaotic behavior "is unpredictable because our initial description will have small errors, and these errors grow until our prediction is completely off," Moore says. "Turing machines are unpredictable even if the initial conditions are known exactly."

Consequently, if a step in an iterated mapping happened to correspond to a generalized shift that incorporates a Turing machine saddled with an "impossible" problem, researchers would have practically no way of determining what ultimately results from those particular initial conditions. "The best one can do is to simulate the system and see what happens," Moore says. "Thus even the simplest long-term properties of the motion are undecidable."

No one yet knows whether this type of dynamics arises in realistic physical systems. "Normally, you see a phenomenon and you model it," Moore says. "These are [models] in search of a phenomenon."

Although the dynamical systems he has studied appear contrived, they suggest that it may be worth looking for a similar level of complexity in, say, the so-called three-body problem, which concerns the complicated motions of three gravitationally interacting objects.

"It's the kind of question that I have often wondered about and urged other people to wonder about," says Charles H. Bennett of IBM's Thomas J. Watson Research Center in Yorktown Heights, N.Y. "I think this is a significant step along the way to really nailing that down."