Monday, July 31, 2006

The Adventures of Victoria and Balthazar: An experiment in viral story telling

Someone turned me on to this little micro-wiki editor, TiddlyWiki. When i started playing with it i saw that it could be a really neat device for an idea i had for a story. The editor and story all live inside this html file. Download it (that's a save page as action), open it in a browser, like firefox, and notice the links on the right hand side of the page. Click on The Adventures of Victoria and Balthazar and start having fun. If you feel so inclined, add or change some of the entries and pass it on to a friend or two -- but please also forward or cc me what you've done. Oh, to edit you can sign with the user name VictoriaNBalthazar.

i shouldn't say anything more, but here's a hint: if you follow the last bold link of each "tiddler", starting from The Adventures ..., you'll find a narrative thread.

Friday, July 28, 2006

"we all want to change the world"

i pulled out my 10 string Warr guitar the other night endeavoring to respond to a creative impulse that is coming in loud and clear regarding a pattern in 10/8. The instrument is "set up for cross-handed playing". i could uncross my hands and learn to play it the way it is set up, but it does seem a suboptimal set up for that arrangement. So, i started to think about how i would set up the instrument for uncrossed playing.

i should note that this was in the context of having just seen Jon Catler perform at a microtonal guitar festival, last Saturday. i noticed that his frets did not go all the way across the neck of the guitar, so that some strings had different patterns of frets along the neck. And, then when i started thinking about my right hand playing bass i flashed on the fact that i wanted the frets to run in opposite directions for the left and right hand. That is, in the left hand, the frets are spaced wider apart as you move toward the headstock, while in the right hand the frets are spaced wider apart as you move toward the bridge.

(Editorial insert: obviously, you have to make the right hand side "bridge" be a nut and "nut" be a bridge. i guess that means you have to put the right hand side pick ups between the leftmost end of the frets and the nut. i guess i better draw a picture.)

i conjecture this would more effectively mirror the left-right symmetry in my body and make playing the instrument a lot easier. Does anybody want to sponsor me to get a Warr set up this way and test out the theory? ;-)

Another random incoming impulse for improving the world... how about a paypal interface to the till of my favorite coffee shop. So, as i'm sitting here typing this and realizing i need a quad shot, white chocolate, rice milk mocha, split 3/1 (3 shots caffeinated, one shot decaf), i go to the coffee shop's web page, order and pay for my drink the order appears on the barrista's screen, she makes it, and calls out my name and my drink and i go pick it up from the bar.

If this model works out, you could easily expand it to a large portion of service sector commerce. Out in the distant future of this idea you could imagine a mobile device, like a phone, that could scan the barcodes of on the shelf goods and with a single click, the good is paid for and the "thing" that makes the buzzer go off when you exit the store is deactivated for this good. Surely, surely, someone is working on all of the ideas in this spectrum, but, i think i could build the former and would enjoy seeing it worked out in practice.

i guess the point is that noticing and responding appropriately to the noticing are two different things. i notice too many things to be able to respond to them both actively and effectively, given my resources. So one question is which noticings come with a responsibility? i guess they all do... if i include 'letting go' as an effective response. Then my question becomes something like

...grant me the strength the change the things i can
the serenity to accept the things i can't
and the wisdom to know the difference

A prolegomena to future posts (on economics)

Before i start muttering about Walrasian auctioneers and such i want to ask a question to the mathematically inclined. In quantum mechanics the claim is made that we effectively can interpret the operation bra Operator ket as a probability. This is all well and good and seems to line up with experimentation. But, from the point of view of mathematics there must be a justification of the form "i'm using this theory of probability, and we can interpret this operation in said theory thusly". So, on the basis of which theory of probability can we interpret the operation as giving up a probability? Is it frequentist? Is it Bayesian?

i'm asking this question in a serious spirit of inquiry. i don't want a hand-wavy argument. i want to see the paper where this is argued out in enough detail that i can do the calculations myself. So, if you, theoretical physicist or mathematician or logician, are reading this and know the answer, or know someone who might know, please post a comment with a reference.

Thursday, July 27, 2006

