Re: A Definition of an Algorithm
- From: lesterDELzick@xxxxxxxxxxxxxxxx (Lester Zick)
- Date: Tue, 21 Feb 2006 21:10:19 GMT
On 20 Feb 2006 19:41:34 -0800, "noson@xxxxxxxxxxxxxxxxxxxxx"
<noson@xxxxxxxxxxxxxxxxxxxxx> in comp.ai.philosophy 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.
It occurs to me that there are two things wrong with this definition.
The first is seemingly endemic to modern forms of definition: you just
define an algorithm as an algorithm without defining what algorithms
are. In other words your definition is a truism; it's circular and
fails to define the subject in exhaustive terms. Even if you were to
substitute another expression such as "an algorithm is a series of
steps" as a definition it still wouldn't tell us what a "series of
steps" or "algorithm" actually mean in mechanically exhaustive terms.
The second objection is more general. You use the phrase "set of all
programs" to define algorithm just the way modern mathematikers use
the phrase "set of all points" to define mathematical objects. But the
problem is mathematical definitions of this form implicitly assume
what they are supposedly defining. For example the conventional
modern mathematical definition for a circle runs "set of all points on
a plane equidistant from any point on the same plane" which is
functionally equivalent to saying a circle is the "set of all points
on a circle" since there is no non geometric point definition for
planes, equidistance, etc.
You can probably just use these expressions colloquially to designate
series of steps, programs, or whatever as long as you don't try to use
such terms in categorically exhaustive terms. Unfortunately it looks
exactly like you're trying to impute some categorical significance to
these kinds of ideas below. Saying various things involve algorithms
doesn't say anything new.
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
I would be very interested in comments, criticism and thoughts.
All the best,
Noson Yanofsky
~v~~
.
- Follow-Ups:
- Re: A Definition of an Algorithm
- From: noson@xxxxxxxxxxxxxxxxxxxxx
- Re: A Definition of an Algorithm
- References:
- A Definition of an Algorithm
- From: noson@xxxxxxxxxxxxxxxxxxxxx
- A Definition of an Algorithm
- Prev by Date: Re: THE PSYCHOPATH - The Mask of Sanity
- Next by Date: Re: A Definition of an Algorithm
- Previous by thread: Re: A Definition of an Algorithm
- Next by thread: Re: A Definition of an Algorithm
- Index(es):
Relevant Pages
|
