Fractals

Euclidean geometry can be extended to account for objects with a fractional dimension. Such objects, known as fractals, come very close to capturing the richness and variety of forms found in nature. Fractals possess structural self-similarity on multiple spatial scales, meaning that a piece of a fractal will often look like the whole. Related to this property is the fact that fractals are extremely compressible in the sense that an algorithm or recipe for the image is far simpler to store than the image itself. This is due to the recursive and/or iterative nature of the fractal algorithm. But since fractals are so closely tied to algorithms, some fractals have the same paradoxical properties as systems that can compute. Chapter 5 introduces some of the basic ideas behind fractal geometry by considering some unusual geometric objects as well as some common stochastic processes found in nature. Chapter 6 focuses on L-systems, which are simple program fragments that can define plantlike and other fractals. Chapter 7 considers fractals that can be defined by linear algebra operators, and Chapter 8 focuses on two special types of nonlinear fractals. This part is concluded by 9, which examines how fractals can be seen as ``nearly simple'' objects by some candidate measures of complexity.

Chaos

Simple motion is rare in nature. It is more common to find highly complicated nonlinear motion due to chaos. Chaotic systems can easily be mistaken for randomness despite the fact that they are always deterministic. Part of the confusion is due to the fact that the future of chaotic systems can be predicted only on very short-term time scales. Chaotic systems possess a form of functional self-similarity that shows itself in fractal strange attractors. This fractal functionality, combined with chaotic unpredictability, is reminiscent of the uncertainty found in computing systems. Chapter 10 introduces the key components of chaotic systems and highlights the properties common to all such systems. Chapter 11 contains a sampling of fractal strange attractors that are generated from chaotic systems. Chapter 12 considers a type of chaos found in producer-consumer systems, and compares and contrasts two very different types of modeling methods. Chapter 13 shows how some of the properties of chaotic systems can be exploited for the purpose of controlling them. Finally, Chapter 14 compares and contrasts chaos to randomness and incomputability.

Complex Systems

Complex systems are things that consist of many similar and simple parts. Often the underlying behavior of any of the parts is easily understood, while the behavior of the system as a whole defies simple explanation. Part of the reason why complex systems can behave in such complicated ways is that some general forms are known to be capable of universal computation. This double-edged result also implies that the future of complex systems cannot be predicted in the general case. By changing the type and form of interactions that exist among the parts of a complex system, the type of global behavior can be varied such that the complex system as a whole can be globally goal-seeking while only local information is passed around by the parts. This means that a collective form of computation can take place without an explicit global algorithm. Chapter 15 introduces a simple and nearly canonical form of a complex system, known as a cellular automaton. Chapter 16 shows how collective systems composed of individual agents can demonstrate self-organized behavior. Chapter 17 reveals how mixtures of competition and cooperation can produce many different and interesting types of behavior that are seen in nature. Chapter 18 illustrates how a collective form of computation can be performed by feedback neural networks with fixed synapses. Finally, Chapter 19 examines how the global form and function of composite objects can be influenced by the parts of the system and the types of interactions permitted.

Adaptation

In the most general sense, adaptation is a feedback process in which external changes in an environment are mirrored by compensatory internal changes in an adaptive system. In the simplest case, an adaptive system may act in a regulatory manner, like a thermostat, so as to maintain some property of the environment at a constant level. An interesting type of adaptation is found in complex systems in which the interactions among the subunits are allowed to change. This process is very similar to a self-modifying program, since the actions of the adaptive unit can affect the environment, which, in turn, feeds information back to the adaptive system. Thus, adaptation can be seen as a computation of the most complex form that emerges through the multiplicity and recursion of simple subunits. This final book part contains examples of adaptation that resemble naturally occurring forms of adaptation. Chapter 20 concentrates on genetic algorithms as methods for solving many different types of problems. Chapter 21 considers classifier systems, which contain a form of adaptation similar to what is found in social systems and immune systems. Chapter 22 shows how artificial neural networks can be used to classify patterns and to learn arbitrary functions. Finally, Chapter 23 considers how models, the phenomena they model, and search methods are all interconnected in a computation-like form of self-reference.