## Friday, February 03, 2006

### Category theory and ontology

I've long harboured the hope that the rise of category theory will push philosophy in interesting directions, and this in two ways: (1) Providing metaphysics with new tools; (2) Making us think harder about the nature of enquiry if a 4000 year old discipline continues to seek to improve its basic language. Concerning (1), it wouldn't surprise me if much of the category theoretic 'metaphysics' gets done by computer science people and physicists. After all, database theorists have to deal with quesions of type and identity all the time. During the IMA n-categories workshop, Michael Johnson gave John Baez and me a fascinating lesson in all this along the banks of the Mississippi.

Today the ArXiv has on offer Towards a Definition of an Algorithm by Noson S. Yanofsky. Defining the concept of an algorithm is surprisingly hard. It's easy enough to give examples of programs you'd want to say carried out the same algorithm, but how would you make the equivalence relations of sameness explicit in the following schema?
Discipline          Objects

Programming Programs

Computer Science Algorithms = Programs/~

Mathematics Computable Functions = Algorithms/~

It sounds like a great topic for a philosopher, and indeed we are pointed to: W. Dean. What algorithms could not be. 2006 Thesis in Department ofPhilosophy. Rutgers University.

Yanofsky goes on to say:

Whether or not two programs are essentially the same, or whether or not a program is an implementation of a particular algorithm is really a subjective decision. We give relations that most people can agree on that these two programs are "essentially" the same, but we are well aware of the fact that others can come along and give more relations. (p. 3)

There's a danger in using the word 'subjective' of decisions to mean one can't at present decide in a way that one thinks won't be challenged in the future. For one thing, much of what you say will have to be given this label, with its relativist connotations. I've never much liked the epithet as used in Subjective Bayesianism to distinguish a position which simply requires our degrees of belief to satisfy the probability axioms, in opposition to Objective Bayesianism where given an agent's state of knowledge there is one rational choice for their degrees of belief. The term almost lends itself to the criticism sometimes heard from non-Bayesians that Bayesians could lock themselves up in a dark room and feel happy, safe in the knowledge that their degrees of belief are coherent. Subjective Bayesians can still think there is a duty upon them to find out what they can and make responsible assessments of plausibilities. Michael Polanyi's choice of 'personal' in Personal Knowledge relates strongly to this sense of responsibility. For some comments on Polanyi see my November 12 post.

Back to category theory, according to Yanofsky, 'The category of algorithms is the initial free category with a strict product that is closed under recursion (i.e., has a natural number object).' I strongly suspect that category theory will prove to be the only viable language to cope with the subtle relations of sameness involved here in computer science, and also elsewhere. For more about category theory and computation, check some of the lectures in the Geometry and Computation programme.

Furthering the project of categorifying physical ontology, Aaron D. Lauda and Hendryk Pfeiffer have just written State sum construction of two-dimensional open-closed Topological Quantum Field Theories .

Kea said...

Wow. I just had a look at Selinger's homepage. At a first glance, 'control' has something to do with the sort of controls implemented in, say, quantum gates. This is very interesting. I'd be glad to hear more about this!

David: I only recently stumbled across your wonderful blog!

February 04, 2006 8:50 PM
urs said...

Some comments on the Lauda&Pfeiffer paper can be found over at the SCT.

February 06, 2006 5:37 PM
Anonymous said...

From a quick skim of his paper, it would seem that Noson Yanofsky's answers to the question of when two algorithms are equivalent is novel. But the question itself is not. Indeed, there is an entire branch of computer science devoted to the study of the semantics of computer programs and of computer progamming languages, none of which work is cited in this paper. Pity.

February 07, 2006 7:57 PM