The computational beauty of nature

In this book, Gary William Flake develops in depth the simple idea that recurrent rules can produce rich and complicated behaviors. Distinguishing "agents" (e.g., molecules, cells, animals, and species) from their interactions (e.g., chemical reactions, immune system responses, sexual reproduction, and evolution), Flake argues that it is the computational properties of interactions that account for much of what we think of as "beautiful" and "interesting." From this basic thesis, Flake explores what he considers to be today' four most interesting computational topics: fractals, chaos, complex systems, and adaptation.

Each of the book' parts can be read independently, enabling even the casual reader to understand and work with the basic equations and programs. Yet the parts are bound together by the theme of the computer as a laboratory and a metaphor for understanding the universe. The inspired reader will experiment further with the ideas presented to create fractal landscapes, chaotic systems, artificial life forms, genetic algorithms, and artificial neural networks.

Read more about Gary' work, plus get source code and errata from this book at http://mitpress.mit.edu/books/FLAOH/cbnhtml/.

Table of contents

Preface

1 Introduction

Part I Computation

2 Number Systems and Infinity

2.1 Introduction to Number Properties

2.2 Counting Numbers

2.3 Rational Numbers

2.4 Irrational Numbers

2.5 Further Reading

3 Computability and Incomputability

3.1 Godelization

3.2 Models of Computation

3.3 Lisp and Stutter

3.4 Equivalence and Time Complexity

3.5 Universal Computation and Decision Problems

3.6 Incomputability

3.7 Number Sets Revisited

3.8 Further Reading

4 Postscript: Computation

4.1 Godel's Incompleteness Result

4.2 Incompleteness versus Incomputability

4.3 Discrete versus Continuous

4.4 Incomputability versus Computability

4.5 Further Reading

Part II Fractals

5 Self-Similarity and Fractal Geometry

5.1 The Cantor Set

5.2 The Koch Curve

5.3 The Peano Curve

5.4 Fractional Dimensions

5.5 Random Fractals in Nature and Brownian Motion

5.6 Further Exploration

5.7 Further Reading

6 L-Systems and Fractal Growth

6.1 Production Systems

6.2 Turtle Graphics

6.3 Further Exploration

6.4 Further Reading

7 Affine Transformation Fractals

7.1 A Review of Linear Algebra

7.2 Composing Affine Linear Operations

7.3 The Multiple Reduction Copy Machine Algorithm

7.4 Iterated Functional Systems

7.5 Further Exploration

7.6 Further Reading

8 The Mandelbrot Set and Julia Sets

8.1 Iterative Dynamical Systems

8.2 Complex Numbers

8.3 The Mandelbrot Set

8.4 The M-Set and Computablity

8.5 The M-Set as the Master Julia Set

8.6 Other Mysteries of the M-Set

8.7 Further Exploration

8.8 Further Reading

9 Postscript: Fractals

9.1 Algorithmic Regularity as Simplicity

9.2 Stochastic Irregularity as Simplicity

9.3 Effective Complexity

9.4 Further Reading

Part III Chaos

10 Nonlinear Dynamics in Simple Maps

10.1 The Logistic Map

10.2 Stability and Instability

10.3 Bifurcations and Universality

10.4 Prediction, Layered Pastry, and Information Loss

10.5 The Shadowing Lemma

10.6 Characteristics of Chaos

10.7 Further Exploration

10.8 Further Reading

11 Strange Attractors

11.1 The Henon Attractor

11.2 A Brief Introduction to Calculus

11.3 The Lorenz Attractor

11.4 The Mackey-Glass System

11.5 Further Exploration

11.6 Further Reading

12 Producer-Consumer Dynamics

12.1 Producer-Consumer Interactions

12.2 Predator-Prey Systems

12.3 Generalized Lotka-Volterra Systems

12.4 Individual-Based Ecology

12.5 Unifying Themes

12.6 Further Exploration

12.7 Further Reading

13 Controlling Chaos

13.1 Taylor Expansions

13.2 Vector Calculus

13.3 Inner and Outer Vector Product

13.4 Eigenvectors, Eigenvalues, and Basis

13.5 OGY Control

13.6 Controlling the Henon Map

13.7 Further Exploration

13.8 Further Reading

14 Postscript: Chaos

14.1 Chaos and Randomness

14.2 Randomness and Incomputability

14.3 Incomputability and Chaos

14.4 Further Reading

Part IV Complex Systems

15 Cellular Automata

15.1 One-Dimensional CA

15.2 Wolfram's CA Classification

15.3 Langton's Lambda Parameter

15.4 Conway's Game of Life

15.5 Natural CA-like Phenomena

15.6 Further Exploration

15.7 Further Reading

16 Autonomous Agents and Self-Organization

16.1 Termites

16.2 Virtual Ants

16.3 Flocks, Herds, and Schools

16.4 Unifying Themes

16.5 Further Exploration

16.6 Further Reading

17 Competition and Cooperation

17.1 Game Theory and Zero-Sum Games

17.2 Nonzero-Sum Games and Dilemmas

17.3 Iterated Prisoner's Dilemma

17.4 Stable Strategies and Other Considerations

17.5 Ecological and Spatial Worlds

17.6 Final Thoughts

17.7 Further Exploration

17.8 Further Reading

18 Natural and Analog Computation

18.1 Artificial Neural Networks

18.2 Associative Memory and Hebbian Learning

18.3 Recalling Letters

18.4 Hopfield Networks and Cost Optimization

18.5 Unifying Themes

18.6 Further Exploration

18.7 Further Reading

19 Postscript: Complex Systems

19.1 Phase Transitions in Networks

19.2 Phase Transitions in Computation

19.3 Phase Transitions and Criticality

19.4 Further Reading

Part V Adaptation

20 Genetics and Evolution

20.1 Biological Adaptation

20.2 Heredity as Motivation for Simulated Evolution

20.3 Details of a Genetic Algorithm

20.4 A Sampling of GA Encodings

20.5 Schemata and Implicit Parallelism

20.6 Other Evolutionary Inspirations

20.7 Unifying Themes

20.8 Further Explorations

20.9 Further Reading

21 Classifier Systems

21.1 Feedback and Control

21.2 Production, Expert, and Classifier Systems

21.3 The Zeroth Level Classifier System

21.4 Experiments with ZCS

21.5 Further Exploration

21.6 Further Reading

22 Neural Networks and Learning

22.1 Pattern Classification and the Perceptron

22.2 Linear Inseparability

22.3 Multilayer Perceptrons

22.4 Backpropagation

22.5 Function Approximation

22.6 Internal Representations

22.7 Other Applications

22.8 Unifying Themes

22.9 Further Exploration

22.10 Further Reading

23 Postscript: Adaptation

23.1 Models and Search Methods

23.2 Search Methods and Environments

23.3 Environments and Models

23.4 Adaptation and Computation

23.5 Further Reading

Epilogue

24 Duality and Dichotomy

24.1 Web of Connections

24.2 Interfaces to Hierarchies

24.3 Limitations on Knowledge

Source Code Notes

Glossary

Bibliography

Index