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.

March 11, 2008

Physics, Topology, Logic and Computation: a Rosetta Stone

Posted by John Baez

It’s done!

Learn how category theory serves as a lingua franca that lets us translate between certain aspects of these four subjects… and perhaps, eventually, build a general science of systems and processes! In a nutshell, it goes like this:

object morphism Physics system process Topology manifold cobordism Logic proposition proof Computation datatype program \array{ & object & morphism \\ Physics & system & process \\ Topology & manifold & cobordism \\ Logic & proposition & proof \\ Computation & data type & program }

It takes a while to explain the details.

Actually, I’ve come to feel that in academia no project is ever really done. At least, not until you lose interest or die — which, come to think of it, is just an extreme case of losing interest. There’s always room for revising, improving, extending, and otherwise revisiting old projects. This is particularly evident with the rise of electronic media like the arXiv. When you catch the umpteenth typo, do you put up yet another version of your paper or not? It just depends how much you care.

There are certainly lots of typos still lurking in this paper, and probably much worse problems. But, we’ve tried to take all your comments into account — sometimes by judiciously not doing anything about them — and I feel they’ve vastly improved the paper. Thanks, all of you! We could never have done it without all you logicians and computer scientists.

Posted at March 11, 2008 5:47 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1629

100 Comments & 3 Trackbacks

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Hi John!

If I am very patient, may I be able to write Windows XP using manifolds and cobordisms? What would be the blue screen of death? How would I halt a program?

I am not joking.

Posted by: Daniel de França MTd2 on March 11, 2008 2:00 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Daniel wrote:

If I am very patient, may I be able to write Windows XP using manifolds and cobordisms?

If string theory is correct, Windows XP already runs using manifolds and cobordisms. If loop quantum gravity is correct, it’s using something a bit different, but very similar: spin networks and spin foams.

If Microsoft’s Project Q succeeds, and you’re very patient, you may someday use a version of Windows XP that runs using a modular tensor category implemented via the fractional quantum Hall effect. Read the conclusions of our paper!

But, you may have switched to Vista by then.

Posted by: John Baez on March 11, 2008 9:01 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Let’s pose a variant then on Daniel’s question.

I took it he was wondering, given the structural similarity between manifolds/cobordisms and data type/program, whether an actually used program could be seen ‘in principle’ as a highly complex manifold?

In view of the complex three-dimensional pictures as shown on page 31 of Yves Giraud’s The Three Dimensions of Proof for very simple operations, Windows XP, or some equivalent in a functional programming language, would be truly monumental.

But what could be said, in whatever stretched sense of ‘in principle’, about the relation between the cobordism which is the program operating on an input and the cobordism which might be the physics underlying a running of the program as seen by quantum gravity?

I take it that your reply points to an ultimate convergence between the physical and program cobordism.

Posted by: David Corfield on March 12, 2008 12:14 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

“In view of the complex three-dimensional pictures as shown on page 31 of Yves Giraud’s The Three Dimensions of Proof for very simple operations, Windows XP, or some equivalent in a functional programming language, would be truly monumental.”

Interesting article. At first, it resembled me Citanovic’Birdtrack notation. http://www.nbi.dk/GroupTheory/ It was one of John’s last years’s XMas gifts.

Guess what? Yves did use Birdtrack notation (you can also call it Penrose notation)! See page 29. And more, his point was to extend to 3 dimensions.

Now, let´s brainstorm here. Birdtrack notation is used to represent tensors ia much compact way. So, maybe we could have some intermadiate steps like:

tensors > birdtrack notation > (generalize) > Yves 3D notation > logic

according to roseta stone, topology can be translated into logic, so :
Yves 3D notation > Topology > generalized (?) tensors.

I hope it makes 0.1% of sense…


Posted by: Daniel de França MTd2 on March 12, 2008 2:22 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Although I doubt anyone will be confused, just to note that in the functional programming community the term Bird-track used to be used sometimes to refer to a particular style of literate programming (acquiring its name from Richard Bird of the Oxford comlab). It’s seldom used now, but if you’re reading old usenet threads, etc… don’t think you’ve stumbled upon some hidden application of graphical notation.

Posted by: bane on March 13, 2008 4:31 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Anyway it would be nice to see a couple examples of programs written using monoidal closed combinator calculus. :) Is it possible or I talk nonsence?

Posted by: osman on March 12, 2008 12:50 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Let me introduce my (maybe naive, I am not mathematician) idea of modifying λ\lambda-calculus in order to directly forbid duplication or deletion data. In case of λ\lambda-calculus the aplication (β\beta-reduction) rule substitutes all occurences of xx in F[x]F[x] for expression λx:F[x]\lambda x: F[x]. In case of non-deleting calculus (let’s call it δ\delta-calculus) we 1) are not able to apply reduction rule to δx:F[x]\delta x: F[x] if F has 00 occurences of xx (no deletion) and 2) may replace only the first occurence of xx by reduction rule applied to δx:F[x]\delta x: F[x] in case there are 1 or more occurences of xx in FF (no duplication).

It’s interesting if it’s possible to write monoidal closed combinators using such δ\delta-calculus.

I’m sorry if this is totally nonsence…

Posted by: osman on March 12, 2008 4:36 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

It’s not nonsense at all; it’s called linear lambda calculus, and we talk about it a little bit in the paper. We’ve also talked about it several times here on the cafe, especially in the classical vs quantum computation posts. Our original intent was to use it exclusively—John had never even heard of a combinator when we started—but the natural transformations required for a symmetric monoidal category correspond exactly to polymorphic combinators, so we went that route instead.

Posted by: Mike Stay on March 12, 2008 6:09 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

But… in Rosetta you describe SKI calculus and link between SKI and lambda-calculus. And you do not describe such link between monoidal closed combinators and linear lambda calculus - why? It would be very convenient for readers like me, for whom it’s too difficult to read special papers about linear lambda!

Posted by: osman on March 12, 2008 8:39 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Sure we do! They’re in definition 21 and 22.

Many of the combinators are irrelevant if you’re in a poset instead of a category. The important ones are B (which we call ‘compose’):

(1)compose:(YZ)(XY)(XZ) compose=λf.λg.λx.(f(gx)) \array{compose:(Y\multimap Z)\multimap (X\multimap Y) \multimap (X\multimap Z)\\ compose = \lambda f.\lambda g.\lambda x.(f (g x))}

C (which we call ‘braid’):

(2)braid:(XYZ)(YXZ) braid=λf.λy.λx.((fx)y) \array{braid:(X\multimap Y\multimap Z) \multimap (Y\multimap X\multimap Z)\\ braid = \lambda f.\lambda y.\lambda x.((f x) y)}

and I (which we call ‘id’)

(3)id:XX id=λx.x \array{id:X \multimap X\\ id = \lambda x.x}

B, C, and I are a universal basis for linear lambda calculus like S and K are for the usual lambda calculus.

Posted by: Mike Stay on March 12, 2008 11:40 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Sorry, I don’t understand. What about comonad “!”? How to write down factorial algorithm? :)

Posted by: osman on March 13, 2008 10:17 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Sorry, I don’t understand. What about comonad “!”? How to write down factorial algorithm? :)

As John explained, we don’t use the exponential comonad ‘!’. But that doesn’t mean you can’t calculate factorial (also denoted ‘!’, unfortunately). You just have to do it in a linear way. Say you introduce an object B together with morphisms and relations among them that make B behave like a bit. Then the Toffoli and Fredkin gates are morphisms

(1)T:BBBBBB T:B\otimes B\otimes B \to B\otimes B\otimes B
(2)F:BBBBBB F:B\otimes B\otimes B \to B\otimes B\otimes B

that are universal for classical computation.

Assuming you have enough memory (i.e. enough copies of B) to store the intermediate results, you can compute any computable function.

Posted by: Mike Stay on March 14, 2008 11:42 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Mike Stay wrote: also denoted ‘!’ unfortunately

I forget about that! No, of course I mean any other classical algorithm. As far as I understood comonad ‘!’ is needed for something like “duplication” or “deletion” in “monoidal” part. I did not mean it is directly linked to factorial algorithm. :)

Yes, I know about gates. But I thought it’s possible to make primitive recursion inside monoidal category in some way.

Posted by: osman on March 15, 2008 6:28 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

This is inside the monoidal category. The Toffoli and Fredkin gates are two morphisms in the category.

To embed classical computation into quantum computation, you first have to make the computation linear. Then the classical states form a basis for the quantum states. As long as you stick to basis vectors and don’t do any superpositions, you’ll be doing classical computation.

Then duplication and deletion are both control-NOT. Let U be the unitary operator implementing control-NOT. Then

(1)U|a,b=|a,ba U|a,b\rangle = |a, b \oplus a\rangle

and in particular,

(2)U|0,0=|0,0 U|0,0\rangle = |0,0\rangle
(3)U|1,0=|1,1. U|1,0\rangle = |1,1\rangle.

So if you have a qubit that you know is in the |0|0\rangle state, then you can do a “classical copy” of the first bit onto the second. (Note that I said it makes a copy of the bit, not the qubit! This is equivalent to measuring the qubit and copying down the result.)

The same control-NOT can function as deletion. If you have two copies of the same bit, you can get rid of one and be left with a qubit bit you know is in the |0|0\rangle state:

(4)U|0,0=|0,0 U|0,0\rangle = |0,0\rangle
(5)U|1,1=|1,0. U|1,1\rangle = |1,0\rangle.
Posted by: Mike Stay on March 17, 2008 7:20 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Is it possible to express these things by modification of monoidal closed combinator calculus without making category cartesian (as described here)?

Posted by: osman on March 17, 2008 8:59 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Nothing I wrote above is cartesian. Control-NOT does not satisfy the coherence laws for duplication and deletion, because it doesn’t copy quantum state, only classical state.

Posted by: Mike Stay on March 17, 2008 10:50 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

OK, I modify my question: is it possible to express these things (control-NOT logic) by modification of monoidal closed combinator calculus? The answer is not obvious for me, unfortunately.

Posted by: osman on March 18, 2008 7:11 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

is it possible to express these things (control-NOT logic) by modification of monoidal closed combinator calculus?

I’m not sure what you mean by “modification”. If you mean, “Is the typical gate-based approach to quantum computation a symmetric monoidal closed category?”, then yes, it is. It’s a strict dagger closed category. (See section 2.7.)

