Kybernetika 30 no. 1, 23-52, 1994

Refinements of inductive inference by Popperian and reliable machines

John Case, Sanjay Jain and Suzanne Ngo Manguelle


Restricted and unrestricted algorithmic devices which attempt to arrive in the limit at explanatory computer programs for input functions are studied. The input functions may be interpreted as summaries of the behavior of real world phenomena. A classification of criteria of success for such devices is made based on Karl Popper's refutability principle in philosophy of science. Also considered are criteria of success requiring reliability in the sense that the devices should not mislead us by converging to faulty programs. The criteria in the classifications are compared to one another and some interesting tradeoff results are obtained. The techniques of recursive function theory are employed.


68T15, 68Q60, 68T27, 03D20, 68Q05, 68T05