Re: A Definition of an Algorithm
- From: "george" <greeneg@xxxxxxxxxx>
- Date: 25 Feb 2006 12:37:48 -0800
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
This group is.
Comp.theory and sci.math.research are not.
Two programs are equivalent if
they are ``essentially'' the same program.
Even after 38 pages, you refuse to get formal about what
it means for two programs to be "essentially the same".
You come closer when you allege that two algorithms
are "essentially the same" if they compute the same
"computable function". But algorithms DON'T compute things:
programs do. More to the point, if you are going to use sorting
as an example, quicksort or mergesort or ANY n lg n sort
is NOT essentially the same algorithm as insertion sort,
bubblesort, or any n^2 sort. These algorithms are different
in an IMPORTANT way, one MORE important than the way
in which they are similar.
Doing this with "computable functions" misses the point,
though: FUNCTIONS are generally DEFINED as having
DOMAINS and RANGES. NECESSARILY. INTRINSICALLY.
As part of their very IDENTITY. My point being that the same
function over two disjoint domains (mapping them to two disjoint
ranges) is generally going to be called TWO DIFFERENT functions
under most formalisms, EVEN IF THEY CAN BE IMPLEMENTED
WITH THE SAME algorithm.
The problem you are trying to address is that all the existing modes
of specifying an algorithm seem one level too specific, seem to require
you to make an arbitrary IRrelevant choice of programming-
language, in which to express them. Seriously, whining about that
makes about as much sense as whining about the fact that you
cannot express numbers without first picking some numerals.
But if you retreat to functions, you get another problem of over-
specification: you have to specify A DOMAIN for the function, despite
the fact that you may not CARE. Addition is addition and it doesn't
MATTER whether I'm adding naturals, integers, rationals, reals, or
complex numbers. It also doesn't matter what subsets of any of
those domains I may have chosen to exclude. There are other kinds
of addition for which these things DO matter but if my "algorithm"
is for "addition"[of the USUAL variety] then I'm NOT TALKING about
those other kinds.
.
- Prev by Date: Re: A Definition of an Algorithm
- Next by Date: Peano's Axioms from the Field Axioms alone?
- Previous by thread: Re: A Definition of an Algorithm
- Next by thread: Peano's Axioms from the Field Axioms alone?
- Index(es):
Relevant Pages
|
|
