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-2005. All Rights Reserved.