There’s a qubit type, say Q,Q, and all the objects in the category are finite tensor products of these: 1,1, Q,Q, QQ,Q\otimes Q, QQQ,Q\otimes Q\otimes Q, \ldots There’s an internal hom type XY=X *YXY.X \multimap Y = X^*\otimes Y \cong X \otimes Y.

When you’re interpreting this stuff in Hilb (i.e. as quantum computation) then the morphisms of the category are matrices with complex elements. For example, the control-NOT gate UU looks like

(1)U=(1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0). U = \left(\array{1& 0& 0& 0\\0& 1& 0& 0\\0& 0& 0& 1\\0& 0& 1& 0}\right).

Say X=Q nX=Q^{\otimes n} and Y=Q m.Y=Q^{\otimes m}. The nmn m elements of a matrix in hom(X,Y)hom(X,Y) can be stored (up to normalization) in the nmn m elements of a state in XY.X \otimes Y. For example, the matrix

(2)V=(a b c d) V = \left(\array{a& b\\c& d}\right)

gets represented as a state

(3)|V=(a b c d). |V\rangle = \left(\array{a\\b\\c\\d}\right).

Gate teleportation is the protocol filling the role of “eval”. It takes the state

(4)|V|x|V\rangle |x\rangle

to the state

(5)|random|Vx.|random\rangle |V x\rangle.

(Actually, it’s a little more complicated than that: there are some corrections that have to be made related to the random bits, but I won’t go into that unless you really want the details.)

Posted by: Mike Stay on March 18, 2008 6:04 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

No, I mean combinator calculus. For example, extend your Definition 22 by following rules:

If XX is type then meas(X)meas(X) is type. If XX is type then following polymorphic combinators give terms: dup:meas(X)meas(X)meas(X)dup: meas(X) \multimap meas(X) \otimes meas(X) del:meas(X)meas(X)meas(X)del: meas(X) \otimes meas(X) \multimap meas(X).

or something like that, in more details. Maybe directly add cartesian projections for meas(X)meas(Y)meas(X) \otimes meas(Y), I don’t know.

Posted by: osman on March 18, 2008 8:32 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

No, I mean combinator calculus.

That is combinator calculus. Gates are combinators.

If XX is type then meas(X)meas(X) is type.

Sure, your “meas” is the same thing as the exponential “!”. Just follow the Curry-Howard isomorphism across from linear logic to computer science and you’ll get the combinator you want.

The thing is, you can leave out “!” because measuring the state of a system XX is the same as entangling XX with YY and then tracing out (ignoring) YY. That’s the whole point of the quantum eraser experiments.

Posted by: Mike Stay on March 18, 2008 9:43 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

My problem is following: I am not scientist. I am 35yo-C-coder-from-deep-Russia. I started very-slow-self-learning in Category Theory 3 years ago just because I want to know the-most-powerful-method-to-understand-the-world-where-I-live. So these things about quantum entaglement are a little bit difficult for me (but of course I’ll try to understand them, ignoring the fact that Hilbert space is quite non-intuitive thing for me).

I just think that if I would see the complete version of combinator calculus with meas, dup and del, it would be more easy for me to understand other things related to generalized computations. :) Thank you!

Posted by: osman on March 18, 2008 10:29 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I just think that if I would see the complete version of combinator calculus with meas, dup and del, it would be more easy for me to understand other things related to generalized computations. :) Thank you!

Well, take the last four inference rules on page 4 here and add the corresponding polymorphic combinators and rewrite rules to definition 22. Those four rules allow duplication and deletion of measured systems.

Posted by: Mike Stay on March 18, 2008 10:52 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I obtained following combinators:

  • weak X:Y(!XY)weak_X: Y \multimap (!X \multimap Y): weakx y = (!x y)
  • contr:(!A!AB)(!AB)contr : (!A \otimes !A \multimap B)\multimap (!A \multimap B) : contr ((!x ⊗ !x) y) = (!x y)
  • derel:(AB)(!AB)derel: (A \multimap B) \multimap (!A \multimap B): derel (x y) = (!x y)
  • prom:A!Aprom: A \multimap !A: prom x = !x

And some preliminary questions:

  1. Is it OK (especially weak Xweak_X)?
  2. Isn’t derelderel just “promBprom \multimap B”?
  3. How to duplicate?
Posted by: osman on March 19, 2008 9:24 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Maybe using evaluation we could convert weak Xweak_X into form :

  • weak:!XYYweak: !X\otimes Y \multimap Y: weak (!x y) = y
Posted by: osman on March 19, 2008 9:42 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

And it looks like contrcontr depends on weakweak, because contr ((!x ⊗ !x) y) = (weak (!x ⊗ !x)) y. So if I am right we have only 2 independent combinators: weakweak and promprom?

Posted by: osman on March 19, 2008 10:02 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I’m sorry, this everyting was wrong. OK, I’ll wait for some paper. Thank you everybody.

Posted by: osman on March 20, 2008 3:20 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Is closed *-autonomous category (and corresponding combinator calculus) exactly what am I looking for? If so I think I have enought information.

Posted by: osman on March 19, 2008 2:18 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

And, to “follow from linear logic” is (maybe) not enough for me. I would like to know what kind of “closeness” or “adjointness” does it mean, how “natural” is linear logic from CT point of view, I would like to know the categorical meaning of any rule of this logic (which I did not know about just several days ago)

Posted by: osman on March 18, 2008 10:46 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Of course, Hilbert space is non-intuitive for me just because I have no time (and enought brain :) ) to learn categorical structuralization (or categorification, or groupoidification, or spanification) of it - this one already (or almost) exist, as I understood. May be in 5-10 years I’ll learn it. Categorical structuralization of physics is greatest progress of the human thought in this century I think.

Posted by: osman on March 19, 2008 1:38 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I mean, is it possible to modify your closed monoidal calculus in order to add analogues of duplication and deletion, natural from quantum or cobordism point of view, and make some classical recursive algorithm?

I’m sorry that you should “decrypt” my questions. :)

Posted by: osman on March 15, 2008 8:56 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Osman wrote:

I mean, is it possible to modify your closed monoidal calculus in order to add analogues of duplication and deletion, natural from quantum or cobordism point of view, and make some classical recursive algorithm?

Sure! We’re describing a generalization of the ordinary untyped lambda calculus, so it’s easy to specialize back to that familiar case, where you can write all the programs you like.

Start with a combinator calculus of the sort we describe. For simplicity, suppose there’s one basic type XX (and all the types formed from this by \otimes and \multimap). This gives a closed symmetric monoidal category containing one object XX (and all the objects formed from this using the tensor product and internal hom).

Then, put in polymorphic combinators for duplication and deletion, and suitable rewrite rules. This ensures that your symmetric monoidal category is cartesian. So, now you’re back to the usual simply typed lambda calculus!

Then, put in terms

α:X(XX)\alpha:X \multimap (X \multimap X) α 1:(XX)X\alpha^{-1}:(X \multimap X) \multimap X

and rewrite rules saying these are inverses. Now you’re back to the usual ‘untyped’ lambda calculus, where you can apply any term to any other. So, now you write all the programs you want.

A bunch of this is explained here and elsewhere in the notes from our 2006-2007 seminar on this subject. I suppose it would be good to include a few sentences in the paper saying what I just said.

When one gets deeply involved in a subject, things start seeming ‘obvious’ that aren’t obvious to anyone else! This is a major reason it’s hard to explain things. I’m sure the stuff I just wrote would not have made sense to me a few years ago. When I write expository papers I always try to place myself back into the mental position I occupied before I learned what I’m explaining. But, sometimes I forget to do this.

Posted by: John Baez on March 15, 2008 10:25 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thank you, but I’m afraid this is obvious what you said here. I supposed there is a “trick” that allows us to leave the category non-cartesian an anyway make some recursive computations. As I see it was my mistake.

I’m impressed with your patience to me, thanks a lot.

Posted by: osman on March 16, 2008 8:22 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Oh, my English again…

I mean I thought there is a trick allowing us to keep category non-cartesian but perform classical computations.

Posted by: osman on March 17, 2008 6:08 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Osman wrote:

I thought there is a trick allowing us to keep category non-cartesian but perform classical computations.

There are probably various tricks like this. The simplest one would be something like this: instead of making the whole category cartesian, make a specific object XX act cartesian by equipping it with its own personal duplication and deletion morphisms:

Δ:XXX \Delta : X \to X \otimes X !:XI ! : X \to I

You want these to make XX into a comonoid, at the very least. Then, if you also have an isomorphism

α:X(XX)\alpha : X \to (X \multimap X)

you’re getting close enough to the untyped lambda calculus that you have a chance of building a universal computer using XX. But I’m sure some extra conditions must be required too, guaranteeing that the closed monoidal subcategory generated by XX, Δ\Delta, !! and α\alpha is sufficiently ‘free’.

There are probably other more interesting tricks, too…

Posted by: John Baez on April 7, 2008 9:48 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Osman wrote approximately:

Sorry, I don’t understand. What about the comonad “!”?

If you read the introduction to this paper, you’ll see we limit ourselves to explaining a very simple flavor of categories — symmetric monoidal closed categories — from four viewpoints: quantum physics, the topology of cobordisms and tangles, multiplicative intuitionistic linear logic, and a version of the combinator calculus.

If we tried to do more, the paper would become too long. It would become the book I someday want to write!

So, in the sections on logic and computation we avoid the comonad ‘!!’, even though it’s very important in linear logic. We’re only talking about the fragment of linear logic that applies to any symmetric monoidal closed category: ‘multiplicative intuitionistic linear logic’.

Posted by: John Baez on March 13, 2008 8:54 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Osman wrote:

And you do not describe such link between monoidal closed combinators and linear lambda calculus - why?

I explained why in the beginning of the section on computation:

Various flavors of ‘linear’ or ‘quantum’ lambda calculus have already been studied, for example by Benton, Bierman de Paiva and Hyland [ref], Dorca and van Tonder [ref], and Selinger [ref]. In the sections that follow we shall take a slightly different tack and consider a linear version, not of the lambda calculus, but of ‘combinatory logic’.

[…explanation of combinatory logic…]

It is a bit irksome to avoid duplication or deletion of data in the lambda calculus, since we need to count how many times each variable gets used. It is easier in combinatory logic: we just need to avoid combinators that duplicate or delete data.

