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 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 or algorism [for Al-Khowarizmi ], a clearly defined procedure for obtaining the solution to a general type of problem, often numerical. Much of ordinary arithmetic as traditionally taught consists of algorithms involving the fundamental operations of addition, subtraction, multiplication, and division. An example of an algorithm is the common procedure for division, e.g., the division of 1,347 by 8, in which the remainders of partial divisions are carried to the next digit or digits; in this case the remainder of 5 in the division of 13 by 8 is placed in front of the 4, and 8 is then divided into 54. The software that instructs modern computers embodies algorithms, often of great sophistication.

algorithm Initially a word with equivalent meaning to formula, but under the influence of computing now regarded as a step-by-step procedure to solve a problem, usually supported by a mathematical proof. In sociology, the term is generally used more loosely than this, to describe the steps which must be followed to construct a new variable from a set of other variables. A good example would be the algorithm used by Erik Olin Wright to arrive at his social class variable, by combining particular combinations of ownership and decision-making responsibilities, said to characterize the various class locations (see his Classes, 1985
).

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.

algorithm A documented series of steps which leads to the transformation of some data. For example, in order to calculate the sum of a series of numbers a possible algorithm would involve repeatedly adding the numbers to be summed to a running total. Computer programs are a manifestation of algorithms which allow them to be executed very quickly.

algorithm (al-gŏ-rith-ĕm) n. a sequential set of instructions used in calculations or problem solving, such as a stepwise series of instructions with branching pathways to be followed to assist a physician in coming to a diagnosis (diagnostic a.) or deciding on a treatment strategy (therapeutic a.).

algorithm Step-by-step set of instructions needed to obtain some result from given starting data. The term is also used in computer science for the method of a computer in following an established series of steps in the solution of a problem.

algorithm •hansom, ransom, Ransome, transom •Wrexham • sensum • Epsom • jetsam •lissom • winsome • gypsum • alyssum •blossom, opossum, possum •flotsam • awesome • balsam • Folsom •noisome • twosome •fulsome • buxom • Hilversum •irksome • Gresham • meerschaum •petersham • nasturtium •atom, Euratom •factum •bantam, phantom •sanctum •desideratum, erratum, post-partum, stratum •substratum • rectum • momentum •septum •datum, petrolatum, pomatum, Tatum, ultimatum •arboretum • dictum • symptom •ad infinitum •bottom, rock-bottom •quantum •autumn, postmortem •factotum, Gotham, scrotum, teetotum, totem •sputum •accustom, custom •diatom • anthem • Bentham • Botham •fathom • rhythm • biorhythm •algorithm • logarithm • sempervivum •ovum • William