This post ties in with the Interaction and Introspection youtube series i'm working on.
Back in 1998 i posed the following question to myself: what would the π-calculus formulation of the paradoxical combinator look like? At the time i was looking for a direct intuitive formulation -- which i found in 2003. In retrospect, i realized recently that there is -- of course -- another way to obtain a version in a concurrency setting: take Sangiorgi's translation of the lambda calculus into the π-calculus and apply it to the term: Y = λf·(λx·f (x x)) (λx·f (x x)). i haven't taken the opportunity to do this calculation, yet; but i am looking forward to it.
For folks to whom the words π-calculus and paradoxical combinator are opaque, let me just say that in modern times a small but growing community has been interested in what it means to compute. Various proposals have been put on the table. Two stand out as very interesting, one is the λ-calculus and the other is the π-calculus. At one point in the history of this discussion the existence of the 'paradoxical' combinator was thought to put into question the internal or self-consistency of the λ-calculus proposal. It apparently did magical things: hence the name. Later it was discovered that this behavior was not only perfectly consistent and reasonable, but actually very useful. It's behavior has a lot to do with recursion, replication and reproduction. Also, as a point of historical contact, i should mention that i'm not the only one to think about the biological import of these proposals. Greg Chaitin makes some very interesting observations about certain λ-terms as essentially having biological interpretations. A lot of other folks have also been thinking about this, as well -- in fact it's become a sort of cottage industry. The view, here, however is entirely my own, and the mistakes -- whatever they may be -- are mine alone.
When i found the formulation of the paradoxical combinator i was looking for i noticed something very interesting. It is remarkably reminiscent of biological reproduction. Moreover, it suggested a very intriguing set of ideas regarding what i call strategies of persistence. i don't want to get too far from the main point of this post, but rather flag a point to elaborate later.
Essentially, the question is: how does a behavior persist in time? In the mobile process calculi what we mean by this question is how do we find a copy of this behavior after we have interacted with it. In the ordinary physical world we are used to ordinary objects remaining after we have looked at them. Yet, physics suggests to us that even looking at an object is really a complex process of interactions. A stream of photons from a light source strike the object and some of them are reflected in the direction of our eyes. The point is that after interacting with the photons, the object remains the same. This need not be the case for all interactions between the object and light. If we aim a laser at a coffee table, we might reasonably expect -- for an appropriately powerful laser -- that the coffee table might get scored with burn marks. In this case the object has not survived the interaction essentially unchanged. So, the question is can we formulate a notion of persistence of behavior at a something like the level of abstraction we see in the mobile process calculi that allows us to think about these issues in more detail? For -- once we begin down this path -- we recognize that there are lots of different means of persistence available.
One very noticeable one is 'perfect copy'. This is what looking at the coffee table appears to have. We look at the table and it seems to be exactly the same from one observation to the next. i submit that the machinery of our neurological system is deeply wedded with a relatively faithful abstraction of this process that 'believes' the table to be the same after each observation. Moreover, physics also embodies a notion of 'perfect' copy in the fungibility of subatomic particles. Photons are all perfect copies of one another. When you think about this for more than 10 seconds, it seems very strange. As a point of comparison, in the abstraction of monetary exchange a dollar bill is fungible -- one intact dollar bill is as good as any other for the act of purchasing an apple -- but no child will fail to notice the actual physical difference between a freshly minted bill and a folded, crumpled bill near the end of its life in circulation. In fact the US Treasury also needs to make these distinctions for the practical purposes of maintaining physically serviceable currency. In fact, each bill is actually given a uniquely identifying serial number. i suggest that -- when scrutinized -- the issues of identity, resources and persistence raise a whole host of interesting questions that have physical significance that actually impact our formulation of physical theories.
At the other end of the spectrum of we have sexual reproduction -- which is also about persistence. This strategy for achieving duration is very different, however. Unlike a photon (the information content of) which is indestructible, sexually reproducing organisms are marked by destructibility, their ephemeral nature. 'All flesh is grass' is the phrase that comes to mind. Further, this strategy for persistence admits -- in fact depends upon -- a little noise, a little grit. There's nothing perfect about the copying this process produces. We can compare these two processes by observing that one -- perfect copy -- results in an indestructible entity that can never change -- once copying is perfect, the entity achieves static immortality -- while the other results in a more dynamic form of persistence. Evolution will -- in the presence of reasonably stable environments -- find excellent adaptations, and keep improving them.
Now, what this post is about is that the mathematical formulation of the π-calculus version of the paradoxical combinator allows one to express both these forms of persistence -- and a whole domain of others. As a way into to this domain i want to explore what is necessary to transform our expression of perfect copy into an expression more closely resembling sexual reproduction. To begin with we need a reflective variant of the π-calculus that i call the rho-calculus (reflective higher-order calculus). The literature gives the moniker 'rho' to another calculus, but i think this calculus has better claim to the name, so i'm sticking by it.
The posts below address presentations of the grammars of these calculi and express the perfect copy form of a version of replication and then make some suggestive observations about how we might decompose this formulation in a way that allows us to transform it into a form that captures an essentially sexual reproduction. In subsequent posts i will lay out the mathematics for this.
Functional Equations VII: The p-Norms
5 days ago