We could have talked about a linear version of the lambda calculus, and that’s what I originally wanted to do. But Mike pointed out that it’s easier to avoid duplication and deletion of data using a combinator calculus. Combinators are like basic ‘building blocks’ that you stick together to form bigger programs; if these building blocks don’t delete or duplicate data, neither will the bigger programs. In the lambda calculus we need to count how many times each variable gets used, and make sure it gets used just once. Stating this precisely requires an annoying (but typical) detour into free versus bound variables. Furthermore, the constraint that each variable gets used once is slightly ‘nonlocal’. So, Mike convinced me that the combinator approach is better.

If we’d had time, I would have explained how to translate any expression in our ‘closed symmetric monoidal combinator calculus’ into a lambda-term. The resulting lambda-terms will then automatically satisfy the constraint that each variable gets used exactly once.

Posted by: John Baez on March 13, 2008 7:11 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

This is an exhaustive answer, thank you. Being a programmer (not CS-scientist) I just wanted to start writing programs with cobordisms, so I was a bit disappointed :)

Posted by: osman on March 14, 2008 3:34 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

How would I halt a program?

I have to admit that this is one part I’m not entirely clear on. There seem to be two approaches to halting, and I’d appreciate the help of the computer science people here in understanding.

The first is the normal form of a term under rewrite rules, which is entirely syntactic. A term has a normal form if the rules are confluent and terminating. This is the case for all terms in the simply-typed lambda calculus, but not in the untyped lambda calculus, since we can write

(1)(λx.(xx))(λx.(xx))(\lambda x.(x x))(\lambda x.(x x))

which rewrites to itself.

The second is interpreting the lambda calculus using (PointedSet, \wedge), the symmetric monoidal closed category of pointed sets, pointed maps, and the smash product. The special point of each pointed set is ‘bottom’ (\bot), which is used to represent the non-halting state. Pointed maps with the smash product means that if part of the computation takes forever, the whole computation takes forever.

But this means the smash product isn’t cartesian! If you interpret a cartesian closed category CC in (PointedSet, \wedge), then you have to treat the cartesian product in CC as merely a tensor product: you can’t talk about real parallel execution any more. The best you can do is simulate it by threading.

Then there’s some weirdness going on with extensionality, because if you’ve got a language like simply-typed lambda calculus, you may not be able to write an infinite loop, but if you interpret it in PointedSet, you still have to worry about its behavior on bottom.

There’s a thread here where Robin talks about how two programs have the same behavior on all inputs that you can define syntactically, but differ when you feed them ‘parallel or’ (por). Por is not a pointed map with the smash product, but it’s apparently a map in a Scott domain, something I’m not very familiar with. It looks like Scott domains use the cartesian product on pointed sets.

If you use the cartesian product and pick the special point to be (,),(\bot, \bot), then a pointed map out of X×YX \times Y contains more information than a pair of pointed maps, one out of XX and one out of YY. This is because whereas a pointed map out of XX has to send \bot to ,\bot, a pointed map out of X×YX \times Y can send (,y)(\bot, y) (where yy is not \bot) to something else. (PointedSet, ×\times) is a symmetric monoidal category in which por is a morphism. But (PointedSet, ×\times) is not a closed category, so we can’t interpret lambda calculus there without throwing away closedness. Is a Scott domain closed? How?

We put extensionality into our equivalence rules for the combinator calculus. Is it necessary in order to get a symmetric monoidal closed category?

In a purely functional context like combinator calculus, what are the reduction strategies available to us? How does extensionality play into each of these?

Posted by: Mike Stay on March 12, 2008 5:03 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Just a thought, but isn’t halting intimately related to fixed points? The lambda expression above is a fixed point of the evaluation function and so can be considered to have “halted” , just like a lambda expression that evaluates to 3, which is also then at a fixed point.

Posted by: Mark Biggar on March 14, 2008 7:35 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

On the contrary, fixed points of the rewrite rules are a class of programs that do not halt. 3 isn’t a fixed point of the rewrite rules; it’s a point at which no rewrite rule applies.

Posted by: Mike Stay on March 18, 2008 12:19 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

David wrote:

Let’s pose a variant then on Daniel’s question.

I took it he was wondering, given the structural similarity between manifolds/cobordisms and data type/program, whether an actually used program could be seen ‘in principle’ as a highly complex manifold?

Well, the point of our paper is that very similar ‘string diagram’ machinery can be used to describe quantum processes, cobordisms, proofs and programs.

But, the first two examples involved compact closed categories, while the second two often involved cartesian closed categories.

What does that mean?

Very crudely, ‘compactness’ is why quantum physics allows ‘creation and annihilation of particle-antiparticle pairs’, but doesn’t allow the arbitrary duplication and deletion of lone particles.

‘Cartesianness’ is why traditional programs don’t allow ‘creation and annihilation of datum-antidatum pairs’, but do allow duplication and deletion of data.

So, there are similarities but also differences.

But, as we explain in the Conclusions, the similarities become more pronounced in quantum computation — especially topological quantum computation, like they’re trying to do in Project Q.

Posted by: John Baez on March 13, 2008 9:09 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Something about what I just wrote made me even more excited than usual about how ‘cartesianness’ lets us duplicate and delete:

xxx x \to x \otimes x x1 x \to 1

while ‘compactness’ lets us create and annihilate particle-antiparticle pairs:

x *x1 x^* \otimes x \to 1 1xx * 1 \to x \otimes x^*

This made me ask Jim if he knew of any compact cartesian categories — that is, compact symmetric monoidal categories where the tensor product is the cartesian product and the unit object is terminal.

We soon saw the only example is the terminal category (fun little exercise).

Then Jim said this reminded him of Hawking radiation! Quantum theory lets you create and annihilate particle-antiparticle pairs. A black hole lets you ‘delete’ particles or antiparticles by throwing them down the black hole. The simple idea behind Hawking radiation is that this lets you create particles: create a particle-antiparticle pair, and then delete the antiparticle!

Here we are not using duplication, just deletion. So, I asked Jim a trickier question: are there any compact symmetric monoidal categories where the unit object is terminal?

I’ll leave this as a puzzle. If the only examples are trivial in some sense, it suggests there’s something funny about the simple story of Hawking radiation told above!

Posted by: John Baez on March 14, 2008 2:26 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

it suggests there’s something funny about the simple story of Hawking radiation told above!

But we know that, indeed, there is something funny about this way of telling the story: we know that it can’t be true literally that one member of the pair of particles is literally “deleted”. In some way or other it got to show up in the “internal state” of the black hole.

It’s that unitarity puzzle: there ought to be a way to descibe black hole formation and decay which is entirely “unitary”, meaning essentially that, globally, no deletion or creation takes place.

There are plenty of articles out there arguing that the entropy of a black hole can entirely be understood as “entanglement entropy” resulting from “tracing out” the stuff that “drops behind the horizon” (scare quotes for good reasons…).

Not sure what the canonical reference is, but this one looks reasonable:

Roberto Emparan, Black hole entropy as entanglement entropy: a holographic derivation .

By the way, I always thought of Frobenius modules as a nice analog for black hole radiation:

suppose AA is a Frobenius algebra and VV a right AA-module. In string diagrams this means that AA-lines can “be absorbed” into VV lines.

But that then automatically implies that VV-lines may “emit” AA-lines, namely that we also have a co-module structure on VV:

We start with VV and with the unit for AA to produce an AA “out of nothing”, then proceed with the coproduct to produce two copies of AA, then use the right AA action on VV to delete one of the copies. From far away this looks as if VV emitted an AA-line.

Of course this example doesn’t capture the particle/antiparticle notion.

Posted by: Urs Schreiber on March 14, 2008 9:49 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

are there any compact symmetric monoidal categories where the unit object is terminal?

Well, the functor AA\otimes- is right adjoint to A *A^*\otimes-, hence it must preserve limits. In particular it preserves terminality: if TT is terminal then ATA\otimes T is terminal too, for all objects AA. So, if the unit object is terminal then clearly every object is terminal, and the category is trivial.

More generally, in a (left or right) closed monoidal category, if the unit object is initial then the category must be trivial.

Also: in a compact symmetric monoidal category, if there is a terminal object 11 then there is also an initial object 0=1 *0 = 1^*. Now consider the object 010\otimes 1. Since 00\otimes- preserves limits, 010\otimes1 must be terminal; and since 1-\otimes1 preserves colimits, it must be initial. So it’s a zero object, which means that 00 and 11 are zero objects as well. The upshot is that every initial object is also terminal, and vice versa.

Posted by: Robin on March 14, 2008 11:58 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

John wrote:

…are there any compact symmetric monoidal categories where the unit object is terminal? I’ll leave this as a puzzle.

The Prince of Compact Categories replied:

Well, the functor AA \otimes - is right adjoint to A *A^* \otimes, hence it must preserve limits. In particular it preserves terminality: if TT is terminal then ATA \otimes T is terminal too, for all objects AA. So, if the unit object is terminal then clearly every object is terminal, and the category is trivial.

Right, that’s about how Jim did it. Being a bit of lowbrow myself, I enjoyed translating his answer into baby-talk. Others may enjoy this too:

Suppose the unit object of our compact symmetric monoidal category is terminal; let’s call it TT.

Since ATAA \otimes T \cong A for any object AA, morphisms

BAB \to A

are in 1-1 correspondence with morphisms

BATB \to A \otimes T

By compactness, these are in 1-1 correspondence with morphisms

A *BTA^* \otimes B \to T

But, there’s only one of these, since TT is terminal. So, there’s only one morphism BAB \to A so AA is terminal!

So, any such category is trivial (equivalent to the terminal category).

The assumption ‘symmetric’ was not necessary; I put it in just to avoid an annoying fuss about left versus right duals.

Posted by: John Baez on March 15, 2008 2:57 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Urs wrote:

we know that it can’t be true literally that one member of the pair of particles is literally “deleted”.

Maybe we know it — but it’s interesting to ask exactly why we ‘know’ it. There’s no experimental evidence on this topic, so what assumptions are we using to draw this conclusion?

It’s that unitarity puzzle: there ought to be a way to descibe black hole formation and decay which is entirely “unitary”, meaning essentially that, globally, no deletion or creation takes place.

Unitarity is a bit different than ‘no deletion’. If you’re a unitarian, you believe that the universe is described by a dagger-category, but that the only ‘physically possible’ morphisms are the unitary ones: that is, those with:

f f=1f^\dagger f = 1 ff =1f f^\dagger = 1

I don’t know a good a priori argument for unitarianism. It seems to work very well in ordinary life. But, in plenty of more far-out theories, like topological quantum field theories, we have a dagger-category but also treat nonunitary processes as physically possible. (These typically involve topology change.)

