Algorithm

An algorithm is a recipe, method, or technique for doing something. The essential feature of an algorithm is that it is made up of a finite set of rules or operations that are unambiguous and simple to follow (computer scientists use technical terms for these two properties: definite and effective, respectively). It is obvious from this definition that the notion of an algorithm is somewhat imprecise, a feature it shares with all foundational mathematical ideas -- for instance, the idea of a set. This imprecision arises because being unambiguous and simple are relative, context-dependent terms. However, usually algorithms are thought of as recipes, methods, or techniques for getting computers to do something, and when restricted to computers, the term "algorithm" becomes more precise, because then "unambiguous and simple to follow" means "a computer can do it." The connection with computers is not necessary, however. If a person equipped only with pencil and paper can complete the operations, then the operations constitute an algorithm.

A famous example of an algorithm (dating back at least to Euclid) is finding the greatest common divisor (GCD) of two numbers, m and n.

Step 1. Given two positive integers, set m to be the larger of the two; set n to be the smaller of the two.
Step 2. Divide m by n. Save the remainder as r.
Step 3. If r = 0, then halt; the GCD is n.
Step 4. Otherwise, set m to the old value of n, and set n to the value of r. Then go to step 2.

A tax form is also a relatively good example of an algorithm because it is finite and the instructions for completing it are mechanically and finitely completable (at least that is the intention). The recipe for cowboy chocolate cake (with two mugs of coffee) is not really an algorithm because its description is not definite enough (how much is a mug of coffee?). Of course, all computer programs are algorithms.

It should also be noted that algorithms are by no means restricted to numbers. For example, alphabetizing a list of words is also an algorithm. And, one interpretation of the computational hypothesis of the mind is that thinking itself is an algorithm -- or perhaps better, the result of many algorithms working simultaneously.

Now to flesh out the definition. An algorithm is an unambiguous, precise, list of simple operations applied mechanically and systematically to a set of tokens or objects (e.g., configurations of chess pieces, numbers, cake ingredients, etc.). The initial state of the tokens is the input; the final state is the output. The operations correspond to state transitions where the states are the configuration of the tokens, which changes as operations are applied to them. Almost everything in sight is assumed to be finite: the list of operations itself is finite (there might be a larger but still finite set from which the operations are drawn) and each token is itself finite (or, more generally, a finitely determinable element in the set). Usually, the input, output, and intermediate sets of tokens are also finite, but this does not have to be the case, at least in theory; indeed these sets can be continuous (see Blum, Shub, and Smale 1989). An algorithm describes a process that the tokens participate in. This process (a computation) is either in a certain state or it is not, it may either go to a certain next state from its current state or it may not, and any transition taken is finite. (One way to relax this definition is to allow the state transitions to be probabilistic, but that doesn't affect their finiteness.)

And finally, in more technical parlance, an algorithm is an intensional definition of a special kind of function -- namely a computable function. The intensional definition contrasts with the extensional definition of a computable function, which is just the set of the function's inputs and outputs. Hence, an algorithm describes how the function is computed, rather than merely what the function is. The connection with computable functions is crucial. A function F is computable if and only if it is describable as an algorithm. The relationship between the extensional definition of F and an intensional definition of it is interesting. There is one extensional definition of F, but there are an infinite number of intensional definitions of it, hence there are an infinite number of algorithms for every extensionally-described computable function F. (Proof: you can always construct a new, longer algorithm by adding instructions that essentially do nothing. Of course, usually we seek the canonical algorithm -- the shortest and most efficient one.)

A computable function is a function whose inputs and outputs can be produced by a Turing machine. Church's thesis states that all the computable functions can be computed by a Turing machine (see CHURCH-TURING THESIS). The best way to understand Church's thesis is to say that Turing computability exhausts the notion of computability. Importantly, not all functions are computable, so not all functions are algorithmically describable (this was a profound discovery, first proved by TURING 1936; Church 1936a; and Kleene 1936; it and related results are among the greatest achievements of twentieth-century mathematics).

Sometimes algorithms are simply equated with Turing machines. The definition given here is logically prior to the notion of a Turing machine. This latter notion is intended to formally capture the former. Gödel (1931; 1934), among his other achievements, was the first to do this, to link a formal definition with an intuitive one: he identified a formally defined class of functions, the recursive functions, with the functions that are computable, that is, with the functions for which algorithms can be written.

This completes the definition of "algorithm." There are a few loose ends to tie up, and connections to be made. First, mathematicians and computer scientists sometimes sharply restrict the definition of "algorithm." They take the definition of "algorithm" given here, and use it to define the notion of an effective procedure. Then they define an algorithm as an effective procedure that always halts or terminates (not all procedures or computer programs do terminate -- sometimes on purpose, sometimes accidentally).

Second, in common parlance, an algorithm is a recipe for telling a computer what to do. But this definition does more harm than good because it obliterates the crucial notion of a virtual machine, while it subtly reinforces the idea that a homunculus of some sort is doing all the work, and this in turn can reinforce the idea of a "ghost in the machine" in the COMPUTATIONAL THEORY OF MIND. So this folk definition should be avoided when precision is needed. Another problem with the folk definition is that it does not do justice the profundity of the notion of an algorithm as a description of a process. It is fair to regard algorithms as being as crucial to mathematics as sets. A set is a collection of objects. An intentional definition of a set describes all and only the objects in the set. An algorithm describes a collection of objects that does something. It would be impossible to overstate the importance of this move from statics to dynamics.

Third, the connection between algorithms and COMPUTATION is quite tight. Indeed, some mathematicians regard algorithms as abstract descriptions of computing devices. When implemented on a standard computer, such descriptions cease to be abstract and become real computing devices known as virtual machines (virtual does not mean not real, here). A virtual machine is the machine that does what the algorithm specifies. A virtual machine exists at some level higher than the machine on which the algorithm is implemented. For example: a word processor is a virtual machine that exists on top of the hardware machine on which it is implemented. The notion of a virtual machine is very important to cognitive science because it allows us to partition the study of the mind into levels, with neurochemistry at the bottom (or near the bottom) and cognitive psychology near the top. At each level, different methods and technical vocabularies are used. One of the crucial facts about virtual machines is that no one machine is more important than the rest. So it is with the brain and the rest of the nervous system that make up thinking things. Theories at all levels are going to be needed if we are to completely and truly understand the mind.

References

Blum, L., M. Shub, and S. Smale. (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines. Bulletin of the American Mathematical Society 21(1):1-46.

Church, A. (1936a). A note on the entscheidungsproblem. Journal of Symbolic Logic 1:40-41, 101 - 102.

Gödel, K. (1931). On formally undecidable propositions of Principia Mathematica and related systems I. Monatschefte für Mathematick und Physik 38:173-198. (Reprinted in J. Heijenoort, Ed., (1967), From Frege to Gödel. Cambridge, MA: Harvard University Press, pp. 592 - 617.)

Gödel, K. (1934/1965). On undecidable propositions of formal mathematical systems. In M. Davis, Ed., The Undecidable. New York: Raven Press, pp. 41-71.

Kleene, S. C. (1936). General recursive functions of natural numbers. Mathematishe Annelen 112:727-742.

Turing, A. (1936). On computable numbers with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society series 2, 42:230-265 and 43: 544 - 546.

Algorithm

See also

References

Further Readings