Algorithm

An algorithm is any well-defined procedure for solving a given class of problems. Ideally, when applied to a particular problem in that class, the algorithm would yield a full solution. Nonetheless, it makes sense to speak of algorithms that yield only partial solutions or yield solutions only some of the time. Such algorithms are sometimes called "rules of thumb" or "heuristics."

Algorithms have been around throughout recorded history. The ancient Hindus, Greeks, Babylonians, and Chinese all had algorithms for doing arithmetic computations. The actual term algorithm derives from ninth-century Arabic and incorporates the Greek word for number (arithmos ).

Algorithms are typically constructed on a case-by-case basis, being adapted to the problem at hand. Nonetheless, the possibility of a universal algorithm that could in principle resolve all problems has been a recurrent theme over the last millennium. Spanish theologian Raymond Lully (c. 1232–1315), in his Ars Magna, proposed to reduce all rational discussion to mechanical manipulations of symbolic notation and combinatorial diagrams. German philosopher Gottfried Wilhelm Leibniz (1646–1716) argued that Lully's project was overreaching but had merit when conceived more narrowly.

The idea of a universal algorithm did not take hold, however, until technology had advanced sufficiently to mechanize it. The Cambridge mathematician Charles Babbage (1791–1871) conceived and designed the first machine that could in principle resolve all well-defined arithmetic problems. Nevertheless, he was unable to build a working prototype. Over a century later another Cambridge mathematician, Alan Turing (1912–1954), laid the theoretical foundations for effectively implementing a universal algorithm.

Turing proposed a very simple conceptual device involving a tape with a movable reader that could mark and erase letters on the tape. Turing showed that all algorithms could be mapped onto the tape (as data) and then run by a universal algorithm already inscribed on the tape. This machine, known as a universal Turing machine, became the basis for the modern theory of computation (known as recursion theory) and inspired the modern digital computer.

Turing's universal algorithm fell short of Lully's vision of an algorithm that could resolve all problems. Turing's universal algorithm is not so much a universal problem solver as an empty box capable of housing and implementing the algorithms placed into it. Thus Turing invited into the theory of computing the very Cartesian distinction between hardware and software. Hardware is the mechanical device (i.e., the empty box) that houses and implements software (i.e., the algorithms) running on it.

Turing himself was fascinated with how the distinction between software and hardware illuminated immortality and the soul. Identifying personal identity with computer software ensured that humans were immortal, since even though hardware could be destroyed, software resided in a realm of mathematical abstraction and was thus immune to destruction.

It is a deep and much disputed question whether the essence of what constitutes the human person is at base computational and therefore an emergent property of algorithms, or whether it fundamentally transcends the capacity of algorithms.

see also complexity

Bibliography

berlinski, david. the advent of the algorithm: the idea that rules the world. new york: harcourt brace, 2000.

hodges, andrew. alan turing: the enigma. new york: simon & schuster, 1983.

leibniz, gottfried wilhelm. theodicy, ed. austin marsden farrer. lasalle, ill.: open court, 1985.

rogers, hartley. theory of recursive functions and effective computability. cambridge, mass.: mit press, 1987.

turing, alan m. collected works of a. m. turing: mechanical intelligence, ed. darrel. c. ince. amsterdam and london: north holland, 1992.

william a. dembski

Algorithm

An algorithm is a set of instructions for accomplishing a task that can be couched in mathematical terms. If followed correctly, an algorithm guarantees successful completion of the task. The term algorithm is derived from the name al-Khowarizmi, a ninth- century Arabian mathematician credited with discovering algebra. With the advent of computers, which are

KEY TERMS

Graph— A picture of an equation showing the points of a plane that satisfy the equation.

Operation— A method of combining the members of a set, two at a time, so the result is also a member of the set. Addition, subtraction, multiplication, and division of real numbers are familiar examples of operations.

particularly adept at utilizing algorithms, the creation of new and faster algorithms has become an important field in the study of computer science.

Algorithms can be written to solve many problems. For example, an algorithm can be developed for tying a shoe, making cookies, or determining the area of a circle. In an algorithm for tying a shoe, each step, from obtaining a shoe with a lace to releasing the string after it is tied, is spelled out. The individual steps are written in such a way that no judgment is ever required to successfully carry them out. The length of time required to complete an algorithm is directly dependent on the number of steps involved. The more steps, the longer it takes to complete. Consequently, algorithms are classified as fast or slow depending on the speed at which they allow a task to be completed. Typically, fast algorithms are usable while slow algorithms are unusable.

See also Computer, analog; Computer, digital; Internet search engine.

algorithm A prescribed set of well-defined rules or instructions for the solution of a problem, such as the performance of a calculation, in a finite number of steps. Expressing an algorithm in a formal notation is one of the main parts of a program; much that is said about programs applies to algorithms, and vice versa. An effective algorithm is one that is effectively computable (see effective computability). The study of whether effective algorithms exist to compute particular quantities forms the basis of the theory of algorithms.

Save for the simplest of algorithms it is difficult to prove that an algorithm is correct (see program correctness proof), or even to specify the effect it is intended to achieve. In practice it is usually necessary to be content with algorithm validation. This process certifies, or verifies, that an algorithm will perform the calculation required of it. It involves testing the routine against a variety of instances of the problem and ensuring that it performs satisfactorily for these test cases. If the test set is chosen sufficiently well there can then be confidence in the algorithm.

Algorithm analysis is the study of the performance characteristics of a given algorithm. One branch of this study, average-case analysis, examines the average behavior of the algorithm. Worst-case analysis studies the behavior when all circumstances are as unfavorable as possible. Algorithms can be analyzed in terms of their complexity and efficiency, where algorithm efficiency is characterized by its order.

Algorithm

An algorithm is a set of instructions that indicate a method for accomplishing a task. If followed correctly, an algorithm guarantees successful completion even without the use of any intelligence. The term algorithm is derived from the name al-Khowarizmi, a ninth century Arabian mathematician who is credited with discovering algebra . With the advent of computers, which are particularly adept at utilizing algorithms, the creation of new and faster algorithms has become an important consideration in the study of theoretical computer science.

Algorithms can be written to solve any conceivable problem. For example, an algorithm can be developed for tying a shoe, making cookies, or determining the area of a circle . In an algorithm for tying a shoe, each step, from obtaining a shoe with a lace to releasing the string after it is tied, is spelled out. The individual steps are written in such a way that no judgment is ever required to successfully carry them out. The length of time required to complete an algorithm is directly dependent on the number of steps involved. The more steps, the longer it takes to complete. Consequently, algorithms are classified as fast or slow depending on the speed at which they allow a task to be completed. Typically, fast algorithms are usable while slow algorithms are unusable.

See also Computer, analog; Computer, digital.

al·go·rithm / ˈalgəˌri[voicedth]əm/ • n. a process or set of rules to be followed in calculations or other problem-solving operations, esp. by a computer: a basic algorithm for division.DERIVATIVES: al·go·rith·mic / ˌalgəˈri[voicedth]mik/ adj.al·go·rith·mi·cal·ly / ˌalgəˈri[voicedth]mik(ə)lē/ adv.