Wednesday, May 31, 2006

Origin and reference

This morning a friend sent me a link to an entry in Cosmic Variance (here). One of the points i took away from the entry was this:

Lloyd’s suggested answer, to the extent that I understand it, arises from the classic thought experiment of the randomly typing monkeys. A collection of monkeys, randomly pecking at keyboards, will eventually write the entire text of Hamlet — but it will take an extremely long time, much much longer than the age of the observable universe. For that matter, it will take a very long time to get any “interesting” string of characters. Lloyd argues that the situation is quite different if we allow the monkeys to randomly construct algorithms rather than mere strings of text; in particular, the likelihood that such an algorithm will produce interesting (complex) output is much greater than the chance of randomly generating an interesting string. This phenomenon is easily demonstrated in the context of cellular automata: it’s remarkably easy to find very simple rules for automata that generate extremely complex output from simple starting configurations.
The idea of randomly generating algorithms as a way of jumping the complexity barrier glosses over an essential problem. For even an unwitting generator to express an algorithm, qua algorithm, one must have the notion of reference already in hand. That is, whatever will treat the expression of the algorithm as an expression of an algorithm must have the capability to refer. This is the case even when the code is the machine, the software is the hardware, as it is in physics, chemistry and biology. But, how does this arise in the universe?

With the \rho construction i demonstrate that all that is necessary -- beyond the usual programming constructs of sequence, parallel and synchronization -- to build an endless tower of universes of Turing-complete complexity is the ability to refer to something. But, i don't yet understand how to make the general capability of reference, or even a single instance of a reference, arise out of nothing.

i often think about this in terms of one of Calvino's Cosmicomic stories. The main character, Qfwfq, describes making a single mark in the universe and how both the universe and his relationship to it changes as a result of that mark. Of the many interesting points of contention and convergence that Walter Fontana and i have had, we both agree that finding a way to bootstrap reference is one of the central questions. If i understood his position correctly, Walter has at one time expressed to me the opinion that somewhere between the TCA cycle and the development of RNA a chemical bootstrapping of reference occurs. Certainly, by the time you have a self-replicating structure you have many of the essential characteristics of reference.

This analysis is in part why i am so interested in expanding the equational characterization of quote, as exhibited in the \rho construction, into a more fine-grained specification that satisfies this characterization. The question is: what constructions will serve the function of being the code of a process (the expression of an algorithm)? Pleasantly, this has the added benefit of providing more concrete, and machine-manipulable representations. i have a binary coding for the \rho-calculus. Matthias Radestock has a Goedel numbering. Just this weekend i was thinking about developing a binary encoding based on the trick of ordering HML formulae and then giving binary representations of processes on the basis of the formulae they satify. In the \rho-calculus/namespace logic setting, there's a coinductive relationship between formulae and processes that could be used to order the formulae as the same time it orders the processes. There's something deep here, but the recursion hurts my brain.

Sunday, May 28, 2006

An observation of the creative process

The first spark...

Early last week i found myself in my favorite coffee shop vocalizing a drum riff in 5/4 (actually, i think it was 10/8). It was pretty groovy. i kept some small attention to it during the week.

A shift in thinking...

On Sunday, the day after i abstain for 24 hours from ingesting stimulants, as my espresso began taking effect i noticed a sensation of feeling 'kicked in the head'. i had a general sense of difficulty with analytic thought. This seemed to open up a space for musical ideation.

The space to respond...

A moment of inactivity, or freedom from immediately pressing obligations, presented itself on Sunday and i pulled out my Ghanaian antelop skin hand drum to work out different variations/arrangements of the drum riff that had appeared earlier.

The future pulling the present toward it...?

i should also say that during the week i sensed the possibility of interpreting the essence of the riff as an arpeggio. Something happened with the little ones and the drumming. i can't remember, but i found myself moving to get a stringed instrument.

Who or what makes the choices...?

A moment of choice presented itself because all during the week i could feel double course strings (as in my octave mandolin or my 12-string) under my fingers when i sensed the possibility of this arpeggio. But, when i started down the stairs to my studio i suddenly felt the strings of my Martin under my hands, and this was the instrument i picked up.

Before i had picked it up i had interpreted the essence of the drum tones as specific notes and so had the propulsive arpeggio the of the piece pretty quickly. i remember some difficulty with the second half of the line -- i kept twisting it around and playing the second part first.

One thing leads to another...

Then, i immediately had a middle part. i could hear it and my fingers grabbed it and i had the essence of the part right away.

