Towards a Definition of an Algorithm

Towards a Definition of an Algorithm

[Noson Yanofsky]

Dear All,

I just put a paper up at http://arxiv.org/abs/math/0602053 .
It should be of interest to many. It uses coherence rules to tell when two
programs are essentially the same algorithm.

Here is the title and abstract:

Towards a Definition of an Algorithm


We define an algorithm to be the set of programs that implement or express
that algorithm. The set of all programs is partitioned into equivalence
classes. Two programs are equivalent if they are ``essentially'' the same
program. The set of all equivalence classes is the category of all
algorithms. In order to explore these ideas, the set of primitive recursive
functions is considered. Each primitive recursive function can be described
by many labeled binary trees that show how the function is built up. Each
tree is like a program that shows how to compute a function. We give
relations that say when two such trees are ``essentially'' the same. An
equivalence class of such trees will be called an algorithm. Universal
properties of the category of all algorithms are given.


Looking forward to hearing any thoughts and criticisms.

I hope to see you all in Nova Scotia at CT 2006 this Summer!

All the best,
Noson (Yanofsky)