Re: A Definition of an Algorithm


Lester Zick wrote:
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.


From my paper:

"We shall define an algorithm analogously to the way that Gottlob Frege

defined a natural number.
Basically Frege says
that that the number 42 is the equivalence class of all sets of size
42. He looks at the set of all finite sets and
makes an equivalence relation. Two finite sets are equivalent if there
is a one-to-one onto function from one
set to the other. The set of all equivalence classes under this
equivalence relation forms the set of natural numbers.
For us, an algorithm is an equivalence class of programs. Two
programs are part of the same equivalence class if they are
``essentially'' the same."

One might say that Frege's defintion is circular because he would say
that "42 is the equivalence relation of all sets of size 42". But he is

not really doing that. Frege is defining the SET of natural numbers.
Not one particular natural number. So too, I am defining the SET
(actually category) of
algorithms. Not one particular algorithm.


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.


I have something very very concreate when I talk about programs.
Equivalence classes of these very concreate things form algorithms.
You might want to look at the paper.


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.

"series of steps" etc is very vaugue. An alchomists also does a series
of steps.

All the best,
Noson

.

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: Algorithm to determine matrix similarity
    ... After that I was told the sorting trick ... my correspondence K:->which satisfies ... I thought I understood your proposed algorithm and implemented ... equivalence relationships. ...
    (sci.math)
  • Re: A Definition of an Algorithm
    ... The first is seemingly endemic to modern forms of definition: ... define an algorithm as an algorithm without defining what algorithms ... that that the number 42 is the equivalence class of all sets of size ... an algorithm is an equivalence class of programs. ...
    (comp.ai.philosophy)
  • Re: 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)
  • Re: Math in Java
    ... JVM startup does take some time. ... most modern being the Berlekamp-Hensel (sometimes called ... LLL algorithm, which is possibly what the site is using. ... Technically speaking the LLL is more modern and is a superior algorithm, ...
    (comp.lang.java.programmer)