Inductive Inference

The paradigm of inductive inference was introduced by Mark Gold in 1967. A common assumption made about Nature is that the observations are consecutive terms of a recursive sequence belonging to a known hypotheses class. Two standard criteria of success are EX (exact) and BC (behaviourally correct), the second one being closer to the problem of prediction. The 1972 paper by Barzdin and Freivald is devoted to prediction and is often credited with the introduction of the Halving Algorithm, a simple version of the Weighted Majority Algorithm.


  • E. Mark Gold. Language identification in the limit. Information and Control 10:447 - 474, 1967.
  • William Gasarch and Carl H. Smith. A survey of inductive inference with an emphasis on queries. Available on the web. 1997
  • J. Barzdin and R. Freivald. On the prediction of general recursive functions. Soviet Mathematics Doklady, 13:1224 - 1228, 1972.