Search

This paper reviews the theory of search. The main viewpoint is statistical but considerable space is spent on connections with other fields such as logic and optimisation. Three primitive ideas dominate: consistency, entropy, and Bayes' methods. The theory of screening provides one of the central examples and there is a section on nonsequential random search deriving from the work of Renyi. The game of Bulls and Cows provides a motivating example for both sequential and nonsequential algorithms.