James wrote:
John, can you explain why you’re interested in lambda calculus? If it’s just that it’s one of your atomic interests, then that’s of course fine, but I suspect your interest in it is based on something else, or at least it originally was.
Great question! Indeed, it’s always upsetting when someone whose work I’m following seems to suddenly switch interests in a discontinuous way - it makes me wonder if I missed some connecting link, or they just got bored with what they’d been doing and jumped to something new. Is there a deeper integrity to their life work, or is it just a bunch of disconnected pieces?
I think about this issue a lot these days - especially in music, where (for example) Miles Davis repeatedly stumped his old fans by switching styles, and Bob Dylan annoyed his by “going electric”. I think the music they made is more enjoyable when you can see the deeper continuities running through their work.
Anyway: for a long time my goal has been to unify our understanding of spacetime with our theory of quantum processes: that’s the big challenge of quantum gravity. So, I got really excited when Rovelli and Smolin introduced spin networks in loop quantum gravity. Spin networks blend in a very nice way some primitive aspects of geometry (graphs) with some primitive aspects of quantum theory (group representations), to give a description of quantum states of the geometry of space.
But, we need to get spacetime into the picture. So, Reisenberger, Rovelli and I introduced spin foams, which are 2-dimensional cell complexes labelled by group representation data. The point is that a slice of a spin foam gives a spin network, just like a slice of spacetime gives a “space”. We can also think of spin foams as a 2-dimensional generalization of Feynman diagrams, which describe the time evolution not of 0-dimensional point particles but of 1-dimensional spin networks.
But, since spin networks already include Feynman diagrams as a special case (taking the group to be the Poincaré group), something funny is going on here: spin foams are like meta-Feynman diagrams going between Feynman diagrams.
This sounds vaguely 2-categorical, and that’s no coincidence. I’d been working on n-categories in parallel with quantum gravity, hoping the two strands of research would converge someday. So for me, right from the start, spin foams were a way to push physics in the direction of -categories.
But, I wanted to see if spin foams could really work as a theory of quantum gravity. So, I spent a bunch of time working with Christensen and Egan on computer calculations with specific spin foam models, trying to see if any reduce to general relativity in the classical limit. The results were sort of depressing: nothing worked the way I expected, and it became ever more clear that we didn’t even know the right questions to ask. So, after a couple of years of this, I decided to give up - or at least take a break. Now Rovelli has some new ideas on this and may be making progress. But I think my skills lie elsewhere.
So, I decided to tackle some other projects. One is higher gauge theory. Another is more philosophical in nature. How can the same gadget - a spin network, or if you prefer, a Feynman diagram - look like a topological entity on the one hand (a graph), and on the other hand represent a quantum process? The answer is that a certain class of categories - symmetric monoidal categories with duals - are simultaneously “spatial” and “quantum-mechanical” in nature. If you think about things this way, it soon becomes clear that many quantum quandaries dissolve if you take this viewpoint: Hilbert spaces and operators are more like “spaces” and “spacetimes” like sets and functions.
Sets and functions form a symmetric monoidal category, but not with duals: they form a cartesian closed category. I had heard many times that cartesian closed categories and the lambda calculus are important for understanding computation, but I never quite understood what that meant. So, I’ve been trying to figure out what people were saying. Since n-categories are a very general formalism for understanding processes, metaprocesses, etc., it would be interesting if we could use them to understand how processes of computation do or don’t resemble the physical processes described by Feynman diagrams.
This is not as crazy as it might first seem, since category-theoretic computer scientists like to use diagrams for describing processes of computation: flow charts, proof nets, and more. And, some of them are even using higher-dimensional diagrams to describe “metaprocesses”, very much like spin foams.
Things get even more interesting when you throw quantum computation into the mix - this lets us see quantum processes as computations of their own special sort, which forbid duplication and deletion of quantum data, but allow entanglement and teleportation. All these differences arises from the difference between symmetric monoidal categories with duals, and cartesian closed categories.
So, in these lectures, I’ve so far been explaining the lambda calculus using diagrams which apply equally well to cartesian closed categories and symmetric monoidal categories with duals: the world of classical computation, and the world of quantum mechanics. These diagrams include Feynman diagrams (or spin networks) as a special case. Next - after I finish sketching how you can build a universal computer using the lambda calculus - I’ll show how you can (and should!) categorify all this stuff to make the process of computation visible. The resulting higher-dimensional diagrams will include spin foams as a special case.
I’m not sure where all this is going, but you can think of it as an extended meditation on the notions of “process”, “metaprocess” and so on - which are really what -categories are all about. Spacetimes, quantum processes, computations, proofs… they all seem to fit into a unified framework, and it’s fascinating to figure how they’re related.
Re: Classical vs Quantum Computation (Week 6)
So your internal composition (p.3) is an example of the bimodule composition, you told us about.