Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

October 23, 2006

This Week’s Finds in Mathematical Physics (Week 240)

Posted by John Baez

In week240 of This Week’s Finds you can learn the value of 00, learn how to play chessgo, and read about Dolan and Trimble’s work on cartesian closed categories and holodeck games:

Posted at October 23, 2006 1:34 AM UTC

TrackBack URL for this Entry:

3 Comments & 0 Trackbacks

Re: This Week’s Finds in Mathematical Physics (Week 240)

I was planning to spend some time this evening writing an account of how Dolan and Trimble’s work fits into the tradition of game semantics, linear logic etc. But I’ve realised I don’t quite understand what Dolan and Trimble are doing. It seems to me that there are some “holodeck strategies” which don’t correspond to elements of the free CCC.

Here’s an example. Sorry it’s so complicated: I’m not sure whether there is a simpler one.

Let α:=X X×X\alpha := X^{X\times X}, and consider the game

α α X α\alpha^{\alpha^{X^\alpha}}

So that I can describe the strategy I have in mind, I’ll draw out the tree and label the moves:

    X   X
   a2\ /b2
      | X    X
     x\ |a1 /b1
         \   X    X
        q1\  |a0 /b0
             | q0

Now consider the following strategy:

q0 q1
q0 q1 a1 a0
q0 q1 b1 b0
q0 q1  x q2
q0 q1  x q2 a2 a0
q0 q1  x q2 b2 b0

(If player 1 plays q0, we play q1; if she then plays a1, we respond at a0, etc.) This is certainly a winning strategy, and I don’t see how it could correspond to any lambda term: the problem is that it exhibits non-local control flow, which isn’t possible in the pure lambda-calculus. In the usual innocent game models, strategies like this are excluded by a “bracketing” restriction, but Dolan and Trimble don’t appear to impose such a restriction.

Perhaps someone could explain where I’ve gone wrong.

Posted by: Robin on October 23, 2006 10:06 PM | Permalink | Reply to this

Re: This Week’s Finds in Mathematical Physics (Week 240)

Never mind, *blush*. I’m just getting confused. I’ve spent too much time thinking about the games for PCF.

The strategy I gave corresponds to the lambda term

λf,a,b.\lambda f,a,b. f((λg.g(a,b)),a,b)f((\lambda g. g(a,b)), a, b).

As you were.

Posted by: Robin on October 23, 2006 10:51 PM | Permalink | Reply to this

Re: This Week’s Finds in Mathematical Physics (Week 240)

These “Holodeck Games” and their strategies feel to me an awful lot like drawing Feynman diagrams for particles constrained to a tree, scattering off of (bad) consequences, and make me think of instantons. I wonder why…

(and I’m sorry about the google/planck/furlongs nonsense from before.)

Posted by: Jesse on October 26, 2006 1:14 AM | Permalink | Reply to this

Post a New Comment