Abstract Results in recursion-theoretic inductive inference have been criticized as depending on unrealistic self-referential examples. J. M. Bārzdiņš proposed a way of ruling out such examples, and conjectured that one of the earliest results of inductive inference theory would fall if his method were used. In this paper we refute Bārzdiņš' conjecture. We propose a new line of research examining robust separations; these are defined using a strengthening of Bārzdiņš' original idea. The preliminary results of the new line of research are presented, and the most important open problem is stated as a conjecture. Finally, we discuss the extension of this work from function learning to formal language learning.

A new identification criterion, motivated by notions of successively improving approximations in the philosophy of science, is defined. It shown that the class of recursive functions is identifiable under this criterion. This result is extended to apply to somewhat more realistic types of data than usual. This criterion is then modified to consider restrictions on the quality of approximations, and the new criteria are compared to existing criteria.

Results in recursion-theoretic inductive inference have been criticized as depending on unrealistic self-referential examples. J.M. Barzdin (1974) proposed a way of ruling out such examples and conjectured that one of the earliest results of inductive inference theory would fall if his method were used. The author refutes Barzdin's conjecture and proposes a new line of research examining robust separations which are defined using a strengthening of Barzdin's original idea. Preliminary results are presented, and the most important open problem is stated as a conjecture. The extension of this work from function learning to formal language learning is discussed.>

Inductive inference (IIMs) are used to model, among other things, human language learning. Various restrictions on the behavior of IIMs are investigated, the question of interest being whether restricted IIMs can be as powerful as unrestricted IIMs. It is shown that set-driven IIMs are limited in power, whereas order-independent, rearrangement-independent, and prudent IIMs are not. The motivation of formal language learning theory from human language learning is questioned.

Rabin and Blum proved the existence of 0, 1-valued recursive functions which are arbitrarily hard to compute. Their proof was partially constructive in that they effectively gave a program for a function that required computation time exceeding a given bound. However, their proof that the function required the specified time contained a non-constructive element; here we show that that element is essential.

Polynomial-time Turing machines that output instances of a given language are considered, where the instances are required to have a certain length specified by the input. Two types of generating machines are investigated. The first, called a constructor, is deterministic and outputs one string in the language having the specified input length, if such a string exists. A generator is nondeterministic and may output different strings in the language using different computations on the same input; it is required, however, that for any string in the language satisfying the input constraint, there be some computation of the generator on this input that produces the string. Although most P and NP languages examined appear to have such polynomial-time constructors and generators, it is shown that the question of whether all NP languages have such machines is related to other open questions in complexity theory and that even under the assumption that P is not equal to NP, the question cannot be resolved using techniques that relativize. More general and/or flexible types of generators are also considered; namely, generators based on other parameters besides length; generators that are not necessarily capable of outputting all of the instances in the language satisfying the input constraint; and generators where the output instance does not need to satisfy the input constraint exactly. Several results are proved about the existence of such generators for various types of languages.

Three kinds of restrictions on inductive inference machines (IIMs) are considered: postdictive completeness, postdictive consistency, and reliability. It is shown that postdictively consistent IIMs can be effectively replaced with post-dictively complete IIMs that succeed to at least the same degree. Various loosenings of the notions of postdictive completeness and reliability are considered, and a pair of related triangular hierarchies is exhibited; IIMs higher (or to the right) in the hierarchies are less restricted and capable of learning more than IIMs lower or to the left. Various conjectures and older results are obtained as corollaries.