6533b860fe1ef96bd12c3136
RESEARCH PRODUCT
On the power of inductive inference from good examples
Rolf WiehagenRusins FreivaldsEfim Kinbersubject
Teaching dimensionSet (abstract data type)Identification (information)General Computer ScienceInferenceContrast (statistics)Inductive reasoningFinite setAlgorithmPower (physics)MathematicsTheoretical Computer ScienceComputer Science(all)description
Abstract The usual information in inductive inference available for the purposes of identifying an unknown recursive function f is the set of all input/output examples (x,f(x)),n eN. In contrast to this approach we show that it is considerably more powerful to work with finite sets of “good” examples even when these good examples are required to be effectively computable. The influence of the underlying numberings, with respect to which the identification has to be realized, to the capabilities of inference from good examples is also investigated. It turns out that nonstandard numberings can be much more powerful than Godel numberings.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-03-01 | Theoretical Computer Science |