Re: A Definition of an Algorithm


noson@xxxxxxxxxxxxxxxxxxxxx wrote:
Dear All,


I think this group might be interested in a paper I just posted.
The title is


Towards a Definition of an Algorithm


Abstract: 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.


It can be found here:
http://arxiv.org/abs/math.LO/0602053


The first sentence of your abstract contains a glaring circularity.
Shouldn't you say something more like: "We define an algorithm to be
the set of programs that implement or express an effective procedure"?

--
Joe Legris

.

Relevant Pages

  • Re: A Definition of an Algorithm
    ... implement or express that algorithm. ... partitioned into equivalence classes. ... the set of primitive recursive functions is considered. ... As to your irrelevant comments about trees versus programs as linear ...
    (sci.math.research)
  • Re: Singly Linked LIst and Objects Newbie Question
    ... Hm it seems that my algorithm and datastructure knowledge is really ... I had never even heard of red-black trees or 2-3-4 trees or any ... So for example you want to write an assertion that evaluates a complex ... boolean method1_checkAssert{ ...
    (comp.lang.java.programmer)
  • Re: No trees in the stdlib?
    ... The particular algorithm to achieve this is a secondary issue. ... It's my fault for having opened the topic with simply "trees" instead, it would have avoided this vagueness problem, but I'm genuinely surprised to know there are no data structures that efficiently support such a common need in Python. ... second option, anyway) ...
    (comp.lang.python)
  • A Definition of an Algorithm
    ... Towards a Definition of an Algorithm ... partitioned into equivalence classes. ... the set of primitive recursive functions is considered. ... say when two such trees are ``essentially'' the same. ...
    (sci.math)
  • A Definition of an Algorithm
    ... Towards a Definition of an Algorithm ... partitioned into equivalence classes. ... the set of primitive recursive functions is considered. ... say when two such trees are ``essentially'' the same. ...
    (comp.ai.philosophy)