This lengthy paper considers inductive inference, especially by probabilistic machines. An inductive inference machine is an algorithmic device that attempts to infer rules from examples, where a rule is any recursive function f, while an example is a pair (x,f(x)), for some x in the domain of f. Naturally, the inference of functions is an infinite process that occurs in the limit. Among the many criteria for successful inference are the two standards EX and BC (as the paper explains). The author considers probabilistic inductive inference machines with these identification criteria and discovers that in each case a discrete hierarchy of classes of recursive functions exists. A function’s class depends upon its probability of identification--more specifically, which of the intervals (1-2-,1], (1-3-,1-2-], (1-4-,1-3-], . . . . this probability is determined to lie in. Pitt then alternatively characterizes these hierarchies of classes as those functions identified by teams of inductive inference machines operating under the same identification criterion (essentially a parallel model of inference), as well as those functions identified by EX or BC machines (whichever is appropriate) operating by frequency identification.

The paper is extremely thorough, and the author rigorously defines the foundations on which the results depend. Much of this work applies to arbitrary identification criteria (with some natural limitations), not just EX and BC. The paper is also sufficiently self-contained to be suitable as an introduction to inductive inference, especially when read in conjunction with one or two of the references, although the student will need some mathematical maturity and background (in particular, basic concepts from recursive function theory and probability theory). The rigor of the presentation does nothing to impair readability, and the author explains many concepts intuitively as well as formally. The material should interest many researchers, especially those in artificial intelligence, recursive function theory, and computational complexity theory, as the concepts that appear here have obvious parallels in those areas.