Here is a dialogue I read recently about implementing Windows XP:
Daniel de França: Hi John! If I am very patient, may I be able to write Windows XP using manifolds and cobordisms? […]
John Baez: 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!
Manifold and cobordism are things used in topology: manifolds represent spaces, and cobordisms represent mappings between them. String theory is based on them, so if string theory is correct, XP already runs using manifolds and cobordisms. Like the rest of the Universe. But why should anyone discuss this? That dialogue took place on the n-Category Café blog, and was about a new paper by John Baez and Mike Stay called Physics, topology, logic and computation: a Rosetta Stone.. The paper explains how, using a branch of maths called category theory, one can show an equivalence between four sets of ideas from different regions of science. These are: manifolds and cobordisms, in topology; states and processes that transform them, in physics; datatypes and functions that map between them, in computing; propositions and proofs that prove one from another, in logic. This equivalence will help us design quantum computers. Which is what Microsoft are doing in Project Q! Category theory has (I believe) vast power and potential in other parts of computing too, and in cognitive science. So, with applications that include neural networks, quantum teleportation, spreadsheets, analogical reasoning and metaphor, software specification, the way humans recognise similar concepts, and General Systems Theory, I thought I'd blog a series of posts about uses of category theory.
My own work on spreadsheets, which I blogged in Spreadsheet Components, Google Spreadsheets, and Code Reuse and Which Spreadsheet Components Would You Like to See?, was inspired by category theory, so that's where I'll start. After all, surely we don't associate spreadsheets with any maths more advanced than accounting and the occasional spot of tax fraud?
One day in Oxford, I walked into a room called KB7. The initials stood for "Keble Road Basement", because the room was in a basement on Keble Road, not far from Keble College. The basement belonged to the Oxford University Computing Lab, and I'd gone there to drag a friend out to the pub. But our drinking session got delayed, because on my friend's desk, I discovered a paper by his supervisor Joseph Goguen.
This paper, Sheaf Semantics for Concurrent Interacting Objects, turned out to be Goguen's most recent publication on research he started in the 60s: a mathematical formalisation of what it means for something to be an object, and what it means to build a system out of interacting objects. It attracted me because I was teaching Artificial Intelligence, and I'd been building "microworlds": game-like worlds for students to run their AI programs in. Such worlds contain interacting objects: for example, an artificially intelligent virtual animal might interact with virtual food by eating it, and with virtual predators by killing them. Common practice would be to code the objects in C++ or whatever, but the paper seemed to offer a more elegant, and more fundamental, approach to object-oriented programming.
However, it applied to much more. Indeed, Goguen viewed it as an important contribution to General Systems Theory. This is an interdisciplinary branch of science that studies the organisation and dynamics of systems as a whole, at a level of abstraction that doesn't depend on what the systems are made of.
(Feedback is an example of a concept at this level. We talk about negative feedback in amplifiers to stabilise frequency response and gain; but also in animals, to regulate blood sugar, and water, and sodium, and other things. It doesn't matter that amplifiers and animals are made from different stuff.)
Goguen's work was at the same level of abstraction, and you can see how general he thought it was from the abstract he wrote:
This paper uses concepts from sheaf theory to explicate phenomena in concurrent systems, including object, inheritance, deadlock, and non-interference, as used in computer security. The approach is very general, and applies not only to concurrent object oriented systems, but also to systems of differential equations, electrical circuits, hardware description languges, and much more. Time can be discrete or continuous, linear or branching, and distribution is allowed over space as well as time. Concepts from category theory help to achieve this generality: objects are modeled by sheaves; inheritance by sheaf morphisms; systems by diagrams; and interconnections by diagrams of diagrams. In addition, behaviour is given by limit, and the result of interconnection by colimit.
To be continued...