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.