Date: Thursday, 15 November 1984 16:21 mst From: James J. Lippard Subject: Miscellaneous Digest V3 #35 Reply-To: {mbx >udd>Multics>Lippard>misc>misc} To: {list >udd>Multics>Lippard>misc>misc} Miscellaneous Digest Volume 3 : Issue 35 Today's topics: Litany Against Fun Malgorithms (from AI-List) ---------------------------------------------------------------------- Date: Tuesday, 13 November 1984 18:25 mst From: Jon Rochlis Subject: from gloria ... maybe for the next misc ... ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The Litany Against Fun, ---------------------- from "National Lampoon's DOON" I must not have fun. Fun is the time-killer. Fun is for children, customers, and the help. I will forget fun. I will take a pass on it. And while it is going, I will turn a blind eye toward it. When fun is gone there will be nothing. Only I will remain - I, and my will to win. Damn, I'm good. ------------------------------ Date: Friday, 9 November 1984 15:04 mst From: Charlie Spitzer Subject: Malgorithms (from AI-List) From: BIESEL@RUTGERS.ARPA Subject: Taxonomy of malgorithms. Now that the concept of malgorithms has been defined it behooves us as serious scientists to classify the different kinds of malgorithms, to write learned papers in obscure journals, and to generally do everything to bring scholarly respectability to this heretofore underrecognized area of computer science. The following is a modest contribution to the establishment of a taxonomy of malgorithms. The notion of an optimal algorithm is an old one, and the definition of of optimality in time, say, or in storage is straightforward. The little "o" and the big "O" notation is well established and suffices to define the complexity of an algorithm (except for a constant or two), and thus permits the comparison of two algorithms for the same problem. The optimal algorithm is therefore simply that algorithm which has the lowest time complexity for any given problem. Often it is possible to prove mathematically that the best possible algorithm for a given class of problems cannot do better than some lower bound. The converse of this, the worst possible algorithm, is not as easily defined. Is the worst possible algorithm one that never finishes, while wiping out every piece of storage and tying up your computer until you unplug it? Or, more insidious, does this algorithm appear to run normally, generate recognizable output, but produce results that are subtly wrong, so wrong as to cause maximum damage when the results are used? If we restrict our considerations only to those algorithms that actually produce the correct result, but do so in the longest possible time, we run into other problems. The concept of 'longest possible time' is ill-defined, since we do not know the temporal extent of the universe. Neglecting for the moment the relatively trivial problem of how to keep a computer running forever ( a hardware problem, and therefore not worthy of our consideration), we still need to define some upper bounds on the time intervals we are considering. Assumption 1: The universe will exist forever. Definition 1: Any algorithm that runs forever before it produces the correct result is a member of the class "Aleph Zero". Extensions to algorithms that take longer than this are made in the obvious way (i.e. classes aleph one etc.). The development of such an algorithm is left as an exercise to the reader. Assumption 2: The universe will exist until some terminal climactic event. Definition 2: Any algorithm that runs a finite amount of time, and produces its output at the last moment of existence, is a member of the class "Gabriel". (members of non-Christian religions may wish to substitute a climactic event of their own choice). While the classes thus far defined would appear to specify theoretical upper bounds for malgorithm execution times, some practitioners may be concerned with malgorithms that take into account the limitations of present hardware configurations. While this kind of pandering to mechanical strictures is abhorrent to every theoretician, some precedents exist in the literature, and we will accordingly briefly touch upon the subject here. Suppose we have devised a malgorithm which can run an arbitrary amount of time before producing its result. The task now becomes one of maximizing this time, subject to the constraints formed by the finite MTBF of the hardware, and the equally finite tolerance threshold of the person waiting for the result. Definition 3: Any malgorithm which produces its output at the last possible instant before either the hardware fails, or the user terminates the program is a member of class "Epsilon". As an aside, malgorithms of this class will usually require some additions to the operating system to recognize an attempt to cancel the program execution. Hardware modifications, in the form of energy storage systems to permit the program to print its output after the frustrated user has pulled the power plug, will probably also be necessary. It should be noted that malgorithms of class "Epsilon" have an unfortunate flaw: since they produce output whenever they are terminated by the user, they are also the fastest possible algorithms for any problem, being limited only by the speed with which the user can pull the plug. Once malgorithms of this class have become established, future work in computational speedup will likely focus on fast switches for power cutoff. Now that we have defined some upper bounds on theoretical malgorithm performance, we would like to define some additional classes of actual malgorithms, primarily for taxonomic purposes. The classes below are only a beginning, and the reader is invited to contribute additional definitions and examples to the discussion. The classes are not maximal or minimal in any sense, but merely define some categories of malgorithms. Example malgorithms should be easily recognized as falling into one or another of the classes defined. Definition 4: Malgorithms which employ recursion to solve a problem for which there exists a closed form solution are members of class "Fibonacci". Definition 5: Malgorithms which solve a problem by exhaustive generation of all permutations, when there is any alternative solution, are members of class "Salesman". Definition 6: Malgorithms which apply a general algorithm to the wrong size problem are members of class "Heapsort". Example: Heapsort applied to the list 1,3,2. Definition 7: Malgorithms for Monte-Carlo solutions to analytic functions are members of class "Pi". Definition 8: Malgorithms which provide a solution to a problem by solving a more complex isomorphic problem are members of the class "Gauss". Example: Multiplication of two numbers by adding their logarithms. Definition 9: Malgorithms which perform redundant computations are members of class "Sheep". Example: Determining the number of sheep in a herd by counting the number of legs and dividing by four. It should be noted that the classes proposed here are neither exhaustive, nor are they mutually exclusive. Most current programs contain algorithms which upon inspection are really malgorithms that fall into one or more of the classes here defined. It is our devout hope that this short note will lead to a more intensive investigation of this much neglected area of computer science. The author is convinced that this area can provide subject matter for several Ph.D. dissertations at the more mathematically rigorous institutions of higher learning, and wishes to express his gratitude to the contributors to the Ailist, who have given the impetus for this important work. Biesel@Rutgers.ARPA ------------------------------ End of Miscellaneous Digest ***************************