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.