Re: A Definition of an Algorithm
- From: Aatu Koskensilta <aatu.koskensilta@xxxxxxxxx>
- Date: Sun, 26 Feb 2006 16:00:15 +0000 (UTC)
george wrote:
noson@xxxxxxxxxxxxxxxxxxxxx wrote:
Abstract: We define an algorithm to be the set of programs that
implement or express that algorithm.
This is ALWAYS a BAD idea.
You're being silly again. It's a perfectly natural and reasonable idea.
The set of all programs is
partitioned into equivalence classes.
Two programs are equivalent if
they are ``essentially'' the same program.
I'm going to guess that means they "perform" the
same mapping of input to output.
No, in the paper it is quite clearly stated that two programs are
"essentially" the same if they can be transformed into each other by
certain operations that intuitively don't change "how the programs
achieve" whatever they're doing. Extensional equivalence is certainly
not what is meant as for that we already have the perfectly good notion
of computing the same function.
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.
And in a great many other ways as well.
JEEzus! If THIS is all you are going to do, then
can't you see that ALL you are doing is just
INVENTING ANOTHER PROGRAMMING language?!?
If algorithms are to be sets of programs a programming language is
obviously presupposed. It is an interesting question whether and to what
extent the resulting definition of "algorithm" depends on the (kind of)
programming language chosen.
As to your irrelevant comments about trees versus programs as linear
text, well, they're irrelevant. It would make no difference if the paper
used instead of trees some more familiar syntax for describing primitive
recursive definitions, although the specific transformations would
perhaps look more convoluted and less natural.
--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.
- References:
- Re: A Definition of an Algorithm
- From: george
- Re: A Definition of an Algorithm
- Prev by Date: Re: A Definition of an Algorithm
- Next by Date: Re: Numerically solving a system of polynomial equations
- Previous by thread: Re: A Definition of an Algorithm
- Next by thread: Re: A Definition of an Algorithm
- Index(es):
Relevant Pages
|
