Riffing on an Algorithm

The estimable Thom Levenson author of the excellent Newton and the Counterfeiter, has a piece at The Inverse Square Blog on what he sees as the decline of the Atlantic Monthly; not a subject that would normally cause me to comment here but he includes a justified dismissal of the Atlantic’s abuse of the word algorithm. Now algorithm is a word that truly belongs here so I have decide to expend some thoughts on its meaning, its origins and historical development.

Thom offers up the following working definition for algorithm:

…algorithms involve at a minimum, explicit instructions that can be carried out by a person or a machine which specify operations iterated through a sequence of steps, and produce an unambiguous correct answer (for a certain value of “correct”) within a finite time.

Put simply an algorithm is a recipe for solving problems in the formal sciences, i.e. mathematics, formal logic and computer science. The recipe consists of a finite set of instructions that if carried out in the prescribed order guaranty a solution for the given problem.

Where does the term algorithm come from? It is actually the linguistic corruption of the name of the Uzbek polymath Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmi. Before I continue I should point out that all Islamic scholars of this period are polymaths and al-Khwarizmi’s ethnicity is disputed, as is the ethnicity of almost all Islamic scholars of this period. Now al-Khwarizmi is most famous as the author of Al-Kitāb al-mukhtaṣar fī hīsāb al-ğabr wa’l-muqābala the book that introduced the mathematical discipline algebra into Mediaeval Europe and also gave it its name. Algebra is a corruption of al- ğabr which can be translated as ‘set together’ and thus leads to an ‘Algebraist’ in Spanish being a medical bonesetter. al-Khwarizmi also wrote a book introducing the India decimal place value number system of Brahmagupta into Islamic culture and then in translation into Europe. In the Latin translation al-Khwarizmi becomes Algoritmi, which in turn becomes algorism and algorithm.

The first of these terms, algorism, was the name given to learning how to calculate using the so-called Hindu-Arabic number system at the mediaeval universities and also the name given to the text books used; famous and much used algorisms were written by Sacrobosco and Robert Grosseteste. Algorism was taught as a subsidiary to computos, which was  the science of computing the date of Easter a central part of the mathematics instruction at the mediaeval universities. Later by transference the word algorithm can to designate the methods of calculation used with the new number system, which are in fact algorithms in the modern use of the word.

Although the term itself is a product of the thirteenth century algorithmic mathematics is much older and in fact represents the origins of the subject. In all early mathematical cultures, Babylon, Egypt, India and China, mathematics was presented as a collection of recipes for the solution of specific types of problem. The concept of mathematical proof did not exist and neither did any concept of generalisation. These developments are that which make Greek mathematics in antiquity so important, as it was the Greek mathematicians who first developed the idea of proof and of a systematic presentation of an entire mathematical discipline.

In more recent times the term algorithm has become very central to mathematical logic and computer science as Post, Church, Turing and others all worked on Hilbert’s so-called Entscheidungsproblem. Entscheidung is the German for decision and Hilbert posed the question as to whether every mathematical problem is decidable i.e. is there a finite series of predetermined steps that will lead to a solution of  given problem; in other words an algorithm. The answer produced by the three meta-logicians (meta-mathematicians) named above is no, pushing the humble algorithm into centre stage at the junction of mathematics, logic, computing and philosophy.