Complexity: A Guided Tour

Whew, this might be getting a bit confusing. I hope you are following me so far. This is the point in every Theory of Computation course at which students either throw up their hands and say "I can't get my mind around this stuff!" or clap their hands and say "I love this stuff!" Needless to say, I was the second kind of student, even though I shared the confusion of the first.

This statement is not provable.” Think about it for a minute. It’s a strange statement, since it talks about itself—in fact, it asserts that it is not provable. Let’s call this statement “Statement A.” Now, suppose Statement A could indeed be proved. But then it would be false (since it states that it cannot be proved). That would mean a false statement could be proved—arithmetic would be inconsistent. Okay, let’s assume the opposite, that Statement A cannot be proved. That would mean that Statement A is true (because it asserts that it cannot be proved), but then there is a true statement that cannot be proved—arithmetic would be incomplete. Ergo, arithmetic is either inconsistent or incomplete.

complex system: a system in which large networks of components with no central control and simple rules of operation give rise to complex collective behavior, sophisticated information processing, and adaptation via learning or evolution.

Linearity is a reductionist’s dream, and nonlinearity can sometimes be a reductionist’s nightmare. Understanding the distinction between linearity and nonlinearity is very important and worthwhile. To

As the nineteenth-century philosopher Henry David Thoreau put it, “All perception of truth is the detection of an analogy.

In short, what Brown, Enquist, and West are saying is that evolution structured our circulatory systems as fractal networks to approximate a “fourth dimension” so as to make our metabolisms more efficient. As West, Brown, and Enquist put it, “Although living things occupy a three-dimensional space, their internal physiology and anatomy operate as if they were four-dimensional … Fractal geometry has literally given life an added dimension.

Turing’s first goal was to make very concrete this notion of definite procedure. The idea is that, given a particular problem to solve, you can construct a definite procedure for solving it by designing a Turing machine that solves it. Turing machines were put forth as the definition of “definite procedure,” hitherto a vague and ill-defined notion.

idea models—models that are simple enough to study via mathematics or computers but that nonetheless capture fundamental properties of natural complex systems.

Tony Rothman points out, “Why the second law should distinguish between past and future while all the other laws of nature do not is perhaps the greatest mystery in physics.

Information, as narrowly defined by Shannon, concerns the predictability of a message source. In the real world, however, information is something that is analyzed for meaning, that is remembered and combined with other information, and that produces results or actions. In short, information is processed via computation.

reached. In dynamical systems theory, each of these abrupt period doublings is called a bifurcation. This succession of bifurcations culminating in chaos has been called the “period doubling route