Re: A Definition of an Algorithm
- From: "george" <greeneg@xxxxxxxxxx>
- Date: Sat, 25 Feb 2006 23:00:16 +0000 (UTC)
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.
This is ALWAYS a BAD idea. Your expectation that it might've
been a defensible idea rests on the fact that Frege did it that way.
What SHOULD'VE alerted you to the fact that it was
a bad idea was the fact that DESPITE the fact that Frege did it that
way, WE QUIT doing it that way.
Nowadays, in the most usual set theories,
a natural number is NOT some equivalence class
with more members THAN THERE ARE natural numbers,
or even than there are sets. Nowadays, small natural
numbers are SMALL things represented by SMALL sets
(the smaller the number, the smaller the set).
That whole approach is just fundamentally backwards.
It invites you to think that the class of sets-of-size-3 has to be
understood BEFORE what "3" is is understood. That cannot
factually be the case. In real life, you have to understand what
3 is, FIRST, IN ORDER to tell what sets to put into the equivalence
class and which to leave out. The same is obviously going to be
true of "algorithms".
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. The textbook did begin by
stressing that that was necessary (even though it is obviously
not sufficient).
The set of all equivalence
classes is the category of all algorithms.
If you want a category-theoretic treatment (as opposed to
a set-theoretic treatment) of algorithms, then surely the
best first place to look for inspiration would be to a category-
theoretic treatment of the natural numbers. Have you found one?
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?!?
SURELY the WHOLE point to THIS enterprise, if it
can have a point, is to achieve INDEPENDENCE from a
particular programming language! Or are you saying that
a language built with binary trees is fundamentally different
from a linear/verbal/syntactic language? I'm sorry, you can't
defend THAT distinction; the mere existence of the phrase
"parse tree" (for compiling the verbal/syntactic languages)
proves THAT.
Each tree is like a program that shows how to compute a function.
That is re-inventing the wheel.
How is this going to look any different from the parse-tree
generated from compiling an implementation of the same
function in a third-generation IMPERATIVE language?!?
EITHER way, you get a binary tree that can be used to compute
the program.
We give relations that
say when two such trees are ``essentially'' the same.
That is a lot more than you need to give.
They are going to be essentially the same if their outputs
agree on agreeing inputs and if they are of similar complexity.
That was known BEFORE you got started.
An equivalence class of such trees will be called an algorithm.
Universal properties of the category of all algorithms are given.
That is an irrelevant misuse of category theory.
.
- Follow-Ups:
- Re: A Definition of an Algorithm
- From: Aatu Koskensilta
- Re: A Definition of an Algorithm
- From: noson
- Re: A Definition of an Algorithm
- Prev by Date: Two papers published by Geometry & Topology
- 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
|