knots, computation, life and space

Well, on Saturday i made breakthrough in travel. Via the wonders of Skype and the graciousness of the conference organizer, Bob Coecke, i presented results on encoding knots as processes in Oxford at the Cats, Kets and Cloisters conference from my home office in Seattle, WA. (Here is an updated version of the slides with many more technical details than i presented at the conference.) There were some technical glitches that made us restart the Skype connection every 5 - 10 mins, and the connection failed to re-establish for the question section. (Bob, posted my email address so that people could mail me questions.) But, despite these inconveniences, i am very hopeful about this way of engaging technically. (In fact, i am currently working with a company that has some technology that could considerably improve this experience.)

i must say that my co-authors have been wonderful! While it is a matter of historical record that i had the original insight, their probing questions, saintly patience with my mathematical ineptitude and diligence and unwillingness to accept anything but highest caliber work has led to a greatly superior offering than what i could have produced on my own. i should also publicly acknowledge the reviewers of 2006's ICALP for pointing out flaws in the way we presented the results in our submission to the conference. i was using the ICALP deadline as a way of forcing myself just to get something written down, and didn't have the highest of expectations for our submission. But, their comments provided a much needed spur to take the presentation of the results to a higher level.

Now, 'knots' and 'computation' make sense in the title of a post about interpreting knots as processes, but why do i mention 'life' and 'space' as well? Well, it turns out that knots are sitting at the confluence of several different lines of research. Another computation angle has Michael Freedman and co using knots to do quantum computation which you can read about at a less technical level in the April 2006 Scientific American article; while biologists are turning to Conway's tangle calculus to reason about folding of genetic material (i'm not as familiar with this line of research as i ought to be, but this might be a starting point); and researchers in (loop) quantum gravity have been making heavy use of knot theory for quite some time. (Check out John Baez's this week's finds to get a sense of what i'm on about.)

Monday, July 17, 2006

First steps toward vlogging...

Well, after exposure to Rocketboom and Ze Frank's, theshow, i was inspired to check out the multimedia tools on the Mac. My family and i put together an experiment in vlogging. i was amazed at how simple it is to create content and publish. Of course, the rub is creating interesting content... Still, there's something about being able to respond to the spontaneous creative impulse that has some freshness and life. Judge for yourself and tell me what you think.

Monday, July 03, 2006

walking from here to heaven

An m4a file (iTunes plays it) of a block chord arrangement.


we can walk from here to heaven * it's as easy as making air into breath * or turing around and just saying yes * i'd like to walk from here to heaven * when we walk from here to heaven * the cracks in the sidewalk are like cracks in the code * and the sobs breaking through will loosen the hold * of all that keeps you from walking to heaven * let's walk from here to heaven * it's the place we've always wanted to go * and we might be surprised by how many have chosen * to walk with us from here to heaven * we can walk from here to heaven * it's as easy as making air into breath * or turing around and just saying yes * i'd like to walk from here to heaven

Sunday, July 02, 2006

On the physical interpretation of sets

Physicality and pedagogy

A few years ago i introduced my twelve year old daughter to the theory of sets. The approach that i took was to make the interpretation as physical as possible. That is to say, we developed a notion of sets as physical containers. This leads naturally to the question of what is contained in those containers. If the answer is that containers are also contained, and one simultaneously maintains the axiom of extensionality -- that sets are equal if they have the same members -- then there is a problem. This is because it is easy to construct sets where the same container appears in two distinct locations. The Von Neumann representations of the natural numbers gives an example at the representation of 2.

Recall that the Von Neuman numeral is defined by the relation

V[n] = { V[n-1],...,V[0] }

so that we can calculate

V[0] = {}
V[1] = { V[0] } = { {} }
V[2] = { V[1], V[0] } = { { {} } , {} }

Notice that in V[2], V[0] shows up in two clearly distinct locations -- inside V[2] and inside V[1] which is also inside V[2]. It is easy to check that V[0], i.e. {} a.k.a. the empty set, has the same elements as the empty set. So, it really is the same container showing up in two distinct locations. This breaks our physical intuitions. Even quantum mechanics doesn't have the same physical object showing up simultaneously in two different places.

Our solution was simple. We decided that sets don't contain sets they contain 'pointers'. We thought of pointers as little slips of paper on which was written an identifier for the set. The set could be redeemed by going with the slip of paper to an authority. This solution allowed us to define all the usual operations like subset, intersection, union and the like. We could do arithmetic with the Von Neumann numerals.

Later, i thought about how this idea might be made explicit in set theory. This line of thought led to a series of developments.

Representing set theories

What i wanted first of all was a methodology for reasoning about set theories. It occurred to me that i could use domain equations -- with EBNF serving as a compact notation for writing such equations -- to write down a recipe for generating the universe of sets. In this formulation we have a very simple equation to capture all the basic universe of a (finite-image version of) the Zermelo-Fraenkel theory of sets

Set ::= { Set* }

This says that a Set is a container bracketed by '{' and '}' containing zero or more Sets. Clearly, this grammar generates {} and { {} } and { {}, { {} } } and all the Von Neumann numerals and many others besides. It automatically respects the foundation axiom; that is, the element-of relation always bottoms out. It won't give infinitely wide sets, either. This can be addressed in a number of ways, but as the short-coming is not really relevant for this discussion i won't mention them, here.

Set theories with quotation

Now, using our methodology how can we modify this basic universe to introduce 'pointers' or 'references'? Here is a simple grammar that does the job.

Set ::= { Quote* }
Quote ::= `Set+'

Like the previous grammar it indicates that a Set is a container bracketed by '{' and '}'. But, unlike the previous grammar it indicates that the containers contain Quotes, not Sets. It goes on the inform us that Quotes are kinds of containers, too. They can contain zero or one Set. Examples of such sets include {}, { `{}' }, { `{ `{}' }' }, { `{}', `{ `{}' }' }, ....