i remember being called upstairs to attend to something with the kids. On one of the trips up or down some flight of stairs i found myself singing the melody. When i got back downstairs i worked it out on the guitar -- thank god for the 5ths tuning! i needed all that range for this melody.

Weaving between the raindrops...

Stani and the kids and i went out to take my eldest son, Max, back to his mother's house and to get the kids out of the house. i think before that i was able to steal about 10 minutes to enter the notes -- one at a time -- into the free music notation editor, lime, for the arpeggio and middle bit.

When we got back i spent about an hour laboriously notating the melody and balancing it against the timing of the arpeggio and the middle bit. i stopped and put the kids to bed. i remember sitting with my back to the pillow sensing and hearing the beginning notes of the break. Then i put Stani to bed. Then, around midnight, i came down to complete the process.

Image and struggle...

Something interesting happened in the second phase of work. i found the metaphor of the glass slipper and the Cinderella story attaching itself to the voices -- wait -- actually this started when i opened lime for the first time. It wanted me to name the first voice and the image of the glass slipper came up and the first arpeggio was MiceToHorses. Then the middle bit was PumpkinToCarriage. Then when i was notating the melody it was BeforeMidnight.

In the second phase of work this metaphor began to exercise a function and suggested more of the break -- i wanted and was hearing something like a princess entering a ball. i'm sure this all sounds remarkably pedestrian and time-worn. But, the experience was remarkably fresh and free and vivid for me.

There was also a kind of tension going on inside me. When the initial tonal impulses came it was very much from my interpretation of an African -- specifically Malian -- melodic sensibility. i was thinking/feeling/sensing folk music, folk music, folk music -- it's a voice i sense as rising up to the vaulted cathedral of the African sky. Then when the Cinderella images started happening there was this sense of Russian art music of a different century pushing against the sensation of the African voices i was hearing in my head.

Out of this tension grew the transposition from C (really G mixolydian) to C harmonic minor. This transposition was also being connected in my nervous system to the post-midnight Cinderella transformation: the whole horses-back-to-mice-carriage-back-to-pumpkin thing.

Completion... and a chance to begin again...

At the cusp of the decision to leave it ending on the low C of the harmonic minor section i knew that the return to the original figure -- with the arpeggio and middle bit phase shifted -- was the glass slipper finding its way onto the proper foot. This morning i am contemplating the sanctity of wish and how Cinderella tells us a little about the story of wish and the way it works in our lives.

(Email me for a copy of the midi file to hear the composition)

Friday, May 26, 2006

Autumn at the climbing wall

The secret life of space


In his series of books called the Nature of Order, Christopher Alexander makes an argument that life is an objectively measurable property of certain configurations of physical space. In his first book, The Phenomenon of Life, he makes the claim to have mathematically formalized this idea. While i think his formalization falls far short of his claim, i believe that his basic idea has legs, so to speak, and can be given a formalization. Below i sketch out a narrative of the development of some ideas that i believe can achieve the formalization -- and attendant framework for doing calculation and prediction -- of Alexander's notions. Essentially, the idea is to find a computational framework for expressing dynamics so general that it is capable of internalizing both the physics of (quantum) gravity and the formal theories of agency and then to show that the proposals for the physics of gravity -- when viewed computationally -- cause the very fabric of spacetime to be made of computational agents of such complexity that they are capable of the things we typically associate with living agents -- even more with reasoning agents. Spacetime itself is not just alive, it is intelligent.

My working hypothesis is that the process algebras constitute such a computational framework and that the bulk of the work is simply to exhibit the process algebraic representations of (quantum) gravity and various characterizations of agency already in the literature. We know that this must be possible, in principle, for any computationally realizable theory of (quantum) gravity and notions of agency. Why? because the process algebras are computationally complete. Thus, if these theories are to be realized as programs they must be realizable as programs in the process algebra setting. Of course, the same could be said of Turing machines (TMs) or the lambda calculus (LC) or cellular automata (CAs). The reasons for choosing the process algebras are these:

  1. The process algebras give a compositional account of computation (neither TMs nor CAs do -- how do you build a TM/CA out of little TMs/CAs at the level of the theory of TMs/CAs?)
  2. With a compositional account of autonomous and concurrent computation (neither TMs nor LC nor CAs support this)
    1. Note that taken together these two notions (and especially the latter) give rise to a natural interpretation of agency as (autonomous) computation
  3. The process algebras have a well-developed family of logics (the so-called Hennessy-Milner logics) dual to the algebras giving an account of properties of computations and hence collections of computations (correlated by exhibiting such property)
