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-mukhtaar 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.

About these ads

8 Comments

Filed under History of Computing, History of Logic, History of Mathematics

8 responses to “Riffing on an Algorithm

  1. Pingback: Linkage « Evolving Thoughts

  2. This raises an interesting question, because I’ve heard the term algorithm used to describe the process of evolution. I assume it’s probably a misuse, since strictly speaking, natural selection is not a solution though I can see how one could envision the two step process of evolution as a ‘recipe’.

    • Although in the computer age the meaning of algorithm has been broadened to mean any procedure for finding a solution there are two elements of the concept that would exclude its use for evolution. Firstly an algorithm is directed towards a specific end and secondly an algorithm only has a finite number of steps. Evolution is non-directed and is, at least potentially, infinite.

      • There is one domain of active study where algorithms are unbounded: chaos theory. It is admittedly a moot point whether a mathematical expression defining a chaotic cycle is an algorithm, but that may be simply an expression of our lack of vision of orders of chaos, ie that what we perceive as chaotic may not actually be so. This returns us to the problems of cutting-edge research, even in mediaeval times: when one is engaged in sufficiently advanced technology, one has to live with the fear of ones own miracles. It is only after the subject becomes consolidated in the mainstream corpus of knowledge that the miracle becomes banal.

      • MPL

        Could you clarify what you mean when you say “an algorithm only has a finite number of steps”?

        While an algorithm as realized by a recursive function / computer program / etc. must have a finite definition, it does not seem like technical usage demands that the algorithm complete in a bounded, or even finite number of steps.

        For instance, a recursively enumerable set may be defined by a partial recursive function that halts only if the element being tested is a member of the set (e.g. testing a Turing machine on an input to see if it halts—it does so in finite time if the machine halts, and doesn’t otherwise). I’m not sure what to call such a partial function but an algorithm.

        In fact, if you allow intermediate output, it’s even possible to take a function that defines a RE set, and write a program that 1) is finite in length 2) never halts 3) eventually outputs any member of the set. This too seems like an algorithm (though perhaps not a very practical one).

  3. Pingback: Monday blast from the past #7: What’s your favourite rhythm? Mine’s am algorithm. | The Renaissance Mathematicus

  4. Pingback: Alchemical confusion. | The Renaissance Mathematicus

  5. Pingback: Planetary Tables and heliocentricity: A Rough Guide | The Renaissance Mathematicus

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s