[net.misc] Definitions of "algorithm"

bsg (06/23/82)

Several weeks ago, I put out a request for definitions of algorithm.
Replies were mailed to me, and I promised to summarize them.
This is that.

First of all, it was clear from the replies that my query wasn't
properly phrased.  What I was looking for was a "seat_of_the_pants"
definition that I could throw out at cocktail parties.  What I got,
in many cases, were (direct or indirect) detailed mathematical
definitions.  So NO, I have not forgotten my sophomore data
structures course; I know perfectly well what an algorithm is in
recursive function theory.  What I wanted (and got a few of) was
a nutshell definition.

Okay.  Indirect definitions.  I got a lot of "See this (or that)
book for an interesting discussion."  For those interested in following
these leads, the three specific references were to Volume 1 of
Knuth; Hartley Roger's "Theory Recursive Functions and Effective 
Computability;" another recursive function theory book by Brainard
and Landweber.  Non-specific references were to "any recursive function
theory book" and "the introduction/first chapter of any data structures
text."

The people who attempted to give brief definitions all agreed that
an algorithm must halt.  The quotable definitions (in my opinion)
were the following:

	"An algorithm is a sytematic method for describing the
	transformation of input to output."

	"A set of instructions guaranteed to halt."
	(If you see a set of instructions running down the hall,
	find out if it's an algorithm.  If it is, don't
	worry, it'll halt by itself.  If not, you'd
	better run after your instructions.)

	"A set of instructions with the property" (better)
	"that they can be executed by a computing entity
	*without any knowledge of the world save an exact
	understanding of the language of instruction*."

	"[An] algorithm is a method for doing something."

Since I have thrown away the original mail, all of these are quoted 
without attribution.  (At least I had permission!)

The most interesting aspect of the discussion was a strong disagreement
on the question "Is a recipe an algorithm?"
I quote, again without attribution, one opinion on each side.

"Actually, I see nothing
wrong with using the terms "algorithm", and "recipie" somewhat
interchangeably. In statistics, for example (as in other disciplines)
textbooks containing algorithms for data analysis but not much
theory, are in fact known as cookbooks."

"To me a receipe is *not* an algorithm.  Algorithm should mean a mathematical
procedure which in some sense operates on an input to produce an output.
You can stretch the point and claim a receipe has as its input raw materials
and some more "complex" substance as output but the operation performed is
chemical and mechanical in nature (thus a receipe could be called a formula
in the chemical sense - unappetizing! - or a blueprint in the mechanical
sense - worse!)."

I'll leave it there.  Any further discussion should be addressed to 
the net, not to me.  Thanks to all who responded.

                           Billie Goldstein
                           (...!npois!bsg)

mark (06/24/82)

Recipes are very similar to algorithms, but I think they are not necessarily,
for the same reason flowcharts aren't: they aren't usually very
"definite".  That is, the steps of an algorithm should be so basic
that there is absolutely no question about exactly what they mean.
A recipe often contains things like "salt to taste", "brown until done",
etc.  These mean different things to different people.

	Mark

dvk (06/26/82)

References: npois.1372

The definition of algorithm that I like is:

	algos (greek, for pain)
	rythmos (greek, for rhythm, cycling)

algorithm - painful iteration (really, those greek words DO exist).

			-Dan Klein