On the inference of approximate programs (Q803121)

An Inductive Inference Machine (IIM) is an algorithmic device that takes as input the graph of a function (an ordered pair at a time) and outputs programs (which should compute that function). A function is said to be identifiable by an IIM M if M converges to a program computing that function. There are several different notions of convergence in the above definition. The authors consider the convergence of M to a single program that agrees with the input function infinitely often \((EX^{\infty})\). They compare that definition with others, already better known, like, e.g., EX (where M is allowed to make finitely many changes), \(EX^ n\) (at most n-changes), BC (where M outputs infinitely many programs and almost all of them compute the input function), etc. It is proved, e.g., that \(EX^{\infty}\) identifies every recursive function, that \(BC- EX^{\infty}\neq \emptyset\), and that \(FEX^{\infty}-(OEX^*\cup EX^{\infty})\neq \emptyset.\) The last part of the paper treats the problems of density classes.