A search algorithm is a computational procedure (an algorithm) for finding a particular object or objects in a larger collection of objects. Typically, these algorithms search for objects with desired properties whose identities are otherwise not yet known. Search algorithms (and search generally) has been an integral part of artificial intelligence and computer science this last half-century, since the first working AI program, designed to play checkers, was written in 1951-2 by Christopher Strachey. At each round, that program evaluated the alternative board positions that resulted from potential next moves, thereby searching for the “best” next move for that round.
The first search algorithm in modern times apparently dates from 1895: a depth-first search algorithm to solve a maze, due to amateur French mathematician Gaston Tarry (1843-1913). Now, in a recent paper by logician Wilfrid Hodges, the date for the first search algorithm has been pushed back much further: to the third decade of the second millenium, the 1020s. Hodges translates and analyzes a logic text of Persian Islamic philosopher and mathematician, Ibn Sina (aka Avicenna, c. 980 – 1037) on methods for finding a proof of a syllogistic claim when some premises of the syllogism are missing. Representation of domain knowledge using formal logic and automated reasoning over these logical representations (ie, logic programming) has become a key way in which intelligence is inserted into modern machines; searching for proofs of claims (“potential theorems”) is how such intelligent machines determine what they know or can deduce. It is nice to think that automated theorem-proving is almost 990 years old.
B. Jack Copeland : What is Artificial Intelligence?
Wilfrid Hodges : Ibn Sina on analysis: 1. Proof search. or: abstract state machines as a tool for history of logic. pp. 354-404, in: A. Blass, N. Dershowitz and W. Reisig (Editors): Fields of Logic and Computation. Lecture Notes in Computer Science, volume 6300. Berlin, Germany: Springer. A version of the paper is available from Hodges’ website, here.
Gaston Tarry : La problem des labyrinths. Nouvelles Annales de Mathématiques, 14: 187-190.