# Universality-Complexity Classes for Partial Differential Equation Systems

This classification applies to continuous, real- or vector-valued systems in which the time derivative has "almost-everywhere zero" characteristics. This means that the influence of the present state at time t on the state at time t+ε is localized. This criterion applies to Reaction-diffusion systems but not if such systems have a global integration term (a term that incorporates a sum, possibly weighted, across the entire domain — an example of a PDE system with a global integration term is seen in the Purwins and Stollenwerk AC gas discharge experiments[3]).

The qualitative descriptions given here are analogous to, and partly based on, those defined by Wolfram [1] for discrete cellular automata.

In the following, w is the width of the system (its largest dimension in space, in dimensionless units), t represents a quantity of time, O() is an expression of approximate magnitude similar to the Big O notation, K is an arbitrary constant.

These classes also apply to one-dimensional continuous real-valued systems; see Gray-Scott reaction-diffusion system in one dimension for some illustrations.

## Class 1

Class 1 systems evolve, within a bounded finite period of time of
order t ≈ O(w^{K}), into a homogeneous state. K depends on the
density of the starting pattern according to some system-specific
measure; for example in the images shown here, the density of blue
spots in the starting pattern is what matters. There can be one or
more homogeneous states for a system, analogous to multiple basins of
attraction for a scalar-valued system.

Examples

K<<1 due to density of starting pattern. This system oscillates in ∂u/∂t for a while, then stops changing.

1.2 Same F and k; K≈1 due to single small localized seed pattern.

## Class 2

Class 2 systems convert localized areas of "input" (initial state) into one of a small set of localized "output" (evolved state) pattern-classes, within a time of order t ≈ O(1). Each localized area of the system evolves into an output pattern more or less independently of what is happening elsewhere. Any given localized input can be characterized in some way that deterministically predicts the resulting output pattern. Details of the characterization depend on the system, but they will generally be "well-behaved", in the sense that is qualitatively similar to "well-behaved" functions that are continuous, continuously-differentiable, and that have a small finite number of singularities or discontinuities. This all means that each localized region of the resulting pattern depends only on the local area of the input pattern: nothing will ever invade from a distant region of the domain (compare to class 2-a below).

After the time of order t ≈ O(1), further evolution of the
system is qualitatively insignificant on timescales of order t ≈
O(K w) although evolution on the order t ≈ O(e^{Kw}) may or
may not be qualitatively different. This means that very slow, but
asymptotically significant, changes may occur. In the example system
shown here, the spots continue to move at a velocity
c≈Ke^{-49d} with K≈0.065 lu tu^{-1}. It takes a
truly immense amount of time (roughly 10^{12} tu by my calculations)
for these 31 solitons to even begin to approximate the final pattern,
which is a hexagonal grid like that seen in one of the class 3-a
examples below, with the individual solitons spread out evenly across
the entire domain.

Example

Spots continue to move with velocity v≈K/t, K is very small.

## Class 2-a

Class 2-a is a subset of class 2 from the Wolfram viewpoint, but
distinct in important ways for continuous-valued systems. They start
out like class 2, but eventually fill the space with a pattern that
then asymptotically approaches a static state. Forming this static
state can take a polynomial long time to form, t ≈ O(w^{K}), with
K≥1. In Gray-Scott and most systems exhibiting systematic growth,
the exponent K is close to 1. An example of K=2 is a system
consisting of a finite number of stripes (worms) that grow from both
ends until filling the space (second example shown).

Another way to think of class 2a is that it combines features of classes 1 and 2. Certain "benign" starting patterns, like the solitons seen in the second example, behave like class 2, but other "cascade-inducing" patterns, like the two types of growing patterns seen here, make it behave like class 1. Unlike class 1, you never get a homogeneous state.

Examples

Exponent K≈1. These spots took about 4000 tu to fill the space.

Exponent K≈2. These two worms took about 1,200,000 tu to fill the space.

## Class 3

Class 3 systems evolve from nearly any starting state into continued, unending spatio-temporal chaos. The state at time t ≈ O(K w) is qualitatively similar to states at all subsequent times. For practical purposes this is like class 2a except that motion and change continue forever.

Example

## Class 3-a

Class 3-a is a subset of class 3 from the Wolfram viewpoint, but distinct in important ways for continuous-valued systems. These start out like class 2, but eventually fill the space with a pattern that then continues to evolve in a long-term unpredictable way. Like the rest of class 3, this continually evolving state is qualitatively similar at all times after the initial filling of space. However, unlike normal class 3 systems, which exhibit "homogeneous chaos", type 3a has a lot of localized stability for fairly significant periods of time — the chaos only covers a small fraction of the space at any given time. In each of the following examples, most of the motion is in the ∂u/∂t component; the spots and stripes seen in the rightmost frames remain for a long time. Spots and bits of stripes die out gradually to be replaced by something new — so if you wait long enough, the entire pattern will change, but that can take a really long time. A significant distinction, and the reason why this is class 3 and not class 2 or 4, is that the rate of change remains constant forever.

