Replies

It was mighty late when I posted last night and it didn't occur to me that, for the lurkers following this discussion, I was doing a terrible job of communicating - that I ought to explain the terminology and relate it to the examples that you used. Sorry about that! In my layspeak, for lurkers following the discussion:

When Chaitin speaks of randomness he is saying that the string of numbers we are looking at cannot be created by a set of instructions (algorithm) smaller than the numbers themselves. If the string of numbers can arise from an algorithm, it would be algorithmically reducible information.

For instance, if you see a string of 300 numbers that look like "12312312312313123123123123..." you would say that is algorithmically reducible because it can be created in three steps:

For N=1 to 100
X$=X$+"123"
Next N

Various researchers believe the genetic code, which looks something like a string of a limited number of characters, can also be reduced in this fashion.

In the "airplane parts laying around v. assembled aircraft" illustration, the assembly manual is like an algorithm for building the aircraft.

Although I don't wish to venture whether the aircraft is algorithmically reducible under Chaitin, if we were talking about genetics instead of airplanes, that assembly manual would roughly parallel the subject of evolutionary computing. That is a very interesting subject to me, but not the one that has caused my ears to perk.

If the airplane came alive - was self-organizing and reproducing itself with ever increasing diversity and sometimes, complexity - we would be looking for the algorithm whereby it accomplishes it. That's the part that interests me, because (thanks to Nebullis) I now know that the genetics involved have the characteristics of information theory.

That is to say, it works like a software program, remembering the past (database), being able to decide friend or foe (conditionals/symbols) as well as actually doing the deed (process.) In other words, it can be reduced to algorithm.

Wolfram has shown that complex, seemingly random, structures can arise from very simple algorithms. We are trying to sort out the distinction between complex, random, and structure (and perhaps more before we are done.)

There are several interesting examples of self-organizing structures arising "randomly."

The classic example is that of dropping sand grains onto a pile. After the pile gets large, the drop of one grain can cause a few grains to fall or trigger a huge number to fall. Analysis of the structures shows that the grains support each other in intricatly connected filamants. Slightly different initial conditions lead to vastly different structures.

(Based on watching the Cerro Grande Fire from too close.) The distribution of fuel (fir, spruce, pine, piñon, juniper, grass) causes fire to spread "where the fire wants" rather than along predictable lines. The growth patterns depend on mostly wind-blown seeds which randomly arrive on the ground.

Avalanches exhibit such behavior also. The snow forms self-supporting structures similar to those in sandpiles. Small perturbations may make a snow angel or trigger a whole mountainside to collapse.

Capitalist economic structures also form complex structures. Local conditions often dominate the placement of buildings and of what suppliers and customers an enterprise may have. (Designed economies such as the socialist, communist, fascist, Clintonian, etc. don't work as well.)

Whether or not there are truly random occurences in Nature, we may often treat events as random when these events are made up of many small causes. Brownian motion is the easiest example. A particle undergoing Brownian motion is so jumpy that it has no defined velocity. Einstein and Smoluchowski made a great leap forward when they showed that the position not the velocity of the particle was what could be described. (The position moves "randomly" but total displacement is proportional to the square root of the time.)

In one sense: "Probability Is as Probability Does." (me) Any system satisfying Kolmogorov's axioms may be treated probabilisitically. (There are other axiom sets: de Finetti, Khinchine, von Mises [brother of Ludwig], etc.; these also work but the questions are subtly different.) Jon von Plato has a (rather technical) book on the subject.

Several people have looked at "randomly" occuring events to establish how one should deal with things. Nicole d'Oresme (1323-1382) (No, it wasn't a girl's name then.) was interested in the permanence of the solar system and was opposed to the Stationary Earth Theory as accepted at the time. (He later changed his mind.) Oresme showed that if the rotation period of the earth (day) and the revolution about the sun (year) were not comensurable, then eclipses would happen at different spots on the earth. He also pointed out that the sun would never be in the same place over the earth at an equinox. In addition he was of the opinion that non-comensurablilty was more likely than comensurablity. (Comensurable number have a rational ratio.)

Continuing toward modern times, it was shown by several (Kroneker for example) that on a square billards table, if the tangent of the x and y velocity components of a particle were rational, the particle would trace out a periodic pattern. (Reflecting boundary.) If irrational, the paths would be dense. Dense paths allow time averages to be equal to space averages. (von Neumann, Birkoff, etal.) This means that the time spent in a section of the table would be proportional to the area of that section. If one makes a square table with two opposite side replaced by semicircles, even rational velocities lead to dense paths. (Except for those exactly parallel or vertical to the sides.)