A study of inductive inference machines
Mark A. Fulk · 1986
Inductive inference machines (IIMs) model learning and scientific theory formation. We investigate various criteria for the success of IIMs and various restrictions on their behavior. We investigate IIMs that attempt to synthesize (in the limit) a program for a function as they receive data (in the form of input-output pairs) about that function. Some of the restrictions such IIMs might be expected to obey are postdictive completeness, postdictive consistency, and reliability. A postdictively complete IIM always outputs a program that computes all of the data it has seen; a postdictively consistent IIM never outputs a program that produces a wrong answer on any argument from the data it has seen. We show that a postdictively consistent IIM can be effectively replaced with a postdictively complete IIM that succeeds on all of the functions that the original did. A reliable machine never produces a final program on a function unless that program is correct for the function. We investigate weakenings of postdictive completeness and reliability, and demonstrate the existence of a parallel pair of triangular anomaly hierarchies of these weakenings. We answer a question of Wiehagen's Wi82 , to the effect that there are no IIMs that cannot be infinitely improved upon. We also investigate IIMs that attempt to synthesize (again in the limit) a program that enumerates an r.e. set as they receive data consisting of the elements of that set. We answer a question of OS82 ; if any IIM succeeds on a class of r.e. sets, then a prudent one does. We continue investigation of ideas of Freivald and Wiehagen FW79 about inference given additional information; we obtain a descending hierarchy based on finite amounts of faultiness in the additional information. Finally, we propose new criteria for success in inductive inference. We argue that these new criteria are better models of what one might reasonably expect from scientific method; and show that these criteria can, in certain cases, be met on broad classes of recursive functions and r.e. sets. We propose new directions for research in the application of the theory of inductive inference machines to the study of scientific method.