This allows us to build the sort of set theory that my daughter and i were using in our investigations. But, is there anything else of value here?

Sets, quotes and games

One of the first things i observed about this theory is that it has a curious correspondence with games semantics. In particular, we can make the following correspondence.

Opponent question <--> {
Player answer <--> }
Player question <--> `
Opponent answer <--> '

Under this correspondence we have that Sets are winning strategies for opponent while Quotes are winning strategies for player.

Sets, quotes and atoms

Recently, a lot of attention in the programming language semantics community has been focused on set theories with atoms, i.e. set theories in which there are fundamental entities, apart from the empty set, out of which to build sets. One such theory, FM-theory (that's Fraenkel-Mostowski theory), has been used by Gabbay and Pitts and others to great effect (See this paper, for example.). i observe that having 'atom-builders', in the form of quotes, enables accounts of freshness without sacrificing the 'closedness' of ZF set theory. That is, one can still build the universe out of nothing without having to introduce unexplained atoms. In yet other words, the theory is not predicated on a theory of atoms.

Sets, quotes and barbers

In a famous variation of his paradoxical construction, Bertrand Russell described a town in Italy in which the one and only barber (a man himself) shaves exactly those men who do not shave themselves. The question is: who shaves the barber? Since, under these conditions, it is apparent that the barber shaves himself if and only if he does not shave himself, the answer would seem to be that there is no such town.

Of course, this is a whimsical version of the paradox of all the sets that do not contain themselves. Like the barber, there is something strange about this set in that it contains itself if and only if it doesn't contain itself, making us loathe to admit it. There are a number of ways out of the Russellian situation, one of which is to carefully contrain the language of the comprehension defining the set. Notice, that in set theory with quotes you can't form this set because sets do not contain sets! Sets contain pointers.

In fact, it turns out that the key step of a lot of diagonalization-style arguments (from a version of Turing's halting problem to a version of the Cantor construction) become localized to the manner in which quotes are dereferenced. There is no way out of these constructions if the reference/de-reference mechanism provides a certain level of expressiveness. But, localizing the issue to one mechanism seems to have practical benefits.

Now, if you compare these ideas to the footnote at the bottom of the previous entry you will see that we are building toward something.