What Is Algorithm?

Simple as the definition of the notion of algorithm is, the concept of what it attempts to convey is a matter of debate and scientific research. In most of textbooks (see, e.g. Review of Discrete Algorithmic Mathematics by S. B. Maurer and A. Ralston) algorithms are required to possess several properties, notably Finiteness and Definiteness. In prose

If the problem is that of computations, being "unambiguous" usually means that a human of average intelligence must be able (if only in principle) follow the instructions with pencil and paper. In theory, a discerning robot must be able to perform the job as well. And this inescapably links the idea of algorithm to programming. Indeed, algorithms are commonly expressed either in a programming language like Pascal or C++, or a pseudocode. Some go an extra mile by inventing a custom programming language, like AL by Maurer and Ralston and the notorious assembly for the hypothetical computer MIX by R. Knuth. This is all for the purpose of making the description of the algorithms as "unambiguous" as possible.

However, quite often, the concept of algorithm is thought to be distinct from that of program. The distinction is similar to that made in mathematics between the Platonic notion of number and a magnitude describing the size of a naturally available set (as in "three cows," say.)

Often, too, a program, unlike an algorithm, is not required to terminate in a finite time, and, indeed, the Halting Problem, that is the problem of existence of an algorithm that could predict whether a given program will terminate (in finite time, of course) for a given input, is a cornerstone of the Computability Theory.

In my view, the finiteness requirement is a red herring. Consider an example of typing out consecutive prime numbers. For any integer, there is an unambiguous (and finite) way to determine whether it is prime or not. We'll do this an integer at a time staring with, say, 2. We may set up a terminating condition (say, check the first million of integers or print out the first million of primes) or not. Compare

It's hard for me to imagine why one of these would be honored with the term algorithm while the other would be denied that honor.

There are several algorithms discussed and illustrated at this site:

1. Algorithm for Computing LCM
2. Calculation of the Digits of pi by the Spigot Algorithm
3. Calculation of the Digits of pi (Faster Version)
4. Cheapest Link & Kruskal's Algorithms
5. Distance Between Strings
6. Egyptian Multiplication
7. Euclid's Algorithm
8. Genetic Algorithm Solves the Toads and Frogs Puzzle
9. Horner's Method
10. Marriage Problem, simulation
11. Mazes
12. Peasant Multiplication
13. Project Scheduling
14. Sorting Algorithms

Geometric construction problems offer additional examples.

The word "algorithm" has an interesting history. Here's a quote from S. Schwartzman's The Words of Mathematics:

(I believe that the name is more often is transcribed as al-Khowarizmi. He was a prolific and an important writer. The title of one of his books, al-jebr w'al-muqabalah, metamorphosed into the current term Algebra. It gives me a great pleasure to mention a fact of which I was unaware until very recently. al-Khowarizmi also wrote a treatise on the Hebrew calendar, Risala fi istikhraj ta'nkh al-yahud "Extraction of the Jewish Era". A calendar is nothing but an algorithmic way of assigning dates.)

References

1. R. Knuth, The Art of Computer Programming, volumes 1-3, boxed set, 2^nd edition, Addison-Wesley, 1998
2. A. Levitin, Introduction to The Design & Analysis of Algorithms, Addison-Wesley, 2003
3. S. B. Mauer, A. Ralston, Discrete Algorithmic Mathematics, A K Peters, 3^rd edition, 2004
4. R. Sedgewick, Algorithms, Adison-Wesley Publishing Co., 1983
5. R. Sedgewick, Algorithms in C++, Adison-Wesley Publishing Co., 1983
6. S. Schwartzman, The Words of Mathematics, MAA, 1994

Copyright © 1996-2009 Alexander Bogomolny