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