[FOM] A definition of an algorithm
dmulcahey at gc.cuny.edu
Fri Feb 24 07:58:43 EST 2006
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.
More information about the FOM