TOWARDS A MATHEMATICAL-THEORY OF MACHINE DISCOVERY FROM FACTS

This paper intends to give a theoretical foundation of machine discove ry from facts. We point out that the essence of a computational logic of scientific discovery or a logic of machine discovery is the refutab ility of the entire spaces of hypotheses. We discuss this issue in the framework of inductive inference of length-bounded elementary formal systems (EFSs), which are a kind of logic programs over strings of cha racters and correspond to context-sensitive grammars in Chomsky hierar chy. First we present some characterization theorems on inductive infe rence machines that can refute hypothesis spaces. Then we show differe nces between our inductive inference and some other related inferences such as in the criteria of reliable identification, finite identifica tion and identification in the limit. Finally we show that for any n, the class, i.e. hypothesis space, of length-bounded EFSs with at most n axioms is inferable in our sense, that is, the class is refutable by a consistently working inductive inference machine. This means that s ufficiently large hypothesis spaces are identifiable and refutable.