Re: Category Theory of Algorithms

On Tue, 10 Apr 2007 17:03:17 +0200, Mitch <maharri@xxxxxxxxx> wrote:

On Apr 10, 12:32 am, "the.theorist" <the.theor...@xxxxxxxxx> wrote:

> In which area?

The area of studying algorithms as mathematical objects, with closure
under some set of operations.

We're not sure to answer probably because of cultural baggage that
goes with the terms you are using.

'Algorithms' (or anything with algorithm in it) usually refers to the
study of design and analysis of specific problems: e.g. shortest
paths, string matching, matrix multiplication, satisfiability of
logical formulas. Take a particular problem, solve it.

With that in mind, there really isn't much idea of studying operations
on those algorithms; one might study a set of operations that are used
-in- an algorithm, but not operations between algorithms (er... except
maybe reduction).

Well, there also some sort of combination as closure that can be seen, typically, in the definition of primitive recursion (primitive recursive algorithm being those build on certains basics structures and closed by certains operations).

This work later leads to similar characterisation of complexity classes (Implicit Computational Complexity) such as the bounded recursion of Cobham or the safe recursion of Bellantoni and Cook.
Again, they show that the set of functions computed by a given algorithmic schemata (some basic operations and closure by some other operations) is exactly FPtime. Is this really studying operation between algorithms ? I don't know...
These works, and later ones, however, deals with the study of algorithms and not functions in the sense that for a given function some algorithms will be catched and some other won't. Typically almost none of the ICC models I'm aware is able to show that quicksort is Ptime (or even simply terminates) while insertion sort is usually not a problem.

Later works include people such as N. Jones, A. Ben-Amram, C.S. Lee (Size CHange Termination), M. Hofmann (Non Size Increasing programs), K.H. Niggl (\mu mesure), D. Leivant (tiering), J.Y. Marion (my PhD supervisor, tiering also), myself (Quasi-interpretations), L. Kristiansen (mwp bounds), P. Baillot, K. Terui (DLAL), R. Amadio, G. Bonfante, and lots of other people (including numerous PhD and master students whose names I do not all remember).

However, we're not currently really studying algorithms as mathematical objects in a "algebra of algorithms" sense. I guess such an algebra could be build with the right insight but theory of algorithms is quite inexistant (it is not even easy to agree on what is an algorithm, cf also works of Gurevich or Moskovakis) compared to theory of functions so it will probably take some times before such a "structured" achievement can be done.

Now, since nobody has applied Category Theory to the study of
algorithms in the manner I was talking about, perhaps there have been
difficulties, and it's been to hard. If that's the case, then: What,
specifically, are those difficulties?

2) if you really do mean -algorithms-... my imagination is too small
to think of anything other than this line of thought leading back
towards programming language semantics. Maybe if you give a more
specific example of what you're looking for.

I guess one of the main difficutly is to get a precise definition of what is an algorithm, one on which everyone can agree.
Then, I'm not sure category theory will be the best suited tool to do the stuff... I'm currently looking at a way to use a tensor algebra to study algorithm. It's only a wild idea currently even is some examples seem to work quite well...

--
Hypocoristiquement,
Jym.
.