The argument I sketched proceeds along different lines: it says that any universe described by a compact monoidal category with a terminal object must be completely, utterly dull!

It’s not a very fleshed-out argument, just an idea for one. I don’t actually think a black hole should be modeled as a ‘terminal object’. But, you can imagine trying to describe the idea of a ‘perfect garbage dump’, where you can throw anything in and have all its information lost (or all but mass, angular momentum and charge)… and then trying to derive some paradox or problem from this assumption, and other assumptions.

Trying to formalize the idea of a ‘black hole as perfect garbage dump’ reminds me of a very interesting section in Sommerfeld’s Optics where he tries to define what it means for an object to be ‘black’. In other words: what boundary conditions for Maxwell’s equations correspond to a perfectly black surface? It turns out to be a hard problem. I’m not sure why: perhaps because a purely passive entity would violate reciprocity.

Posted by: John Baez on March 15, 2008 3:10 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Related question: how many category theorists visualize terminal objects as black and initial objects as white? I think I do.

Posted by: John Baez on March 15, 2008 3:22 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

A tiny request and a question:

- could we get page numbers? Would help in taking notes

- could we imagine adding inference to the Rosetta stone? I mean I’m sure there could be many other additions to such a general programme, but this is one I’d love to see. Of the many possible choices for the objects/morphisms I’d pick Bayesian style names (beliefs/updates?; propositions/inferences?). I’m very biased, but I’d put inference in the middle of the stone. Maybe someone could attribute this quote I once heard:

“First God invented Bayes rule, then he drew his pistol!”

Posted by: Allan E on March 16, 2008 7:32 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Allan wrote:

could we get page numbers?

Yes! You’ve got ‘em now! I apologize to everyone for not including them sooner; I didn’t want to mess with the publisher’s format until the paper had reached a reasonably stable state.

could we imagine adding inference to the Rosetta stone?

I can imagine it… but does it really work? I’d say it ‘works’ if we can describe closed symmetric monoidal categories where ‘beliefs’ are objects and ‘updates’ are morphisms — or something like that. I don’t see precisely how it should go. Has anyone tried something like this?

As for a closed symmetric monoidal category of ‘propositions’ and ‘inferences’, that’s sort of what the logic section is all about. But, sadly, I don’t really understand how Bayesian inference connects to proof theory. Maybe this has something to do with David’s ‘progic’ project?

Posted by: John Baez on March 16, 2008 9:48 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

A good place to start on relating inference to physical processes is belief propagation, which has as special cases

the forward-backward algorithm, the Viterbi algorithm, iterative decoding algorithms for Gallagher codes and turbocodes, Pearl’s belief propagation algorithm for Bayesian networks, the Kalman filter, and the transfer-matrix approach in physics.

In an ideal world I’d get down to understanding belief propagation in terms of information geometry.

Posted by: David Corfield on March 19, 2008 10:01 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Dear John Baez,

It seems an interesting paper, I’ll read it opportunely.

I wonder whether concurrent processes would have a place in your Table 4. I see that you have an analogy scheme for parallel processes. That is, processes that do not compete with themselves and proceed independently (uncoupled) . In the case of concurrent processes, they compete for common resources in order to achieve some computational objective (they are coupled in some sense). Directed topology (“ditopology”) has been introduced recently as a technique to help verifying concurrent computation, the presence of deadlocks, etc. It would be reasonable to think about concurrent processes as parallel processes with more structure, right? What would be the correspondence of such systems with other concepts in category theory, physics, etc?

I wonder about the relevancy of concurrent processes in physics, in particular.

Thanks
Christine

Posted by: Christine Dantas on March 17, 2008 7:55 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Last week I had lunch with Carl Hewitt and discussed with him the relationship between the actor model and physics. Hewitt had in mind creation and annihilation operators when conceiving of message passing: one actor “emits” a message, while another “aborbs” the message, and these particles can move around each other. Upon receipt or emission of a message, an actor’s ‘behavior’ changes, but is still considered to be the same actor.

We can get a monoidal category from this by having an object X be “an actor with behavior X” and morphisms be either sending a message

(1)a *:XX M a^*:X \to X^' \otimes M

or receiving a message

(2)a:XMX . a:X \otimes M \to X^'.

So roughly, a lambda calculus term is a description of one possible ordering of messages being sent and received. Denotational semantics talks about all possible orderings.

Feynman diagrams were invented to keep track of this kind of thing: each diagram keeps track of one way two systems can interact. The rules of the game tell you how to get all possible interactions.

In physics, more complicated interactions are less probable. This is somewhat related to algorithmic information theory, in that the number of interactions gives a notion of the length of the program, and the probability of each drops off exponentially with the number of interactions or instructions.

Now, since this is the n-Category Café, we really have higher categories in mind. Typed lambda calculus gives a 2-category with objects from types, morphisms from terms, and 2-morphisms from rewrite rules. These rewrite rules happen to be confluent for lambda calculus, so it doesn’t matter in which order you apply them.

The actor model gives a 2-category with objects from types, morphisms from behaviors, and 2-morphisms from sending/receiving a message. These 2-morphisms are not confluent, so you can model two actors vying for the same resource.

Note that in the comparison above, I had to use 1-categories, and the way I got 1-categories from each of these 2-categories was different. With lambda calculus, we can get rid of the 2-morphisms by taking equivalence classes; this is possible because the rewrite rules are confluent.

With the actor model, they’re not confluent, so I had to get rid of the lowest level, the types, instead. I did it by declaring all data types to be isomorphic: every data type is just bits.

Posted by: Mike Stay on March 17, 2008 10:41 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

