[FOM] A definition of an algorithm

[Dustin Mulcahey]

A colleague of mine has posted a very interesting paper.  I thought  
some of you would be interested.

His name is: Noson Yanofsky.

The title is: "Towards a Definition of an Algorithm."

The abstract is:
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.

The paper can be found at: http://xxx.lanl.gov/abs/math.LO/0602053

The fact that an "algorithm" is hard to define (as opposed to a  
"program") makes the question
very interesting. I think Noson has an interesting and novel  
solution.  I am, however, personally curious as to any other efforts  
on this front.

Dustin Mulcahey