Examples

Pattern stops moving, but pulsation in ∂u/∂t continues indefinitely

Stripes slowly change due to occasional localized die-offs

## Class 4

Class 4 systems will usually, but significantly not always, evolve into an essentially unchanging state. However, there is no easy way to predict the evolution in terms of any characterization of the starting state. A substantial fraction of starting states will take a very long time to stop evolving. As with the chaotic (class 3) systems, the fate of a starting pattern varies greatly with very small changes to the starting pattern; unlike class 3 systems, class 4 systems do eventually stop evolving.

The inherent unpredicability of class 4 patterns allows for, but does not guarantee, the possibility that the system is a class 4-a system.

For a second example, that of (F=0.06, k=0.0609), read my paper "Stable localized moving patterns in the 2-D Gray-Scott model" (preprint here). Also check out the extensive catalog of patterns and the general discussion of (F=0.06, k=0.0609) phenomena on this page.

Example

Diversity of growing, stationary, rotating and moving patterns, all either partly or completely stable

## Class 4-a

Class 4-a systems are subject to a "halting problem" like that of computation. This does not necessarily mean that the system is actually capable of universal computation, just that it is subject to a halting problem: There is no way to determine, by looking at the starting pattern, how long it will take to reach a final state (if any), other than simply running a simulation to see how the system evolves.

No example has yet been proven — However, read the paper and links cited in Class 4 above, and if you feel inspired, create your own patterns at these parameter values, to see what is possible!

## Automated Classification

There are a number of issues yet to be overcome before a classification study analogous to that of [1] can be performed.

Defining the Set of Starting Patterns

Wolfram [1] dealing with discrete cellular automata performed an automated statistical analysis and classification of celular automata systems, by automatically generating starting patterns from a universe of possible choices and watching what happens (as measured by certain statistics). As pointed out by others (see [2]) such studies are subject to "finite size effects" resulting from the fact that the automatic measurement must stop at some finite size domain and number of time steps; this problem will also be present in any work on continuous real-valued systems.

In addition to size effects, there is a problem of determining how to cover the set of possible states for a given system. Two principles of the geometry of point sets combine to make things difficult:

- Whereas the universe of starting patterns for discrete cellular
automata on a finite domain is א
_{0}, and such a universe is can usually be shown to be adequate to characterize the system on infinite domains, the universe of starting patterns for a continuous real-valued system, even on finite domains, is א_{2}.

- A universe of א
_{2}starting functions cannot be accurately characterized by any automatic statistical sampling method, unless that method is certified via human intelligence. In general, this is just because no finite set of sample points can come close enough to all of the points in the "space of measure א_{2}". In particular, there is a need to analyze the PDE functions to define equivalency classes for the starting patterns and parameter values and prove that nothing is being missed. In the Gray-Scott system, for example, there are many parameter values at which you won't get anything interesting unless your starting pattern includes regions that fall into both basins of attraction (above and below the blue state created by the saddle-node bifucation). In many cases, this type of analysis is a deep unsolved problem in its own right.

In order to address this, for any systems for which the analysis
problem appears intractable, another option is available: The universe
of initial states can be explicitly defined by a starting pattern
function, and this function can be taken to be a part of the
definition of the system to be classified. If the definition is
precise enough, the universe of possible patterns could be made
finite, or at least brought down to a number (like א_{0}) that can
more comfortably be chracterized by a finite sample set.

For the above examples, this amounts to re-considering the problem for
different types of starting patterns. Consider the two examples shown
above for Class 1. The leftmost image of each example was evolved from
the starting pattern in a very small number of time-steps. A clear
difference is seen — blue background with lots of yellow/orange
spots, versus red background with a single blue spot. The first
represents a starting pattern function that randomly generates a large
number of rectangular spots with random positions. The second is a
starting pattern "function" that always generates the same starting
pattern: a single rectangular spot. Both have superimposed noise, but
for the parameters in question, the noise quickly smooths out and the
large spots ar all that matter. If we consider the initialization
function to be a part of the definition of the system, the first type
of starting pattern would have א_{0} or א_{1} possible forms; the
second starting pattern has 1 (a finite number) of forms. In either
case, getting an accurate statistical measure of the behavior
of the system seems more feasible.

Back to main menu

References

[1] S. Wolfram, Universality and complexity in cellular automata, Physica D: Nonlinear Phenomena 10 (1984) 1-35.

[2] Lawrence Gray, A mathematician looks at Wolfram's new kind of science, Notices of the AMS 50 (2) (2003) 200-211.

[3] Lars Stollenwerk, "Pattern formation in AC gas discharge systems", website of the Institute of Applied Physics, WWU Munster, 2008

[4] Robert Munafo, Stable localized moving patterns in the 2-D Gray-Scott model (2009) available here.

This page was last updated on 2015 Nov 04. s.11