As to ditopology, I do not know what the current `best model’ for concurrency is from that direction.

In a paper on the Dagstuhl seminar/conference site, I did look at using simplicially enriched categories and then using bar/cobar type constructions to get a DG category rather as is used in work by Lazaroiu. (My paper is at
kathrin.dagstuhl.de/files/Materials/06/06341/06341.PorterTimothy.Paper!!.pdf)
There may be other papers on that site with relevance to Christine’s question.
The relevant details for that meeting were:

date 20.08.-25.08.06, Seminar Nº 06341

Computational Structures for Modelling Space, Time and Causality

organised by R. Kopperman (City University of New York, US), P. Panangaden (McGill University - Montreal, CA), M. B. Smyth (Imperial College London, GB), D. Spreen (Univ. Siegen, DE)

There are mostly just the abstracts there but there are also links to the proceedings (DROPS submission) for some of the participants.

Posted by: Tim Porter on March 19, 2008 8:57 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Here’s a quick note, disagreeing with one of your constructions. In 1.4.2, you translate a programming language into a closed monoidal category, and I was nodding and agreeing that your translation did what I would expect a dictionary to do until I got to the last generator for the equivalence relation on morphisms:

“ if terms are “extensionally equivalent”, they are equivalent. Here we say f:(X \to Y) and f’:(X \to Y) are extensionally equivalent if (f x):Y and (f’ x):Y are equivalent for all terms x:X. ”

Certainly you get a closed monoidal category using your scheme. But you get (I argue) the wrong one: in particular, you still get a closed monoidal category without the extensionality condition.

Let me give an example:

In the category SVect, the objects are super-vector spaces (Z/2-graded vector spaces) and the morphisms are grading-preserving linear maps (“even” maps). The internal hom between two svector spaces? That’s the svector space of all linear maps. (In particular, External Hom is not Forget applied to Internal Hom.)

The monoidal structure is tensor, where the product of two (-1)-graded parts is (+1)-graded. (The braiding, which I don’t need for this discussion, is the usual flip map, with a sign when I braid an odd thing past an odd thing.) The unit object is still just \R, but, for example, there is only the zero morphism from this unit object to a purely-odd vector space like \R^{(0|1)} = 0 \oplus \R, where the \R has odd grading.

In particular, given a space X, then (external hom) maps from the unit object into X pick up just the even (i.e., (+1)-graded) elements; they’re not enough to get all elements. Your “extensionally equivalent” condition loses information, when applied to this category: it says that two functions agree if they agree on all even elements.

So if I translate SVect into a programming language using the method you outline, and then translate back into a category, I get back Vect of (ungraded) vector spaces, not SVect; moreover, this is not the forgetful function SVect \to Vect that forgets the grading, but rather the “reduce” functor (I can’t call it “Forget”, because it is not fully faithful) that forgets the odd part of the space.

Posted by: Theo on March 23, 2008 1:30 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

SVect is also a good example where the re-write rule should not be “(((braid f) x) y) = ((f y) x)”, even though the braiding is symmetric.

Posted by: Theo on March 23, 2008 1:33 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Theo’s got a point. The general idea is that if one wants to argue “elementwise” in category theory, one should be prepared to use, instead of (what are sometimes called) “global elements” IXI \to X, “generalized elements” (general morphisms with codomain XX). For example, in topos theory, it is well known that restriction to global elements is much too crude – there may not be any (for instance, in the topos of sheaves on the unit circle, the universal covering space conceived as an etale space or sheaf has no global elements whatsoever, because that would amount to a global section S 1S^1 \to \mathbb{R})!

One can see this principle at work in the Curry-Howard correspondence between proofs and programs: an equivalence class of proofs A 1,,A nXA_1, \ldots, A_n \vdash X translates to a term t(a 1,,a n)t(a_1, \ldots, a_n) of type XX with free variables a ia_i of types A iA_i. You can think of these free variables as connoting indeterminate generalized elements of type A iA_i (any term or generalized element of type A iA_i is allowed to be substituted for the variable a ia_i).

A proof of IXI \vdash X or of X\vdash X would translate to a closed term of type XX (no free variables). So your procedure amounts to a decision to consider only closed terms.

SVect is also a good example where the re-write rule should not be “(((braid f) x) y) = ((f y) x)”, even though the braiding is symmetric.

Theo’s right here too. Probably best just to chuck that rewrite rule; just do what you did before in section 3 (mod out by the hexagon etc.).

I can’t call it “Forget”, because it is not fully faithful

It’s a very minor point, but I don’t agree with Theo here. Uncontroversially, you can at least dispense with “full” here; for example the forgetful functor from groups to sets isn’t full.

If one takes the attitude that “forgetful” can only apply to an functor DCD \to C where objects of DD are CC-objects which come equipped with extra structure and the functor is the one which forgets that structure, then yeah, according to that, faithfulness would be necessary (and Theo is observing here that the functor which remembers only the even-graded part is not faithful – quite right). But we’re in a situation where I’d say that SuperVectSetSuperVect \to Set forgets “stuff” as well (namely the odd-graded part). And that language seems perfectly okay to me.

While we’re on the subject of your paper – I’m uneasy with the business of the decision procedure [or coherence problem] for smc categories in section 3. Citing Szabo as having something to do with solving the decision procedure is bound to lead to misunderstanding, and citing my thesis is fine but has the drawback that it’s unpublished. And Kelly and Mac Lane only gave a partial solution.

Here are some other references where a proposed full solution is published and presumably less controversial than Szabo’s (but I really can’t vouch for them personally – I haven’t checked all the details):

  • C.B. Jay, The structure of free closed categories, JPAA 66: 271-285 (1990).
  • S. Soloviev, Proof of a conjecture of S. Mac Lane, Annals of Pure and Applied Logic 90: 101-162 (1997).
Posted by: Todd Trimble on March 23, 2008 4:44 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Of course, I should not have asked that Forget be full; I misspoke.

I do absolutely demand that Forget have a left-adjoint that deserves to be called Free. In the example of SVect \to Vect that forgets the grading, but is faithful on morphisms, we can take the adjoint to be \otimes\R^{1|1}. For the unfaithful functor Reduce, I guess there is also an adjoint: we embed Vect into SVect as purely even spaces. (Indeed, when I said “\otimes\R^{1|1}”, I first did this embedding.)

So perhaps I will consider both to be forgetful. But then I want to say “forgets structure” for a faithful functor with a left adjoint, and “forgets stuff” if it is not faithful. I’m still much more comfortable using the word “Forget” only when I’m forgetting structure, not stuff.

In any case, Yoneda says that to recognize a space, it’s enough to consider its generalized elements. The global elements certainly are not enough: \R^{0|1} also has no global elements. A popular way to describe constructions with supermanifolds (e.g. super Lie groups) uses generalized elements, since then we can port the element-centric definitions.

Posted by: Theo on March 24, 2008 3:23 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I do absolutely demand that Forget have a left-adjoint that deserves to be called Free.

I don’t. For example, consider the you-know-what functor from complete Boolean algebras to sets, or the one from fields to sets. Neither has a left adjoint, but I’d find it strange to forbid calling them forgetful functors.

Posted by: Todd Trimble on March 24, 2008 1:57 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Besides the issues Todd mentions, it also seems wasteful to define ‘forgetful functor’ to mean ‘right adjoint’, when the latter phrase is already terse and perfectly clear. I think it’s better to tell a nice story about functors that forget nothing, properties, structure, or stuff.

Posted by: John Baez on March 25, 2008 3:03 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thanks for everything, Todd, including the extra refs for the coherence problem for symmetric monoidal closed categories. By the way: as soon as you send me your thesis, the problem about it being unavailable will go away (if you want it to). I’ll just scan it in and put it on the web.

Posted by: John Baez on March 25, 2008 2:48 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Theo wrote:

Your “extensionally equivalent” condition loses information, when applied to this category: it says that two functions agree if they agree on all even elements.

Yikes! Thanks for catching this. Believe it or not, Mike and I had been fussing about whether to include ‘extensional equivalence’ as part of the definition of when two terms give the same morphism, but I’d been too rushed to give it careful thought. It felt funny to me because of its focus on ‘points’ x:IXx : I \to X… but for some idiotic reason I didn’t see that it was actually wrong.

I don’t have Lambek and Scott’s book on me here in Singapore, but I believe they did include extensional equivalence as part of their equivalence relation when constructing a cartesian closed category from a theory phrased in terms of the lambda calculus.

I’ll have to go back and check… it now seems wrong to me. Of course your example isn’t cartesian, but the same problem would seem to arise. Say you take a cartesian closed category, turn it into a lambda-theory, then turn it back into a cartesian closed category this way. Then two morphisms f,f:XYf , f' : X \to Y in the original category would now become identified if fx=fxfx = f'x for every x:1Xx : 1 \to X. This seems like an interesting thing to do to a cartesian closed category — but a highly destructive process in general.

Your other point, about the rewrite rule for the braiding in a symmetric monoidal category, is also well taken. I’ll try to get these problems in the paper fixed before Bob Coecke publishes the darn thing.

Posted by: John Baez on March 25, 2008 2:44 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Now I’m getting increasingly confused about certain points…

Todd wrote:

You can think of these free variables as connoting indeterminate generalized elements of type A iA_i.

[…]

…your procedure amounts to a decision to consider only closed terms.

I get your point in the context of the lambda calculus… but in combinatory logic, which is what I’m talking about in this section of the paper, there are no variables! All terms are ‘closed’. Right? So… I’m confused.

Theo wrote:

SVect is also a good example where the re-write rule should not be “(((braid f) x) y) = ((f y) x)”, even though the braiding is symmetric.

Again, I understand the problem if x and y are allowed to be ‘generalized elements’. But if they’re ‘closed terms’ this rule now seems okay to me — even in any braided monoidal category. After all, it says that for any morphisms x:IXx: I \to X, y:IYy: I \to Y and f:YXZf: Y \otimes X \to Z we have

fB X,Y(xy)=f(yx) f B_{X,Y} (x \otimes y) = f (y \otimes x)

And this seems correct. Right?

But: how useful are these rewrite rules if they only handle ‘closed terms’?

But: what else is there, in combinatory logic??

If I think about this more, I should be able to see my way out of this trap… but I’ll just post this now.

Posted by: John Baez on March 25, 2008 8:02 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I wrote:

…but in combinatory logic, which is what I’m talking about in this section of the paper, there are no variables! All terms are ‘closed’. Right?

Of course, in this setting we can take a ‘generalized element of type XX’, that is a morphism x:AXx: A \to X, and curry it to get a ‘closed term of type AXA \multimap X’, that is a morphism x˜:I(AX)\tilde{x}: I \to (A \multimap X). This must be the way out…

… but still, if we have a rewrite rule like

(((braid f) x) y) = ((f x) y)

this seems to apply only to ‘global elements’ x:IXx: I \to X, y:IYy : I \to Y, not generalized elements.

Posted by: John Baez on March 25, 2008 10:49 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

So, in SVect, the braiding for homogeneous elements (those entirely even or entirely odd) is B(ab)=(1) |a||b|baB(a\otimes b) = (-1)^{|a||b|} b\otimes a, where |a||a| is 00 if aa is even-graded part and 11 if aa is in the odd-graded part; for general elements, the Braid is extended by (bi)linearity. This matters because it changes the notions of, e.g., when a function is (anti)symmetric. BB is an isomorphism between VWV\otimes W to WVW\otimes V. The functor SVect\toVect that forgets the grading is monoidal but not symmetric monoidal, because it takes BB to an isomorphism that is not the usual braiding in Vect.

But, yes, for (even) morphisms x:IXx: I\to X and y:IYy: I\to Y, we certainly have B(xy)=(yx)B(x\otimes y) = (y\otimes x). This is true in any braided monoidal category. Because we can untwist open strings:

  I   I          I         I     I   I
  |   |          |         |     |   |
 x|   |y         |         |     |   |
  \   /          /         /    y|   |x
   \ /        I /         /      |   |
    \     =    \    =    /    =  |   |
   / \        / \       /        |   |
  /   \      /   \     /   I     |   |
  |   |     y|   |x   y|   |x    |   |
  |   |      |   |     |   |     |   |

So, in particular, if you only use such global elements, you’ll never be able to pick up braidings that are not symmetric. I think this is probably bad, and means that the rules are missing something. At the very least, the right way to describe a braided monoidal category is to say that XY fgWV BVWX\otimes Y \to^{f\otimes g} W\otimes V \to^B V\otimes W is the same as XY BYX gfVWX\otimes Y \to^B Y\otimes X \to^{g\otimes f} V\otimes W, and also that XI BIX LXX\otimes I \to^B I\otimes X \to^L X is just XI RXX\otimes I \to^R X; if you have both of these, then the untwisting follows. (LL and RR are the left- and right-identity isomorphisms.)

Something you don’t talk about in this section is the associator. As you know, every weakly monoidal category is equivalent to a strict monoidal one (where the associators are identity maps), and also every weakly monoidal category is equivalent to a skeletal one, but you can’t get both.

For example, we have a category equivalent to FinSet which has one set of each cardinalty; I’ll call this set [n]={0,,n1}=Hom([1],[n])[n] = \{0,\dots,n-1\} = {Hom}([1],[n]). We have a (cartesian!) monoidal structure on this. On objects, [n][m]=[nm][n]\otimes [m] = [n m]. On morphisms, if j:[1][n]j: [1]\to[n] and i:[1][m]i: [1]\to[m], then ji=jm+i:[1][nm]j\otimes i = j m+i: [1]\to[n m].

Ok, so this might violate what I said before. Damn. Because, see, jiijj\otimes i \neq i\otimes j. At all. Even though both are global elements (morphisms with domain =[1]= [1]. On the other hand, this is strictly associative: k(ji)=knm+jn+i=(kj)ik\otimes(j\otimes i) = k n m+j n+i = (k\otimes j)\otimes i. I’m trying to remember what the natural example of a skeletal non-strict monoidal category is.

So, anyway, I’m just thinking outloud. I’m very nervous, from this example, about your rewrite rules. I’m also uncomfortable that I feel like I proved something to which I provided a counterexample.

I think, overall, that I do not believe that I can push morphisms past the braiding as I did above? Or, rather, the rule is that Braid is not the identity map. But it is, I guess, the Flip map B(xy)=yxB(x\otimes y) = y\otimes x.

Posted by: Theo on March 27, 2008 12:44 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Ok, I understand my confusion. We never expect Braid to be the identity map. That would be silly.

I’m still looking for my simple example of a skeletal category where the associator is not the identity. Skeletal Picard groupoids do this, and generically skeletal monoidal categories are not strict.

I can do this ad hoc. The trouble is to satisfy the pentagon identity. Returning to the FinSet example, we could be perverse and use ij:[1][m][n]=[mn]i\otimes j : [1] \to [m]\otimes[n] = [m n] defined as (m1i)+mj(m-1-i) + m j; i.e. we reverse the order on the first set. Then (ij)k=((m1i)+mj)k=nm((m1i)+mj)+nmk=(nmm+1)+imj+nmk(i \otimes j) \otimes k = ((m-1-i) + m j) \otimes k = n m - ((m-1-i) + m j) + n m k = (n m - m + 1) + i - m j + n m k, whereas i(jk)=(m1i)+m((n1j)+nk)=(nm1)imj+nmki\otimes (j\otimes k) = (m-1-i) + m((n-1-j) + n k) = (n m - 1) - i - m j + n m k. So the associator is definitely not the identity map.

The associator [m][n][p][m][n][p][m]\otimes[n]\otimes[p] \to [m]\otimes[n]\otimes[p] reverses the order of the first term. Then chasing the pentagon, we see that the two routes each reverse exactly the second term.

So, yes, this is a skeletal non-strict structure.

Anyway, I’m wandering off topic. I certainly don’t have any complaints about your treatment of the associator. My only complaint continues to be the braiding, and writing the rules in terms of global elements rather than all generalized elements (i.e. functions).

Posted by: Theo on March 27, 2008 1:25 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

We understood that using specific choices for the rewrite rules was bad; the right way to do it would be to specify coherence laws on the rewrite rules instead. I think the reason we did it that way is because we wanted to relate it back to the lambda calculus, where you deal with variables. Otherwise, you’d never see anything resembling

(1)B=λxyz.x(y(z)) B = \lambda xyz.x(y(z))

which is how most computer scientists think of it.

Posted by: Mike Stay on March 27, 2008 1:48 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

John and Mike,

I have a new row to add to your Rosetta Stone:

Information Theory—Sources/Destinations—Communication Systems

I have just submitted a paper to the arxiv (the link should work by tonight) in which information theory is axiomatized via category theory. I represent communication systems as morphisms, and give axioms that characterize measures of information in terms of how they behave when communication systems are combined using category-theoretic composition and product operations.

The result is a more general notion of information which encompasses discrete, continuous, and quantum entropy, as well as other functions that are not normally associated with information (vector space dimension, for example.)

I would be very grateful for any comments you might have on my work.

Posted by: Ben on March 25, 2008 8:23 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Ben, you seem to have lost the bibliography, or at least the version I downloaded was missing the bibliography.

Posted by: Simon Willerton on March 26, 2008 1:07 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Good point. I’ll fix that tomorrow.

Posted by: Ben on March 26, 2008 3:56 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Posted by: Ben on March 26, 2008 4:21 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Hi, Ben,

“The conventional measures of information are not appropriate for all situations, and a more general mathematical concept is needed”. Yes, yes! I’ve been trying to make -exactly- that point since 1990 or so (in student eprints and personal communications, later in Usenet postings), but I consistently failed to get this point across to various highly astute mathematicians. I hope you will enjoy better fortune!

Back in 1990, my ideas in brief were (1) to formalize Shannon’s axiomatic approach, using ideas related to lattice theory to remove mention of probability spaces, (2) to formalize some analogies between the easy/general part of classical Galois theory and classical information theory, exploiting an easy/general approach using group actions. I was inspired in part by a remark by my undergraduate algebraic topology (Marshall Cohen) that Noether had noticed that Poincare’s homology groups generalized Betti numbers from numbers to abelian groups, and in part by the Galois duality as per Gelfand between closed subsets in a compact Hausdorff space X and closed ideals of the ring of continuous functions on X. (As everyone here probably knows, here and in classical Galois theory, we have an order reversing duality which “plays nice” which reverses inclusion in the lattice of subgroups/fixsets.) Reading the undergraduate textbook by Davey and Priestly, Introduction to Lattices and Order, was also very helpful to me, particularly the stuff on closure operators and Wille’s “theory of concepts” (which generalizes the remark about lattice structure, and which I tried to popularize for many years). So was an expository paper by Richard Millman, “Kleinian Transformation Geometry”, A. M. Monthly 84 (1977). My interest in both group theory and information theory first arose from a class taught by Martin Harwit (author of an intriguing book, Cosmic Discovery, which IMO was underappreciated when in came out in 1981), who was inspired at least in part by the work of his friend Neil Sloane— who was inspired by his own friend, Claude Shannon!

In an unrelated development, due to some technical problem, yesterday I was unable to post over at Ars Mathematica some background for the award yesterday to Jacques Tits of one half of the 2008 Abel Prize, which I see as evidence of a renewal of interest in the legacy of Klein. Idea (2) falls under this heading, since I used homogeneous spaces (the space of right cosets of a pointwise stabilizers as per Galois) and pointed out that the dimensions of these spaces obey Shannon’s axioms from his 1948 founding paper. (As you know, the axioms you use are significantly different.) It is perhaps notable that over at Not Even Wrong, a few days ago someone suggested Gelfand as possible winner of the Prize; apparently no-one there expected Tits, so obviously there remain conciousnesses to be raised.

Way back in 1994 people were discussing in a once interesting newsgroup, bionet.info-theory, the problem of developing a theory of “biocomplexity”. I had been struck by a chance remark by George C. Williams, Adaptation and Natural Selection (a book often cited as one foundation for the rise of ideas like “kinship selection” in modern evolutionary biology) suggesting that Williams was aware as early as 1966 that “theories of biocomplexity” which assume that organisms are -defined- by their DNA are likely to be based upon a false premise. As I used to put it: naked DNA doth not a bacterium make; you also need complicated “structural overhead”: cell membranes, ribosomes, and so on. Then prevelant ideas concerning the origin of life held that this overhead in fact predated reproduction as we know it. Consequently, I suggested, biologists might need to study notions of “information” or “complexity” which are fundamentally distinct from Shannon’s probalistic formulation.

In particular, I tried hard to make the point that the generality of Shannon’s approach (probability measures can be introduced almost anywhere, after all!) can obscure the fact that using his theory could be completely inappropriate for attempts to capture intuitive ideas of complexity. I pointed out for example that Shannon’s entropies (and my student generalizations) are -subadditive-, whereas biologists might seek measures of “biocomplexity” which are -superadditive-. Unfortunately, I never could seem to get anyone there to understand what I was saying about lattices, closure operators, and so on. (See Davey and Priestly.)

Your list of citations is brief, so I don’t know whether you are aware that there are literally thousands of proposed “information measures” and “complexity measures” in the literature, with almost entirely unknown interrelationships, some of which probably provide examples of your axiomatic approach. In particular, the mathematical ecology literature contains a huge literature on “complexity measures”, some (such as Simpson’s measure) predating Shannon. (Most of the ecologically motivated speculations are profoundly inelegant; some of the mathematically motivated ones are profoundly interesting.) Back around 1994 I wrote two student papers attempting to survey “entropies”, and garnered thousands of references, and venture to guess that the literature has doubled since then.

I may have more substantial comments once I’ve had a chance to study your eprint more closely.

Last but not least, I too wish to thank John and Mike for their excellent paper! I have tried and failed on several occasions to explain some beautiful connections between idea (2) and the lovely reformulation of elementary enumerative combinatorics by Joyal; for some hints see the undergraduate textbook by Cameron, Permutation Groups, and note the close connection between the Joyal cycle index of a structor (combinatorial species) and the Polya index of a finite group action, and thus with the ideas in http://arxiv.org/abs/math/0004133. And the generalization of the “Quotient law” (see Cover and Thomas, Elements of Information Theory) involves Schreier cocycles (see Baumslag and Chandler, Group Theory).

Posted by: Chris Hillman on March 28, 2008 7:24 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Well, this is very unfortunate. I added many more comments and unfortunately the software… lost -all- my work! And this is not the first time I’ve fallen victim to an unadvertised cache limitation. Ben, if you are lurking, let’s find a more stable venue to continue the discussion.

Rather than swearing a vile oath, I’ll gently reiterate my plea that the Cafe migrate to some software which works for me, such as VBulletin or better yet, a wiki running under WikiMedia with all mathy features enabled. And leave it at that.

Posted by: Chris Hillman on March 30, 2008 4:09 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Chris, I feel your pain. It’s also happened to me in the past that I’ve spent ages writing a long comment, only to have it vanish into the ether.

However, after it happened a couple of times I got into the habit of writing long comments in a text editor, before pasting them into the comments box. Now I never lose anything. Would that work for you?

(Also, I would like to gently iterate a plea for the Cafe to stick with its current software. I like it!)

Posted by: Tom Leinster on March 30, 2008 5:10 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I used homogeneous spaces (the space of right cosets of a pointwise stabilizers as per Galois) and pointed out that the dimensions of these spaces obey Shannon’s axioms from his 1948 founding paper. (As you know, the axioms you use are significantly different.)

This is highly intriguing! Yes, my axioms are different, but it wouldn’t be surprising if these dimensions satisfied my axioms too. This would require the homogeneous spaces to be associated to morphisms is some category. Unfortunately, my Galois theory is quite rusty.

Your list of citations is brief, so I don’t know whether you are aware that there are literally thousands of proposed “information measures” and “complexity measures” in the literature, with almost entirely unknown interrelationships, some of which probably provide examples of your axiomatic approach. In particular, the mathematical ecology literature contains a huge literature on “complexity measures”, some (such as Simpson’s measure) predating Shannon. (Most of the ecologically motivated speculations are profoundly inelegant; some of the mathematically motivated ones are profoundly interesting.) Back around 1994 I wrote two student papers attempting to survey “entropies”, and garnered thousands of references, and venture to guess that the literature has doubled since then.

Yes, I am at least vaguely aware of the multitude of measures out there; picking through them for the interesting ones will no doubt be a Herculean task. I’d be interested in your bibliography if you still have it around. At the very least, this explosion of measures might convince researchers of the utility of a unifying mathematical framework. One can hope.

I would like to point out that, in my current opinion, the notions of “information” and “complexity” are related but distinct. For instance, complexity doesn’t satistfy any kind of data-processing inequality. Sending a received message through a second system can’t increase the amount of information obtained. It may, however, increase the complexity of the message significantly. My intuition tells me there is some mathematical relationship between information and complexity that can be discovered once these terms are defined in the right way.

I’m sorry about your lost comments! My blog is open for discussion; unfortunately, there is no math typesetting software installed as of yet.

Posted by: Ben on March 31, 2008 6:28 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I too sometimes lose work while posting comments or even blog entries. When this happens I swear a vile oath, promise to always compose my comments in another text editor, and then decide that’s too much work.

One trick worth keeping in mind is this. Even when the window for posting comments displays an error message along the lines of “Tough luck, buster! You lost all your work!”, you can sometimes recover your work by right-clicking on the window and then clicking “Back”.

While it’s not perfect, we’ll probably keep the Café in its current format for quite a while, simply because the costs of drastically changing things exceed the benefits.

The next big step will be to set up a wiki, not as a replacement for this blog, but as a repository of definitions, theorems, exposition, etc. It’s coming along slowly…

Posted by: John Baez on April 7, 2008 9:08 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

This stuff looks great! I’ve been thinking about this, too–I did my master’s thesis on algorithmic information theory (AIT) and physics, so I’ve been trying to make it mesh with what I’ve been learning.

A prefix-free code is another name for an instantaneous code; you can tell that the message is over once you read the last bit. A prefix-free Turing machine can be considered as a pair of communicating systems: the listening end will wait forever until it gets enough bits for a code word and then will stop reading, while the sending end will wait forever until all the bits it sends have been read. So unless the sender sends exactly one code word, the message (program) is invalid and the computer goes into an infinite loop.

If you use the Lebesgue measure on binary strings (the measure of an n-bit string is 2 n2^{-n}) then the sum of the measures of valid programs is 1.\le 1. Since the halting programs are a subset of the valid programs, the sum of their measure

(1)Ω M= phaltsonM2 |p|1. \Omega_M = \sum_{p halts on M} 2^{-|p|} \le 1.

This is what Chaitin called the “halting probability” of the prefix-free machine MM, and proved that for every MM there exists c Mc_M such that the shortest program for MM outputting the first nn bits of Ω M\Omega_M is at least nc Mn-c_M bits long.

Tadaki generalized Ω\Omega to a zeta function (though he didn’t know it–he was looking at the fractal dimension of the string). He tossed in a scaling factor:

(2)Ω M(s)= phaltsonM2 s|p|. \Omega_M(s) = \sum_{p halts on M} 2^{-s |p|}.

For every MM there exists c Mc_M such that for all computable ss, the shortest program for MM outputting the first nn bits of Ω M(s)\Omega_M(s) is at least n/sc Mn/s-c_M bits long.

In my thesis, I pointed out that it was a stat. mech. zeta function, that the length of the program was like the energy of a state, and looked at a version that was based on natural numbers instead of binary strings. Tadaki followed up with this paper that looks at things like the temperature, energy, entropy, and specific heat in AIT.

I said that the length was like the energy of a state in statistical mechanics. Now I think it actually has more to do with the action of a path, and I should be using a Wick-rotated zeta function: instead of summing the measures 2 s|p|2^{-s |p|}, sum the actions exp(is|p|)exp(i s |p|). Since actions add when you compose morphisms, you can often just count the generators in the morphism to get its “measure”, like the interactions in a Feynman diagram or the pants/upside-down pants in a 2Cob morphism.

Michel Lapidus at UCR is researching complex dimensions of fractal strings, defined as the zeros of the zeta function of the fractal string. There ought to be some relation between the complex dimensions he’s looking at and this stuff; I showed in my thesis that there’s information about which programs halt stored in the complex zeros of the zeta function of a Turing machine. He and I looked at analytically continuing the zeta function of a Turing machine to the region s1,s \le 1, but I left before we got anywhere with it. It would be really interesting to know what the information content of Ω(s)\Omega(s) is for ss away from the half-line s1.s\ge 1.

It turns out that this way of looking at things also works very nicely with the actor model, a model of computation meant to address concurrent systems (and also happens to have excellent security properties, which is why I’m working with them at Google). ‘Actors’ are generating objects in a symmetric monoidal category, and splitting and combining actors (called “sending/receiving a message”) are morphisms. An ‘actor system’ is an arbitrary tensor product of actors. 2Cob is a very simple actor system where circles are actors, pants is sending a message and upside-down pants is receiving a message.

Any specific morphism out of an actor system is one way in which messages could be exchanged. In the actor model, you typically don’t know in advance in what order the messages will be received, so to write a program, you don’t just talk about a single morphism. Instead, you have to think about all possible evolutions, the set of all morphisms out of an object. There’s an embedding of the terms and rewrite rules of untyped lambda calculus into the objects and morphisms of the actor model such that there’s only one morphism out of any given actor system. But in general you can have many morphisms, and this can be used to do concurrent computations—at the expense of dealing with things like race conditions and deadlock.

Posted by: Mike Stay on March 29, 2008 1:27 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

2Cob is a very simple actor system where circles are actors, pants is sending a message and upside-down pants is receiving a message.

Sorry, 2Cob is a very simple actor model. A bunch of oriented circles is a system in this model.

Posted by: Mike Stay on March 29, 2008 6:17 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thanks for the info! I find the link between AIP and statistical physics very interesting. I wonder if there are any similarities to the work of Ruelle in defining energy, temperature, etc. for general dynamical systems.

It’s my belief that any measure of dimension is also a measure of information, so it would not surprise me if complex dimension of fractal strings satisfy my axioms. Of course, translating concepts into and out of category theory is not always an easy task.

Thanks especially for bringing the actor model to my attention. I’m planning at some point to do a similar category-theoretic analysis of algorithmic complexity measures, and it looks like this model may be a natural starting point.

Posted by: Ben on March 31, 2008 7:18 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

This is a bit late, but when I had a look at this paper, I was reminded of a question I’ve had for a long time: Is there a good or standard infix notation for Hom\mathrm{Hom}?

For instance, something like A CBA\vdash_C B for Hom C(A,B)\mathrm{Hom}_C(A,B) wouldn’t be so bad. Instead of \vdash we might use \triangleright (which doesn’t look so good here), \geq, \models, \gg, \Rightarrow, or really anything that looks like an arrow pointing to the right. Another possibility is to use an actual arrow pointing to the right, but I’m a little nervous about causing confusion with existing notation. It would be even better if we had different notations for internal and external Hom\mathrm{Hom}. This kind of comes up in this paper.

Actually, if there’s any notation that makes the tensor-hom adjunction look really pretty, that would be excellent. Maybe we should consider sub/superscript notation as well as infix and the standard prefix one.

Posted by: James on March 31, 2008 10:19 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Are you talking about internal homs or external homs? Since you mention your desire to make hom-tensor duality look pretty, I’ll assume you mean internal hom. For this, our paper uses a notation that’s standard in linear logic:

ABA \multimap B

created using ‘\multimap’ in TeX. It’s nice because it looks sort of like a right-pointing arrow, but different enough so you can’t possibly confuse it with all the other right-pointing arrows so important in category theory.

I think this counts as pretty:

hom(AB,C)hom(A,BC) hom(A \otimes B, C) \cong hom(A , B \multimap C)

In our ‘logic’ section we use ABA \vdash B to mean the external hom: the set of morphisms from AA to BB. This is not standard practice, as far as I can tell — we just did it to emphasize a certain point we were trying to make.

Posted by: John Baez on March 31, 2008 10:50 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thanks. I did mean either internal or external. Let me try it out.

Let RSR\to S be a ring map, let AA be a right SS-module, let BB be an SS-RR-bimodule, and let CC be a right RR-module. Then the tensor-hom adjunction isA SB RC=A S(B RC).A\otimes_S B \vdash_R C = A\vdash_S (B\multimap_R C).I like it!

For left modules, it won’t look as nice, but that’s because if we like left modules, we should be writing our arrows going from right to left. Then we would want a notation BAB\triangleleft A for homs from AA to BB. If we swap left with right in everything above, then we could writeC RB SA=(C RB) SA.C\dashv_R B\otimes_S A = (C\triangleleft_R B)\dashv_S A.Unfortunately, there doesn’t seem to be a mirror image of \multimap!

Do you think this could catch on? If it does, then surely someone will code up a mirror image of \multimap.

Posted by: James on April 1, 2008 12:22 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

James wrote:

Then the tensor-hom adjunction is A SB RC=A S(B RC). A\otimes_S B \vdash_R C = A\vdash_S (B\multimap_R C). I like it!

You’ll see something almost like this on page 41 of our paper. Check it out! It’s the last of the ‘deduction rules’ listed at the top of the page, the one labelled (c), for ‘currying’. Following the logicians, we use a horizontal double line where you use an equals sign. For us, this means there’s a natural isomorphism between the sets ABCA\otimes B \vdash C and ABCA\vdash B\multimap C.

Do you think this could catch on?

In linear logic, it already has. In real life… well, most people can barely multiply. So, what counts as ‘catching on’ is all relative.

If it does, then surely someone will code up a mirror image of \multimap.

I thought someone already had. Mike Stay might know. We had a lot of trouble in our paper deciding whether homs should go left to right or right to left… this interacts in nasty ways with other arbitrary conventions, with the result that all conventions seem stupid some of the time. But, I don’t think we chose \multimap merely because there was no way to draw the mirror-image version!

Posted by: John Baez on April 1, 2008 9:01 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Actually, now that you mention it, why do people use horizontal lines when stating adjunctions? Why don’t people just use an equality, or an isomorphism sign if they want to be super careful?

Posted by: James on April 2, 2008 12:30 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I’m not completely sure of the history, but I think the use of horizontal lines is due to Lawvere, who was emphasizing that logical rules of inference (as in Gentzen sequent calculus, where the horizontal lines are traditional) are typically based on adjunctions.

I actually like the horizontal lines – for me it often makes the yoga of adjunctions easier to read.

Posted by: Todd Trimble on April 2, 2008 1:01 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

In unicode, it’s character 27DC, ⟜, “LEFT MULTIMAP”. But I don’t know how to generate one in latex (except by using a package for unicode).

Posted by: Mike Stay on April 2, 2008 1:29 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

But I don’t know how to generate one in latex

I use this:

\newcommand\lolli{\multimap}
\newcommand\illol{\mathbin{\mathpalette\reflectwithstyle\multimap}}
\newcommand\reflectwithstyle[2]{\reflectbox{\mathsurround=0pt$#1#2$}}

which defines \lolli to be the right-pointing lollipop, and \illol to be the left-pointing one.

You need to include the graphicx package to get \reflectbox. (In case anyone is wondering, the \mathpalette palaver is needed so that it works in subscripts and so forth.)

Posted by: Robin Houston on April 2, 2008 12:30 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

The pxfonts package contains the inverse multimap symbol, and a few others besides. The following

\documentclass{article}
\usepackage{pxfonts}
\begin{document}
\[
\multimap \quad
\multimapinv \quad
\multimapboth \quad
\multimapdot \quad
\multimapdotinv \quad
\multimapdotboth \quad
\multimapdotbothA \quad
\multimapdotbothB
\]
\end{document}

Produces what you want, and more besides.

The pxfonts package is standard and is available from CTAN. It contains all the glyphs from the AMS maths set and a few extra. As well, it’s a scalable font. I also think it looks a lot nicer than the standard TeX font.

HTH

Andrew

Posted by: Andrew Stacey on April 3, 2008 8:13 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I’ve fixed all the problems I can see with this paper, especially those mentioned above by Theo and Toddexcept for the rather important problem concerning rewrite rules.

I’m still pretty confused by that problem. In email Todd has suggested that he may help us out a bit more. I’d really welcome that!

Let me summarize my confusion once more, in the special case of the braiding (though it extends to all our rewrite rules). Theo suggested that the rewrite rule

(((braidf)x)y)=((fy)x)(((braid f) x) y) = ((f y) x)

was wrong in certain cases. To me, it always seems to be right, since in any braided monoidal category we have

B X,Y(xy)=yxB_{X,Y}(x \otimes y) = y \otimes x

for all ‘global points’ xx and yy, that is, morphisms x:IXx : I \to X and y:IYy : I \to Y. However, it seems to be insufficient to capture the really interesting aspects of the braiding. It only tells you how to do the braiding on ‘global points’. So, I don’t seem able to recover an entire braided monoidal category from a combinator calculus equipped with this rewrite rule.

Todd suggested just ‘chucking’ this rewrite rule, but if I do that, what do I put in its place? And, why is this rewrite rule worse than any other? They all concern global points, at least as we’re formulating them here. So, maybe rewrite rules are a lousy way of trying to describe a braided or even symmetric monoidal closed category… or even a cartesian closed category!

Posted by: John Baez on April 7, 2008 10:16 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Of course, a cheap way out would be to say that every braided monoidal closed category gives a braided monoidal combinator calculus satisfying a bunch of rewrite rules, but not claim anything about the converse.

Posted by: John Baez on April 7, 2008 11:17 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Just a quick comment before I try to say anything more substantial about this business – you’re absolutely right that the rewrite rule for the braiding as applied to global points is correct; this follows from the coherence theorem for braided monoidal categories. I guess I may have been thinking ahead to generalized points, where Theo’s example shows the need for caution, so far as I can tell. Sorry for that confusion.

Posted by: Todd Trimble on April 8, 2008 12:20 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

I have a couple of comments and questions about dinatural transformations:

(1) At the end of page 48, you seem to imply that identity and cut rules lead to dinatural transformations instead of natural ones because of the “different number of variables”. I cannot make sense of this. It seems to me that the reason one need dinatural transformations is the fact that the variable X in the identity rule (and Y in the cut rule) have both positive and negative occurences.

(2) Because dinatural transformations do not compose, you cannot get a 2-category out of them. In my opinion, it breaks the beautiful n-categorical framework you are showing us. Could you comment on this? In the same way you can define a monoidal category as a special case of 2-category, can’t you define dinatural transformations as a special case of a n-categorical notion?

(3) In the same vein, I have the feeling that dual objects in categories are just adjoint in 2-categories with one object. Am I right?

Posted by: Thierry Leduc on September 28, 2008 5:00 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thierry wrote:

It seems to me that the reason one needs dinatural transformations is the fact that the variable X in the identity rule (and Y in the cut rule) have both positive and negative occurences.

You’re right. Our ‘explanation’ of the need for dinatural transformations was sloppy. Luckily it’s not too late for us to fix it. Thanks!

Because dinatural transformations do not compose, you cannot get a 2-category out of them. In my opinion, it breaks the beautiful nn-categorical framework you are showing us. Could you comment on this?

This is a problem Paul–André Melliès and I spent a lot of time on this summer.

It appears that unlike ‘monoidal category’ or ‘symmetric monoidal category’, structures such as ‘monoidal closed category’ or ‘cartesian closed category’ cannot be defined as algebras of a 2-theory in Cat, because variables appear both covariantly and contravariantly — or as you put it, both ‘positively’ and ‘negatively’ — in certain laws.

(See Yanofsky for a convenient introduction to 2-theories: they’re a categorified version of Lawvere’s algebraic theories.)

So, there’s an interesting question: what more general notion ‘theory’ should we use to handle structured categories like these?

When we make some more progress, I’ll report on it here at the Café.

In the same vein, I have the feeling that dual objects in categories are just adjoint in 2-categories with one object. Am I right?

Yes: dual objects in monoidal categories are the same as adjoint morphisms in 2-categories with one object. This is well-known. I spoke about it back in week83, in the Tale of nn-Categories. But alas, this particular review article is avoiding explicit talk of nn-categories — except in one section, where I warn the reader that everything here is just the tip of the iceberg. I wanted to minimize the prerequisites.

Posted by: John Baez on September 28, 2008 10:43 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

1. Following your reply, I read your tale of n-categories (week 83 in particular). I like the graphical way you present adjunction. I wonder whether such string diagrams are possible for natural transformations in general. You show how to represent natural transformations of type 1 –> FG, FG –> 1 or F –> G. But what about the general case, for instance FG –> FGH? What is it in term of string diagram?

2. Did Paul–André Melliès and you make any progress. I cannot wait :-)

Posted by: Thierry Leduc on November 30, 2008 6:20 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thierry Leduc wrote:

I wonder whether such string diagrams are possible for natural transformations in general.

Yes!

You show how to represent natural transformations of type 1 → FG, FG → 1 or F → G. But what about the general case, for instance FG –> FGH? What is it in term of string diagram?

You can probably figure it out yourself. Don’t expect it to look quite as beautiful as for an adjunction, where the string diagram is very pretty. If you get stuck, try this:

  • Ross Street, Categorical structures, Handbook of Algebra Volume 1, editor M. Hazewinkel, Elsevier, Amsterdam 1996.

I wish there were a free online treatment of 2-categorical string diagrams, but I don’t know one.

Did Paul–André Melliès and you make any progress?

Yes!

I cannot wait :-)

I’m afraid you’ll have to wait. We are very slow people.

Posted by: John Baez on December 1, 2008 2:41 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

For a nice pedagogical intro to string diagrams, there’s also Section 2.2 of Aaron Lauda’s paper Frobenius algebras and planar open string topological field theories.

Posted by: Bruce Bartlett on December 1, 2008 4:14 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Simon Willerton gave a great talk called “Two 2-traces” at the last Categories, Logic and Foundations of Physics workshop, and he starts off with a great explanation of higher string-diagram notation. You can watch the video here!

Posted by: Jamie Vicary on December 1, 2008 11:02 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Thanks for that Jamie (though I’m not sure that was my greatest explanation of the diagrammatic approach). Coincidentally, I’m talking on the same subject in Cambridge tomorrow. I’m also supposed to be in the middle of writing this stuff up at the moment.

In the meantime Thierry, there is a bit about graphical representation of natural transformations in my paper A diagrammatic approach to Hopf monads. Section 1 is called ‘The diagrammatics of natural transformations’ but it quickly goes into looking at how these diagrammatics interact with monoidal structures on categories. (I was asked to blog about this paper and have written about 6 different attempts, all dealing with different aspects of the paper – I should finish something!)

I hear that the Catsters have done a video or two on this subject. Have a look at String diagrams, adjunctions and monads.

Posted by: Simon Willerton on December 1, 2008 3:02 PM | Permalink | Reply to this
Read the post Entropy, Diversity and Cardinality (Part 1)
Weblog: The n-Category Café
Excerpt: Entropy in relation to biodiversity and categories
Tracked: October 16, 2008 9:16 AM
Read the post Monoidal Closed Categories And Their Deviant Relatives
Weblog: The n-Category Café
Excerpt: I'm curious to know whether a deviant definition of 'monoidal closed category' is equivalent to the usual one, or see counterexamples if it's not.
Tracked: February 23, 2009 12:19 AM
Read the post New Structures for Physics III
Weblog: The n-Category Café
Excerpt: Mike Stay and I have finished what we hope is the final version of our paper for Bob Coecke's book on New Structures for Physics. Peter Selinger's paper for this book is also done.
Tracked: February 27, 2009 5:05 AM

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Hi, John and Mike,
You wrote an interesting paper. As you are interested in the feedback, I suggest you my remarks.
1. Writing about categorical models of computation, you well represent models of computation based on lambda-calculus. At the same time, there is another developed direction in this area based on automata in categories. It would be beneficial for your paper if you also include an exposition of this direction.
2. It would be also beneficial for your paper if you include an exposition of applications of category theory to biology. Then you will have:
Physics, Biology, Topology, Logic, and Computation
It will support your main idea.
3. * Rosetta Stone is a very good metaphor for this approach. However, categorical analysis of the situation shows: the Rosetta Stone contains a description of the same thing in different languages, while the categorical approach describes different things in the same language. Consequently, these situations are dual. Thus, in terms of category theory, you are creating/describing a co-Rosetta Stone.

* Those who do not know category theory may ignore this remark.

Mark

Posted by: Mark Burgin on March 13, 2009 2:05 AM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

Y.I. Manin wrote an article on the passage “from renormalization to homotopical topology to theory of computation”.

Posted by: Thomas on May 1, 2009 4:22 PM | Permalink | Reply to this

Re: Physics, Topology, Logic and Computation: a Rosetta Stone

A very interesting linguistical tradition in India has some remarkable analogy with “Rosetta-Stone”-ishness: book. I wonder if Weil or other number theorists with knowledge in indian literature mentioned it.

It is a milenium long tradition (slesa) in India (and spreading through east asia, coming up in architecture too) on writing stories which tell two (or more?) different stories at the same time. Imagine a text which tells you the Illiad and the Odyssey simultaneously, without any weirdness or brutal deformations of syntaxt etc. In Sanskrit, this did lead to a change of language, dictionaries etc., in other words, into a kind of linguistic feedback-loop. The indian writer A. K. Ramanujan told it in a story: Once, someone traveled by train from Dheli to Bombay, sitting in the upper berth in the train. Then he left the train for dining at some station in between and came back, entered the train, but - because the upper berth was used by someone else - took the lower one. Well, the sights out of the window looked now a bit strange and the traveller found out that he was riding on the train from Bombay to Dheli now. “Whow!”, he exclaimed, “that’s a great technology! The upper berth of this train rides from Dheli to Bombay, the lower berth in the opposite direction, at the same time!” Ramanujam wanted to illustrate a kind of mental flexibility he thought as characteristic for “indian mentality”. The author of the book thinks of “slesa” as a kind of literature written and read with such mental flexibility.

Posted by: Thomas on August 19, 2011 11:38 AM | Permalink | Reply to this

Post a New Comment