Knuth 1.1: What is an algorithm?

Aside from the usual, less-formal definitions of algorithm (such as procedure, process, method, etc), Knuth describes five important features which differentiate an algorithm. These features are paraphrased below:

1. Finiteness. An algorithm must always terminate after a finite number of steps. Similar procedures which differ only in that they do not terminate can be described as computational methods.
2. Definiteness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
3. Input. An algorithm has zero or more inputs: quantities that are given to it initially before the algorithm begins, or dynamically as the algorithm runs.
4. Output. An algorithm has one or more outputs: quantities that have a specified relation to the inputs.
5. Effectiveness. An algorithm is also generally expected to be effective, in the sense that its operations must all be sufficiently basic that they can in principle be done exactly and in a finite length of time by someone using pencil and paper.

Euclid’s algorithm for finding the greatest common divisor is used as an example. It certainly terminates if given the correct input. It is well defined for only using the basic notion of integer division. it has inputs and outputs. Finally, it is effective because integer division is a well-defined and unambiguous operation. However, one interesting point of note is that loose-definitions can drastically change our evaluation of an algorithm. Knuth’s Euclid example works well: if inputs are not specified/restricted to integers, it fails to be effective. It relies on using integer inputs to unambiguously calculate a remainder. He also uses the recipe analogy again. “Add a dash of salt” is ambiguous…we don’t precisely know how or where to add the salt.

Formal Definition

We can formally define a computational method (see above) as a quadruple, (Q, I, Ω, f). Q being the states of computation, I being the input, Ω being the outputs, and f the computational rule (division in the Euclid case). A definition like this does not however enforce the features mentioned above, such as effectiveness. Further restrictions must be employed.