Freivalds defined an acceptable programming system independent
criterion for learning programs for functions in which the final
programs were required to be both correct and “nearly” minimal size,
i.e., within a computable function of being purely minimal size. Kinber
showed that this parsimony requirement on final programs
limits learning power. However, in scientific
inference, parsimony is considered highly desirable. A
lim-computable function is (by definition) one calculable by a
total procedure allowed to change its mind finitely many times about its
output. Investigated is the possibility of assuaging somewhat the
limitation on learning power resulting from requiring parsimonious
final programs by use of criteria which require the final, correct
programs to be “not-so-nearly” minimal size, e.g., to be within a
lim-computable function of actual minimal size. It is
shown that some
parsimony in the final program is thereby retained, yet learning power
strictly
increases.
Considered, then, are lim-computable functions as above but for which
notations for constructive ordinals are used to bound the number of
mind changes allowed regarding the output. This is a variant of an
idea introduced by Freivalds and Smith. For this ordinal notation complexity
bounded version of lim-computability, the power of the resultant
learning criteria form finely graded,
infinitely ramifying, infinite hierarchies intermediate between the
computable and the lim-computable cases. Some of these hierarchies, for the
natural notations determining them, are shown to be optimally tight.