In the discussion below i pursue only the loop approach to quantum gravity. i have serious philosophical and computational concerns about string theory. i will detail these in another entry.

Space as dynamics

This winter i developed an interpretation of spin networks as processes. This builds from my interpretation of knots as processes. The essential idea is that the network can be represented as a process in an algebra built out of names that are elements of compact Lie groups that are associated with the guage-invariance of the particular field being quantized. i am in the process of working with a stellar group of researchers to tighten up and publish the results on knots as processes. From there the spin network results are a very natural extension. However, i have found an even more pleasant presentation of the results in which they are factored into some results about the representations of graphs as processes and then specialized to knots and spin networks. This allows the bulk of the technical results to be qa'd by the process algebra community -- who are arguably the best folks to spot bugs in these results.

Of general interest in these researches is the notion that nothing is static. Or, rather that what we think of as stasis is actually a property of dynamic systems and that all systems in actual world are dynamic systems. If they seem static it is because they exhibit a certain property -- a kind of recursive structure in the description of the computation they realize -- that we recognize as stasis. i will post more on this later.

Epistemology and action

In connection with the last idea, the core intuition here is that to know is to exhibit the ability to do. Even knowing is a kind of dynamics. Last year, in the spring, i began to pursue more seriously some thoughts i'd had regarding how this intuition could be formalized in the relationship between epistemic logics (ELs) and Hennessy-Milner logics (HMLs). The basic intuition was that HMLs were a reasonable candidate for ELs -- in fact better than the home-grown ELs proposed by the community -- because

  • the notion of agent is explicit and compositionally characterized in the process algebra setting;
  • the notion of an agent 'knowing x' could be correlated to having access to a name nx for an agent that has the capability x.
My idea was to pursue this in the reflective framework i was setting up via the \rho-calculus. It is not essential to the core idea, but provides a number of computational advantages. In particular, since names are conflated with the codes of agents in the reflective setting 'knowing x' can now be interpreted directly as knowing a name code(x) which is the code of an agent exhibiting the capability x.

i mentioned some of these ideas to Bob Coecke and Alexandru Baltag in an email exchange. Later, Radu Madare -- whom i knew through my connection with Corrado Priami -- worked with Alexandru. He and Alexandru did some work on epistemic logics. Then Radu considered with Corrado the connection between spatial versions of HMLs and epistemic logics with HMLs -- a consenual validation, imho -- of my intuitions that HMLs make a reasonable -- if not better -- framework for ELs.

Connecting the dots

How do these two lines of research fit together? The key point is that by realizing (quantum) gravitational characterizations of spacetime as processes in the same framework as one can write down properties of agents that believe and know and make statements about their beliefs enables one to check -- computationally -- whether -- or better which of -- the processes of spacetime satisfy properties that characterize conditions of belief and knowledge. This makes good on a part of the proposal. Here is a framework in which one can reason about configurations of spacetime in a way to verify what sort of agency it has.

As to life... well, one of the most interesting aspects of the recent flurry of activity in using process algebras to model biological systems is more abstract characterizations of life. In What is Life? Schroedinger investigates this as a physicist would -- looking for an abstract theoretical framework in which to characterize what we mean when we say life. It is recognized by many that Schroedinger's little essay can be seen as predicting the existence of DNA before it was discovered. Likewise, i think that the process algebraic accounts of biological systems are a step towards finding a more abstract characterization of life that will ultimately be predictive.

In particular, i think we can expect to be able to debate in a very precise way about formulations of the notion of life expressed as properties written in some HML. Such properties can be applied to the processes representing spacetime. We can ask specifically which configurations of space have life. In fact, because there is likely to be considerable debate about which of many properties we want to include in the notion of life we can expect gradations of notions of life. We can ask -- as Alexander does -- which of these configurations exhibits more life -- meaning which configuration satisfies more of the properties we wish to associate with life.

While it is certainly satisfying and exciting to think that the profound intuitions of such a great architect as Christopher Alexander really can be put on firm mathematical footing, i find myself even more intrigued by what happens to my conception of the universe in which i live in the wake of these investigations. It is not just that the very fabric of spacetime comes alive, but that life is foliated onto many levels. Such an account of life as certain kinds of information processing systems -- certain kinds of processes or agents -- enables a view into a world in which everything -- from the internet to pop songs -- comes alive to the degree it is able. Suddenly, i find myself living in a larger, more lively world. This is exciting.