Several well-known inductive inference strategies change the actual hy
pothesis only when they discover that it ''provably misclassifies'' an
example seen so far. This notion is made mathematically precise, and
its general power is characterized. In spite of its strength, it is sh
own that this approach is not of universal power. Consequently, hypoth
eses are considered which ''unprovably misclassify'' examples, and the
properties of this approach are studied. Among others, it turns out t
hat this type is of the same power as monotonic identification. Then i
t is shown that universal power can be achieved only when an unbounded
number of alternations of these dual types of hypotheses is allowed.
Finally, a universal method is presented, enabling an inductive infere
nce strategy to verify the incorrectness of any of its incorrect inter
mediate hypotheses. (C) 1995 Academic Press, Inc.