# 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 ontoPage 8 | Top of Article 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

### Source Citation

**Gale Document Number: **
GALE|CX3404200018