Thursday, March 25, 2010

Categories list - 20 years old!

I notice that the Categories List, started and maintained by Bob Rosebrugh, is now 20 years old. The advertisement (see below) for the list was first sent out on 11th March 1990. My email address then was munnari!!

We category theorists owe a great deal to Bob Rosebrugh for this initiative, and for his other creation the on-line journal Theory and Applications of Categories.
Among other things he has dealt very calmly and competently with the little crises which tend to occur on such lists.

Thank you, Bob.

(I think I played a small (very small) part in the creation. Some years prior I spoke at every categories conference about the importance of email and the internet. I will have to look up the date, I think it was around 1983/1985.)

March 11,1990

Dear Colleague:

This letter is to announce the availability of a Bulletin Board for Category
Theory on BITNET. The address is CATEGORIES@MTA.BITNET.

The intention is to operate in a manner similar to the Types Bulletin Board.
To join the mailing list, simply send a message to:


After confirmation of two-way transmission your name will be added to the list.
Please provide a very complete return address. To distinguish messages for
forwarding from others of an administrative nature, please mail to Categories
ONLY messages which are intended to be forwarded. All other messages should be
sent to categories-request@mta.bitnet, or to me ( rrosebrugh@mta.bitnet )

Anyone may submit (electronically only) any material about Category Theory (and
only about Category Theory) for distribution - abstracts, announcements of
results or meetings, queries, or full papers. Material will be forwarded as
received unless there is evidence that the message received is garbled. The
initial committment is that turn-around times will not exceed a couple of days.

TeX files are welcome in any flavour - plain, AmSTeX or LaTeX. They should
include a Character Code Reference which is available on request.
Unfortunately, until we see how well this works, there can be no committment to
either authors or subscribers regarding accuracy of TeX files transmitted. TeX
preprints will be archived separately, and a catalogue of them will be
published irregularly. Macro packages are the responsibility of the author,
however an attempt will be made to archive versions of diagram macro packages.

I gratefully acknowledge assistance from David Jones at Types who suggested
some of the procedures to be used. Electronic addresses to which this is being
sent are taken from lists provided by Mike Barr and Max Kelly, and I thank
them (and Mike Johnson who transmitted Max's list.)

Those seem to be the main points. Looking forward to a useful exchange,


Bob Rosebrugh
/TO categories@mta.bitnet
/BC Mike Barr ,
Francis Borceux ,
Aurelio Carboni ,
Peter Freyd ,
Mike Johnson ,
Paul Johnson ,
Stefano Kasangian ,
Fred Linton ,
Phil Mulry ,
Susan Niefield ,
Bob Pare ,
Andy Pitts ,
Pino Rosolini ,
Dietmar Schumacher ,
Phil Scott ,
Robert Seely ,
Ross Street ,
Paul Taylor ,
Bob Walters ,
Charles Wells ,
Richard Wood

The following message has been sent out to about 100 addresses from
Mike's and Max's address lists. On the assumption that anyone I have heard
from wishes to be included on the subscriber list, I have included you already.
Let's see how it goes.



Wednesday, March 24, 2010

Impossibility proofs

Proofs that something is impossible (the solution of quintic equations in radicals, squaring the circle, etc) have been crucial in mathematics since they require a very precise understanding. This has also been true in computer science: the impossibility of calculating the halting function requires a precise formulation of computability.

I have been thinking about the impossibility of more particular constructions in practical programming languages. One I have in mind is the following: in C is it possible to write a function which given two pointers to functions returns a pointer to the composite function? I don't think so. People (for example, Yuri Gurevich) have claimed to give a precise meaning to C and hence an impossibility proof is conceivable. I would like to see such a proof (or an example program refuting my conjecture).


Monday, March 01, 2010

Applied Algebra

By algebra I don't mean the usual groups, rings, fields, vector spaces etc of a mathematics course. Algebra is much more general, and involves considering the operations on things, and of course equations between these operations.

In applying algebraic ideas to a new field the first problem is to decide what are the basic operations. You don't see this problem in a classical algebra course because the operations of symmetries (groups), quantities (rings, and fields) have long since been clarified. In a new field the choice is very difficult and a bad choice leads to endless complication and confusion.

I have written about this in earlier posts: the parallel operation on processes seems to me to be misguided; the operations on relations in the algebra called "allegories" also seems to me to be misguided. I have suggested alternatives.

Here is another example from the book by Ferenc Gecseg on Products of Automata (Monographs in Theoretical Computer Science, An EATCS Series). A sequential machine has a set of states A, an input alphabet X and an output alphabet Y. It has also a transition function AxX->A and an output function AxX->Y. Now Gecseg defines a "product of sequential machines" as follows:
Click here for the definition.

The definition looks complicated, but even more complicated is the graphical representation:

This graphical representation suggests that there are much simpler operations, with the property that Gecseg's operation is a derived operation. The real entities are the boxes with wires on the boundaries. The real operations are the series and parallel operations, together with certain wire constants. Gecseg's operation is a derived operation in the algebra Span(Graph).

Labels: , ,