|
|
 |
Articles |  |
|
General Physics |  |
 |
Undecidability and Intractability in Theoretical Physics (1985) |  | |
|
|||||||||
There is a close correspondence between physical processes and computations. On one hand, theoretical models describe physical processes by computations that transform initial data according to algorithms representing physical laws. And on the other hand, computers themselves are physical systems, obeying physical laws. This paper explores some fundamental consequences of this correspondence.[1]
The behavior of a physical system may always be calculated by simulating explicitly each step in its evolution. Much of theoretical physics has, however, been concerned with devising shorter methods of calculation that reproduce the outcome without tracing each step. Such shortcuts can be made if the computations used in the calculation are more sophisticated than those that the physical system can itself perform. Any computations must, however, be carried out on a computer. But the computer is itself an example of a physical system. And it can determine the outcome of its own evolution only by explicitly following it through: No shortcut is possible. Such computational irreducibility occurs whenever a physical system can act as a computer. The behavior of the system can be found only by direct simulation or observation: No general predictive procedure is possible. Computational irreducibility is common among the systems investigated in mathematics and computation theory.[2] This paper suggests that it is also common in theoretical physics. Computational reducibility may well be the exception rather than the rule: Most physical questions may be answerable only through irreducible amounts of computation. Those that concern idealized limits of infinite time, volume, or numerical precision can require arbitrarily long computations, and so be formally undecidable.
A diverse set of systems are known to be equivalent in their computational capabilities, in that particular forms of one system can emulate any of the others. Standard digital computers are one example of such ``universal computers'': With fixed intrinsic instructions, different initial states or programs can be devised to simulate different systems. Some other examples are Turing machines, string transformation systems, recursively defined functions, and Diophantine equations.[2] One expects in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, so that they can simulate any physical system.[3] This is the case if in all physical systems there is a finite density of information, which can be transmitted only at a finite rate in a finite-dimensional space.[4] No physically implementable procedure could then shortcut a computationally irreducible process.
Different physically realizable universal computers appear to require the same order of magnitude times and information storage capacities to solve particular classes of finite problems.[5] One computer may be constructed so that in a single step it carries out the equivalent of two steps on another computer. However, when the amount of information
specifying an instance of a problem becomes large, different computers use resources that differ only by polynomials in
, are those such as arithmetical ones taking a time polynomial in
, so that PSPACE-complete problems cannot be solved in polynomial time. A final class of problems, denoted NP, consist in identifying, among an exponentially large collection of objects, those with some particular, easily testable property. An example would be to find an
-digit integer that divides a given
-digit number exactly. A particular candidate divisor, guessed nondeterministically, can be tested in polynomial time, but a systematic solution may require almost all
possible candidates to be tested. A computer that could follow arbitrarily many computational paths in parallel could solve such problems in polynomial time. For actual computers that allow only boundedly many paths, it is suspected that no general polynomial time solution is possible.[5] Nevertheless, in the infinite time limit, parallel paths are irrelevant, and a computer that solves NP-complete problems is equivalent to other universal computers.[6]
Seven examples of patterns generated by repeated application of various simple cellular automaton rules. The last four are probably computationally irreducible, and can be found only by direct simulation.
The structure of a system need not be complicated for its behavior to be highly complex, corresponding to a complicated computation. Computational irreducibility may thus be widespread even among systems with simple construction. Cellular automata (CA)[7] provide an example. A CA consists of a lattice of sites, each with
possible values, and each updated in time steps by a deterministic rule depending on a neighborhood of
sites. CA serve as discrete approximations to partial differential equations, and provide models for a wide variety of natural systems. Figure 1 shows typical examples of their behavior. Some rules give periodic patterns, and the outcome after many steps can be predicted without following each intermediate step. Many rules, however, give complex patterns for which no predictive procedure is evident. Some CA are in fact known to be capable of universal computation, so that their evolution must be computationally irreducible. The simplest cases proved have
and
in one dimension,[8] or
and
in two dimensions.[9] It is strongly suspected that ``class-4'' CA are generically capable of universal computation: There are such CA with
,
,
Computationally, irreducibility may occur in systems that are not full universal computers. For inability to perform, specific computations need not allow all computations to be shortcut. Though class-3 CA and other chaotic systems may not be universal computers, most of them are expected to be computationally irreducible, so that the solution of problems concerning their behavior requires irreducible amounts of computation.
As a first example consider finding the value of a site in a CA after
steps of evolution from a finite initial seed, as illustrated in Fig. 1. The problem is specified by giving the seed and the CA rule, together with the
digits of
necessary to input this specification. However, the evolution of a universal computer CA for a polynomial in
: exponentially longer than for the first two in Fig. 1.
One may ask whether the pattern generated by evolution with a CA rule from a particular seed will grow forever, or will eventually die out.[11] If the evolution is computationally irreducible, then an arbitrarily long computation may be needed to answer this question. One may determine by explicit simulation whether the pattern dies out after any specified number of steps, but there is no upper bound on the time needed to find out its ultimate fate.[12] Simple criteria may be given for particular cases, but computational irreducibility implies that no shortcut is possible in general. The infinite-time limiting behavior is formally undecidable: No finite mathematical or computational process can reproduce the infinite CA evolution.
The fate of a pattern in a CA with a finite total number of sites
can always be determined in at most
steps. However, if the CA is a universal computer, then the problem is PSPACE-complete, and so presumably cannot be solved in a time polynomial in
One may consider CA evolution not only from finite seeds, but also from initial states with all infinitely many sites chosen arbitrarily. The value
of a site after many time steps
initial site values, where
is the rate of information transmission (essentially Lyapunov exponent) in the CA.[9] In class-1 and -2 CA, information remains localized, so that
, and
, and
The global dynamics of CA are determined by the possible states reached in their evolution. To characterize such states one may ask whether a particular string of
) initial string. Since candidate initial strings can be tested in
candidate initial strings.[15] In the limit
, it is in general undecidable whether particular strings can appear.[16] As a consequence, the entropy or dimension of the limiting set of CA configurations is in general not finitely computable.
Formal languages describe sets of states generated by CA.[17] The set that appears after
nodes. If, indeed, the length of computation to determine whether a string can occur increases exponentially with
should also increase exponentially, in agreement with empirical data on certain class-3 CA,[17] and reflecting the ``irreducible computational work'' achieved by their evolution.
Irreducible computations may be required not only to determine the outcome of evolution through time, but also to find possible arrangements of a system in space. For example, whether an
patch of site values occurs after just one step in a two-dimensional CA is in general NP-complete.[18] To determine whether there is any complete infinite configuration that satisfies a particular predicate (such as being invariant under the CA rule) is in general undecidable[18]: It is equivalent to finding the infinite-time behavior of a universal computer that lays down each row on the lattice in turn.
There are many physical systems in which it is known to be possible to construct universal computers. Apart from those modeled by CA, some examples are electric circuits, hard-sphere gases with obstructions, and networks of chemical reactions.[19] The evolution of these systems is in general computationally irreducible, and so suffers from undecidable and intractable problems. Nevertheless, the constructions used to find universal computers in these systems are arcane, and if computationally complex problems occurred only there, they would be rare. It is the thesis of this paper that such problems are in fact common.[20] Certainly there are many systems whose properties are in practice studied only by explicit simulation or exhaustive search: Few computational shortcuts (often stated in terms of invariant quantities) are known.
Many complex or chaotic dynamical systems are expected to be computationally irreducible, and their behavior effectively found only by explicit simulation. Just as it is undecidable whether a particular initial state in a CA leads to unbounded growth, to self-replication, or has some other outcome, so it may be undecidable whether a particular solution to a differential equation (studied say with symbolic dynamics) even enters a certain region of phase space, and whether, say, a certain
Computationally complex problems can arise in finding eigenvalues or extremal states in physical systems. The minimum energy conformation for a polymer is in general NP-complete with respect to its length.[21] Finding a configuration below a specified energy in a spin-glass with particular couplings is similarly NP-complete.[22] Whenever the stationary state of a physical system such as this can be found only by lengthy computation, the dynamic physical processes that lead to it must take a correspondingly long time.[5]
Global properties of some models for physical systems may be undecidable in the infinite-size limit (like those for two-dimensional CA). An example is whether a particular generalized Ising model (or stochastic multidimensional CA[23]) exhibits a phase transition.
Quantum and statistical mechanics involve sums over possibly infinite sets of configurations in systems. To derive finite formulas one must use finite specifications for these sets. But it may be undecidable whether two finite specifications yield equivalent configurations. So, for example, it is undecidable whether two finitely specified four-manifolds or solutions to the Einstein equations are equivalent (under coordinate reparametrization).[24] A theoretical model may be considered as a finite specification of the possible behavior of a system. One may ask for example whether the consequences of two models are identical in all circumstances, so that the models are equivalent. If the models involve computations more complicated than those that can be carried out by a computer with a fixed finite number of states (regular language), this question is in general undecidable. Similarly, it is undecidable what is the simplest such model that describes a given set of empirical data.[25]
This paper has suggested that many physical systems are computationally irreducible, so that their own evolution is effectively the most efficient procedure for determining their future. As a consequence, many questions about these systems can be answered only by very lengthy or potentially infinite computations. But some questions answerable by simpler computations may still be formulated.
This work was supported in part by the U. S. Office of Naval Research under Contract No. N00014-80-C-0657. I am grateful for discussions with many people, particularly C. Bennett, G. Chaitin, R. Feynman, E. Fredkin, D. Hillis, L. Hurd, J. Milnor, N. Packard, M. Perry, R. Shaw, K. Steiglitz, W. Thurston, and L. Yaffe.
Previous section | Next section
Send comments or suggestions about this site to comments@stephenwolfram.com.
Site created 1996; updated 2001. © 2002 Stephen Wolfram, LLC
