The Computational Beauty of Nature
Computer Explorations of Fractals, Chaos,
Complex Systems, and Adaptation

About the Book
  · title page
  · home*
  · cover artwork
  · jacket text
  · table of contents
  · the author*
  · ordering information
Book Contents
  · three themes
  · part synopses
  · selected excerpts
  · all figures from book
  · quotes from book
  · glossary from book
  · bibliography
  · slide show
Source Code
  · overview &
  · FAQ list*
  · download source code
  · java applets
  · news*
  · reviews & awards
  · errata
  · for educators
  · bibliography (BibTeX format)
  · other links
Three Themes: #2

2. The interesting stuff is in the middle

``Beauty,'' i.e., that which makes something interesting, is related to a mixture of regularity and irregularity. When things are too regular, we usually find them to be uninteresting because they yield no surprises for us. Complementary to this, highly irregular things are often uninteresting because they make no sense. In the middle, between regularity and irregularity, lies a place where things can be understood, but not completely.

This idea is best illustrated with an example that appears in the book (paraphrased from Section 22.6, ``Internal Representations'').

Consider the task of finding a good movie to see. You have at your disposal several movie reviews and some prior knowledge concerning the relative tastes of the individual movie reviewers. Some reviewers seem to like everything ever put on film, so what they say about any movie is useless, in that it tells you nothing at all about whether or not you will like a movie. Other movie reviewers have such complex tastes that you may be hard pressed to ever guess what kind of movie they would like or dislike. However, if you find that your taste in science fiction films is similar to one particular critic's, or that your preferences for comedy films are exactly opposite to those of another critic, then these are both useful pieces of information for you to use when picking a movie.

The key point here is that the usefulness of a movie review depends on the relative complexity of the critic: if he or she is either too simplistic or too complex, then the information they provide is negligible.

We can extend the analogy to partially describe what makes a movie entertaining. Both predictable and random plots or boring. But something in between, that contains both familiarity and surprise, makes a movie fun to watch.

Still not convinced? Then consider music. Very few people enjoy listening to simple scales, no matter how precisely they are played. Nor do people enjoy listening to random beeps. Interestingly, analysis of classical music often reveals a fractal representation for the notes, which gets to the heart of the idea that ``beautiful'' things contain a mixture of regularity and irregularity.

This basic idea, that neat things are at the midpoint between computability (simplicity) and incomputability (randomness) can be extended to just about every conceivable domain. The table below (adapted from a table in Chapter 24) is a partial listing of a broad range of things that seem to fit with this idea.

  Computable Partially Computable Incomputable
Sets recursive RE and CO-RE not RE & not CO-RE
Numbers rational computable irrational incomputable
Programs trivially (never) halt possibly halt ---
Proofs true or false profound statements unprovable
NP-Complete Problems underconstrained critically constrained overconstrained
Deterministic Geometry Euclidean deterministic fractal ---
Stochastic Geometry --- stochastic fractal pure noise
AC compressible possibly incompressible incompressible
Mandelbrot Set white regions border regions black regions
Continuous Dynamics fixed point chaotic high-dimensional chaos or stochastic
Discrete Dynamics regular from over-sampling complex at mid-sampling irregular from under-sampling
Attractors integral dimensions strange infinite dimensional
Mater solid liquid gas
Wolfram CA class I or II class IV class III
Langton's lambda lambda < 1/3 lambda near 1/2 lambda > 2/3
Agent Interactions globally coordinated or always cooperative locally coordinated or cooperative and cooperative uncoordinated or always competitive
NK Nets K = 1 K = 2 2 < K <= N
Sandpiles flat and stable critical tall and unstable
Economics communism free but regulated unrestrained
Governments dictatorial democracy anarchy
Patterns consistent hidden order inconsistent
Models not self-referential coadaptive or recurrent hopelessly self-referential
Search Methods local or greedy hybrid exhaustive
Search Spaces smooth complex structured pathological

Many of the topics listed in the table may not be familiar to you, but most of them are covered in considerable detail in the book. In particular, each book part is concluded with a ``Postscript'' chapter that reviews all of the topics covered in a part as they relate to the ideas from the theory of computation. In this way, it is possible to see how all of these diverse areas relate to the fundamental region between computability and incomputability.

Copyright © Gary William Flake, 1998-2002. All Rights Reserved. Last modified: 30 Nov 2002