Medieval Arabic Notions of Algorithm: Some Further Raw Evidence

摘要

During YuriFest 2010 the discovery of a proof search algorithm devised in the 1020s by Ibn Slna (Avicenna) was announced. A Gurevich abstract state machine was given in evidence that Ibn Sina really did intend an algorithm; this was needed because Ibn Slna explained the algorithm by a long sequence of exercises, not by a rigorous definition. More recently a radically original logical decision algorithm has come to light in the work of the 12th century Baghdad scholar Abu al-Barakat. Taking these algorithms alongside the already known algorithms of al-KliwarizmT for solving quadratic equations, and of al-Khalil for listing finite sequences of letters, we can see that the medieval Arabic scholars uncovered a range of algorithms of various kinds. But it seems that they never brought these algorithms together under a single notion of 'algorithm'; in fact we know of no writer who drew a comparison between any two of these algorithms. A natural question for historical research is to uncover what kinds of entity the medieval Arabic scholars thought these algorithms were. The present paper assembles some raw material that should be relevant to this question, including a not very successful attempt by al-Farabi to institute a theory of logical procedures.