Learning and Consistency
Rolf Wiehagen

Thomas Zeugmann

University of Kaiserslautern

Research Institute of

Department of Computer Science

Fundamental Information Science

P.O. Box 3049

Kyushu University 33

67653 Kaiserslautern

Fukuoka 812

GermanyJapanwiehagen@informatik.uni-kl.de

thomas@rifis.sci.kyushu-u.ac.jp

Abstract
In designing learning algorithms it seems quite reasonable to construct themin such a way that all data the algorithm already has obtained are correctly
and completely reflected in the hypothesis the algorithm outputs on these data.
However, this approach may totally fail. It may lead to the unsolvability of thelearning problem, or it may exclude any efficient solution of it.
Therefore we study several types of consistent learning in recursion-theoretic
inductive inference. We show that these types are not of universal power. We
give “lower bounds” on this power. We characterize these types by some versionsof decidability of consistency with respect to suitable “non-standard” spaces ofhypotheses.
Then we investigate the problem of learning consistently in polynomial time. In
particular, we present a natural learning problem and prove that it can be solvedin polynomial time if and only if the algorithm is allowed to work inconsistently.

1. Introduction
The phenomenon of learning has attracted much attention of researchers in various fields. When dealing with learning computer scientists are mainly interested instudying the question whether or not learning problems may be solved algorithmically.
Nowadays, algorithmic learning theory is a rapidly emerging science, cf. Angluin andSmith (1983, 1987), Osherson, Stob and Weinstein (1986). Nevertheless, despite theenormous progress having been made since the pioneering papers of Solomonoff (1965)
and of Gold (1965, 1967), there are still many problems that deserve special attention.
The global question we shall deal with may be posed as follows: Are all data of equal
importance a learning algorithm is fed?
First we study this question in the setting of inductive inference. Then we ask
whether the insight obtained may be important when one has to solve learning problems that are in a sense closer to potential applications. For that purpose we consider
a domain that has recently attracted attention, namely the learnability of indexedfamilies (cf., e.g., Zeugmann, Lange and Kapur, 1995, and the references therein).
We consider the particular indexed family of all the pattern languages and show thesuperiority of inconsistent learning strategies over consistent ones for this particularfamily. Next, we want to explain all this in some more detail.
One main problem of algorithmic learning theory consists in synthesizing “global
descriptions” for the objects to be learned from examples. Thus, one goal is the following. Let f be any computable function from IN into IN. Given more and more
examples f (0), f (1), ..., f (n), ... a learning strategy is required to produce a sequenceof hypotheses h0 , h1 , ..., hn , ... the limit of which is a correct global description of thefunction f , i.e., a program that computes f . Since at any stage n of this learning process the strategy knows exclusively the examples f (0), f (1), ..., f (n), it seems
reasonable to construct the hypothesis hn in a way such that for any x ≤ n the “hypothesis function” g described by hn is defined and computes the value f (x). Sucha hypothesis is called consistent. In other words, a hypothesis is consistent if andonly if all information obtained so far about the unknown object is completely andcorrectly encoded in this hypothesis. Otherwise, a hypothesis is said to be inconsistent. Consequently, if the hypothesis hn above is inconsistent, then there must be anx ≤ n such that g(x) 6= f (x). Note that there are two possible reasons for g to differ
from f on argument x; namely, g(x) may be not defined, or the value g(x) is definedand does not equal f (x). Hence, if a hypothesis is inconsistent then it is not only
wrong but it is wrong on an argument for which the learning strategy does alreadyknow the correct value. At first glance we are tempted to totally exclude strategies
producing inconsistent hypotheses from our considerations. It might seem that consistent strategies, i.e., strategies that produce always consistent hypotheses, are theonly reasonable learning devices.
Surprisingly enough this is a misleading impression. As it turns out, in a sense
learning seems to be the art of knowing what to overlook. Barzdin (1974a) first announced that there are classes of recursive functions that can be learned in the limit
but only by strategies working inconsistently. This result directly yields the following
questions:(1) Why does it make sense to output inconsistent hypotheses?
(2) What kind of data, if any, the strategy should overlook?
As we shall see below the first question finds its preliminary answer in the fact that,in general, there is no algorithm detecting whether or not a hypothesis is consistent.
Consequently, in general, a strategy has no chance to effectively verify the consistencyof its previous guess with the new data it has been fed. On the other hand, a strategy cannot overcome this drawback by simply searching any consistent hypothesis,
since it has to converge in the limit, too. Therefore, in order to be really successful
in the limit a strategy cannot take care whether all the information it is provided
with is actually correctly reflected by its current hypotheses. Answering the second
question is more complicated. However, an intuitively satisfying answer is provided
by a characterization of identification in the limit in terms of computable numberings (cf. Wiehagen (1978), Theorem 8). This theorem actually states that a class Uof recursive functions can be learned in the limit iff there are a space of hypotheses
containing for each function at least one program, and a computable “discrimination”

function d such that for any two programs i and j the value d(i, j) is an upper boundfor an argument x on which program i behaves differently than program j does. The
key observation used in constructing the strategy that infers any function from U is
the following. Let i be the strategy’s last guess and let f (0), ..., f (n) be the data
now fed to it. If the strategy finds a program j such that for all inputs x ≤ d(i, j)
its output equals f (x), then program i cannot be a correct one for function f . Thenthe strategy changes its mind from i to i + 1. In other words, the strategy uses thedata up to d(i, j) for the purpose to find a proof for the possible incorrectness of its
actual hypothesis i via some global property the space of all hypotheses possesses.
Just for achieving this reasonable purpose the learning strategy may ignore all thedata f (x) where d(i, j) < x ≤ n, thus trading off consistency of the new hypothesis(unachievable, in general, anyway) for an incorrectness proof concerning the former
hypothesis.
Summarizing the above discussion we see that the main reason for the superiority
of inconsistent strategies in the setting of inductive inference of recursive functions iscaused by the undecidability of consistency. As we shall see further, consistent learning
is also sensitive with respect to additional requirements that a learning strategy might
be supposed to fulfil, e.g. the order in which the input data are provided or the domain
on which a strategy is required to behave consistently.
However, it remained open whether this inconsistency phenomenon is of epistemological importance, only, but of almost no practical relevance. Dealing with the latterproblem requires a different approach. It might be well conceivable that consistency
is often decidable if one restricts itself to learning problems that are of interest withrespect to potential applications. Consequently, the superiority of inconsistent strategies in this setting, if any, can only be established in terms of complexity theory. What
we present in the sequel is a partial solution to this problem. As it turned out, there
are natural learning problems having the following property: Though consistency isdecidable in the corresponding domain, these learning problems can be solved by apolynomial-time strategy if and only if the strategy may work inconsistently.
Hence the inconsistency phenomenon does survive also in domains where consistency is decidable. Moreover, the reason for the eventual superiority of inconsistent
strategies is in both settings in some sense the same. In both cases the learning algorithms cannot handle the problem of finding/constructing consistent hypotheses. On
the one hand, this inability has been caused by the provable absence of any algorithm
solving it, while, on the other hand, this problem may be computationally intractable.
As far as we know the result above is the first one formally proving the existence oflearning problems that cannot be solved in polynomial time by any consistent strategy
in a setting where consistency is decidable. Moreover, in our opinion it strongly
recommends to take inconsistent learning strategies seriously into consideration. Thisrequires both, the elaboration of “intelligent” inconsistent techniques as well as finding
criteria with the help of which one can decide whether or not fast consistent strategies
are unavailable. The inconsistency technique we have used just consists in ignoringdata unnecessary for the strategy in order to fulfil its learning task. Of course, thismight not be the only such technique.
The paper is structured as follows. Section 2 presents notation and definitions.
Section 3 deals with the inconsistency phenomenon in the setting of inductive inference

of recursive functions. The problem whether the inconsistency phenomenon is of any
relevance in the world of polynomial time learning is affirmatively exemplified in
Section 4. In Section 5 we discuss the results obtained and present open problems.
All references are given in Section 6. Note that Wiehagen and Zeugmann (1992)
and Wiehagen (1992) dealt already with the inconsistency phenomenon in inductive
inference and in exact learning in polynomial time. Furthermore, part of the present
paper has been published in Wiehagen and Zeugmann (1994).

2. Preliminaries
Unspecified notations follow Rogers (1967). IN = {0, 1, 2, ...} denotes the set of
all natural numbers. The set of all finite sequences of natural numbers is denotedby IN∗ . The classes of all partial recursive and recursive functions of one, and twoarguments over IN are denoted by P, P 2 , R, and R2 , respectively. R0,1 denotes theset of all 0 − 1 valued recursive functions. Sometimes it will be suitable to identify arecursive function with the sequence of its values, e.g., let α = (a0 , ..., ak ) ∈ IN∗ , j ∈IN, and p ∈ R0,1 ; then we write αjp to denote the function f for which f (x) = ax , if
x ≤ k, f (k + 1) = j, and f (x) = p(x − k − 2), if x ≥ k + 2. Furthermore, let g ∈ P
and α ∈ IN∗ ; we write α < g iff α is a prefix of the sequence of values associated withg, i.e., for any x ≤ k, g(x) is defined and g(x) = ax . If U ⊆ R, then we denote by [U ]the set of all prefixes of functions from U .
Any function ψ ∈ P 2 is called a numbering. Moreover, let ψ ∈ P 2 , then we write ψiinstead of λxψ(i, x) and set Pψ = {ψi i ∈ IN} as well as Rψ = Pψ ∩ R. Consequently,
if f ∈ Pψ , then there is a number i such that f = ψi . If f ∈ P and i ∈ IN are suchthat ψi = f , then i is called a ψ–program for f . A numbering ϕ ∈ P 2 is called a Gödelnumbering (cf. Rogers (1967)) iff Pϕ = P , and for any numbering ψ ∈ P 2 , there is ac ∈ R such that ψi = ϕc(i) for all i ∈ IN. Göd denotes the set of all Gödel numberings.
Using a fixed encoding h...i of IN∗ onto IN we write f n instead of h(f (0), ..., f (n))i,for any n ∈ IN, f ∈ R. Furthermore, the set of all permutations of IN is denotedby Π(IN). Any element X ∈ Π(IN) can be represented by a unique sequence (xn )n∈IN
that contains each natural number precisely ones. Let X ∈ Π(IN), f ∈ P and n ∈ IN.
Then we write f X,n instead of h(x0 , f (x0 ), ..., xn , f (xn ))i provided f (xk ) is defined for
all k ≤ n. Finally, a sequence (jn )j∈IN of natural numbers is said to converge to thenumber j iff all but finitely many numbers of it are equal to j. A sequence (jn )j∈INof natural numbers is said to finitely converge to the number j iff it converges in thelimit to j and for all n ∈ IN, jn = jn+1 implies jk = j for all k ≥ n. Now we are readyto define some concepts of learning.
Definition 1. (Gold, 1965) Let U ⊆ R and let ψ ∈ P 2 . The class U is said tobe learnable in the limit with respect to ψ iff there is a strategy S ∈ P such that foreach function f ∈ U ,(1) for all n ∈ IN, S(f n ) is defined,(2) there is a j ∈ IN such that ψj = f and the sequence (S(f n ))n∈IN converges to j.
If U is learnable in the limit with respect to ψ by a strategy S, we write U ∈ LIMψ (S).
S
Let LIMψ = {U U is learnable in the limit w.r.t. ψ}, and let LIM = ψ∈P 2 LIMψ .

Some remarks are mandatory here. Let us start with the semantics of the hypotheses produced by a strategy S. If S is defined on input f n , then we always interpretthe number S(f n ) as a ψ–number. This convention is adopted to all the definitions
below. Furthermore, note that LIMϕ = LIM for any Gödel numbering ϕ. In theabove definition LIM stands for “limit.” Moreover, in accordance with the definitionof convergence, only finitely many data of the graph of a function f were available
to the strategy S up to the unknown point of convergence. Therefore, some formof learning must have taken place. Thus, the use of the term “learn” in the above
definition is indeed justified. As we have mentioned, in general it is not decidable
whether or not a strategy has already converged when successively fed some graphof a function. With the next definition we consider a special case where it has to be
decidable whether or not a strategy has already learned its input function.
Definition 2. (Gold, 1967; Trakhtenbrot and Barzdin, 1970) Let U ⊆ R
and let ψ ∈ P 2 . The class U is said to be finitely learnable with respect to ψ iff there
is a strategy S ∈ P such that for any function f ∈ U ,(1) for all n ∈ IN, S(f n ) is defined,(2) there is a j ∈ IN such that ψj = f and the sequence (S(f n ))n∈IN finitely converges
to j.
If U is finitely learnable with respect to ψ by a strategy S, we write U ∈ F INψ (S).
S
Let F INψ = {U U is finitely learnable w.r.t. ψ}, and let F IN = ψ∈P 2 F INψ .
Next we formally define different models of consistent learning.
Definition 3. (Barzdin, 1974a) Let U ⊆ R and let ψ ∈ P 2 . The class U iscalled consistently learnable in the limit with respect to ψ iff there is a strategy S ∈ Psuch that(1) U ∈ LIMψ (S),(2) ψS(f n ) (x) = f (x) for all f ∈ U , n ∈ IN and x ≤ n.
CON Sψ (S), CON Sψ and CON S are defined analogously as above.
Intuitively, a consistent strategy does correctly reflect all the data it has alreadyseen. If a strategy does not always work consistently, we call it inconsistent.
Next, we add a requirement to the definition of the learning type CON Sψ that isoften implicitly assumed in applications, namely, that the strategy is defined on every
input, cf. Michalski et al. (1984, 1986).
Definition 4. (Jantke and Beick, 1981) Let U ⊆ R and let ψ ∈ P 2 . The class
U is called R–consistently learnable in the limit with respect to ψ iff there is a strategy
S ∈ R such that U ∈ CON Sψ (S).
R−CON Sψ (S), R−CON Sψ and R−CON S are defined analogously as above.
The latter definition has a peculiarity that should be mentioned. Although thestrategy is required to be recursive, consistency is only demanded for inputs that
correspond to some function f from the class to be learned. With the next definition
we model the scenario in which consistency is required on all inputs. In order todistinguish the resulting learning type from the latter defined one, we use the prefix
T . Informally, T points to total consistency.
Definition 5. (Wiehagen and Liepe, 1976) Let U ⊆ R and let ψ ∈ P 2 . The
class U is called T –consistently learnable in the limit with respect to ψ iff there is a
strategy S ∈ R such that
(1) U ∈ CON Sψ (S),(2) ψS(f n ) (x) = f (x) for all f ∈ R, n ∈ IN and x ≤ n.
T −CON Sψ (S), T −CON Sψ and T −CON S are defined in the same way as above.
Finally, looking at potential applications it is often highly desirable to make noassumptions concerning the order in which input data should be presented. Therefore,
we sharpen Definitions 3 through 5 by additionally demanding a strategy to behave
consistently independently of the order of the input.
Definition 6. (Blum and Blum, 1975) Let U ⊆ R and let ψ ∈ P 2 . U ∈T −CON Sψarb iff there is a strategy S ∈ R such that(1) for all f ∈ U and every X ∈ Π(IN), there is a j ∈ IN such that ψj = f , and(S(f X,n ))n∈IN converges to j,(2) ψS(f X,n ) (xm ) = f (xm ) for every permutation X ∈ Π(IN), f ∈ R, n ∈ IN, andm ≤ n.
T −CON Sψarb (S) as well as T −CON S arb are defined in analogy to the above.
Furthermore, appropriately incorporating the requirement to learn from arbitrary
input directly yields the learning types LIM arb , F IN arb , CON S arb , and R−CON S arb .
Therefore, the formal definition of these learning models is omitted here. Note that
LIM = LIM arb as well as F IN = F IN arb , cf. Jantke and Beick (1981). Moreover, for
all learning types LT ∈ {F IN, F IN arb , T −CON S, T −CON S arb , R−CON S, R−
CON S arb , CON S, CON S arb } we have LTϕ = LT for every Gödel numbering ϕ. In
the following section we aim to compare the learning power of the different modelsof consistent learning to one another as well as to the other models of learning that
we have defined. Note that in the following ⊆ denotes subset and ⊂ denotes proper
subset. Finally, incomparability of sets is denoted by #.

3. The Inconsistency Phenomenon in Inductive
Inference
The main goal of this section is a thorough study of the learning power of thedifferent models of consistent learning. Our first subsection deals with the learning
type CON S and compares it to learning in the limit.

3.1. The General Inconsistency Phenomenon
The inconsistency phenomenon has been discovered independently by Barzdin(1974a) and the Blums (1975). They observed that there are classes of recursive

functions that are inferable in the limit but which cannot be learned by any consistent strategy. Since both papers do not contain a proof of this assertion, we present
here a proof from Wiehagen (1976) actually showing a somewhat stronger result thanthe one formulated in the next theorem. We shall discuss this issue below.
Theorem 1. (Barzdin, 1974a)

CON S ⊂ LIM

Proof. Let U = {f ∈ R f = αjp, α ∈ IN∗ , j ≥ 2, p ∈ R0,1 , ϕj = f }, whereϕ ∈ Göd. Obviously, U ∈ LIM (S), where S(f n ) is equal to the last value f (x) ≥ 2
from (f (0), ..., f (n)) and 0, if no such value exists. For the purpose to prove thatU∈
/ CON S we need the following claim.
Claim. For every α ∈ IN∗ , there is an f ∈ U such that α < f .
Indeed, by an implicit use of the Recursion Theorem, cf. Rogers (1967), it is easy
to see that for every α ∈ IN∗ and every p ∈ R0,1 , there is a j ≥ 2 such that ϕj = αjp.
Now, suppose that there is a strategy S ∈ P such that U ∈ CON Sϕ (S). By theclaim, we get S ∈ R and for every α ∈ IN∗ , α < ϕS(α) . Thus, on every α ∈ IN∗ , S
always produces a consistent guess. Then, again by an implicit use of the Recursion
Theorem, let j ≥ 2 be any ϕ–number of the function f defined as follows: f (0) = j,
and for any n ∈ IN,(

f (n + 1) =

0, if
1, if

S(f n 0) 6= S(f n )S(f n 0) = S(f n ) and S(f n 1) 6= S(f n ).

In accordance with the claim and the assumption that S works consistently one
straightforwardly verifies that S(f n 0) 6= S(f n ) or S(f n 1) 6= S(f n ) for any n ∈ IN.
Therefore the function f is everywhere defined and we have f ∈ U . On the other
hand, the strategy S changes its mind infinitely often when successively fed f , acontradiction to U ∈ CON Sϕ (S).
q.e.d.
Note that the class from the proof of Theorem 1 is even iteratively learnable in
the limit. We call a class U of recursive functions iteratively learnable iff there is a
strategy that learns any f ∈ U as follows: In step n the strategy exclusively gets its
previous guess produced in step n − 1 as well as the new value f (n). By IT we denotethe collection of all classes U which can be learned iteratively. In Wiehagen (1976)
CON S ⊂ IT ⊂ LIM has been proved. Recent papers give new evidence for the
power of iterative learning (cf., e.g., Porat and Feldman (1988), Lange and Wiehagen(1991), Lange and Zeugmann (1992)).
A closer look to the proof above shows that, in general, a strategy attempting tolearn functions consistently has to overcome two difficulties. First, it should avoid tochange too often its current guess that is eventually no longer consistent, to a definitely consistent hypothesis, since this behavior may force the strategy to diverge.
Second, trusting that its current guess is consistent may eventually lead to an actually inconsistent hypothesis, since the strategy cannot effectively prove consistency.
Indeed, it turns out that a class U is consistently learnable iff there is a suitable spaceof hypotheses ψ such that the consistency problem restricted to U and ψ is effectively
decidable. More precisely, let U ⊆ R and let ψ be any numbering. We say that
U –consistency is decidable with respect to ψ iff there is a predicate cons ∈ P 2 suchthat for every α ∈ [U ] and all i ∈ IN, cons(α, i) is defined, and cons(α, i) = 1 if andonly if α < ψi .
Theorem 2. U ∈ CON S iff there is a numbering ψ ∈ P 2 such that
(1) U ⊆ Pψ ,(2) U –consistency with respect to ψ is decidable.
Theorem 2 is a consequence of Theorem 9 from Wiehagen (1978). Note that for
an arbitrary Gödel numbering, U -consistency is undecidable for any non-empty class
U ⊆ R.
Next we provide deeper insight to the problem whether or not consistent learningis sensitive with respect to the domain of the allowed strategies.

3.2. Consistent Learning in Dependence on the Domain of
the Strategies
As already mentioned, in machine learning it is often assumed that learning algorithms are defined on all inputs. On the one hand, this requirement is partiallyjustified by a result of Gold (1967). He proved that learning in the limit is insensitive
with respect to the requirement to learn exclusively with recursive strategies, i.e., if
U ∈ LIM (S), then there is a strategy Ŝ ∈ R such that U ∈ LIM (Ŝ). One theother hand, consistency is a common requirement in machine learning. Therefore, it
is natural to ask whether or not the power of consistent learning algorithms further
decreases if one restricts itself to recursive strategies. The answer to this question isprovided by our next theorem.
Theorem 3. T −CON S ⊂ R−CON S ⊂ CON S.
Proof. By definition, T − CON S ⊆ R − CON S ⊆ CON S. In order to show
R − CON S \ T − CON S 6= ∅ let U = {f f ∈ R, ϕf (0) = f } where ϕ ∈ Göd.
Obviously, U ∈ R−CON Sϕ (S) by the strategy S(f n ) = f (0) for all n ∈ N .
Now assume that U ∈ T −CON Sϕ (S). Hence S ∈ R and ϕS(f n ) (x) = f (x) for any
f ∈ R, n ∈ IN and x ≤ n. By an implicit use of the Recursion Theorem, let f = ϕibe the following function.
f (0) = i,(f (n + 1) =0, if S(f n 0) 6= S(f n )1, if S(f n 0) = S(f n ) and S(f n 1) 6= S(f n ).

Clearly, f ∈ U (note that one of the two cases in the definition of f must happen
for all n ≥ 1). On the other hand, S(f n ) 6= S(f n+1 ) for all n ∈ IN, contradicting
U ∈ T−CON Sϕ (S). Hence U 6∈ T−CON S. This completes the proof of T−CON S ⊂R−CON S.
In order to prove CON S \ R − CON S 6= ∅ we use a class similar to the classabove, namely U = {f f ∈ R, either ϕf (0) = f or ϕf (1) = f }. First we show thatU ∈ CON S. The wanted strategy is defined as follows. Let f ∈ R and n ∈ IN.
S(f n ) = “Compute in parallel ϕf (0) (x) and ϕf (1) (x) for all x ≤ n until (A) or (B)happens.

(A) ϕf (0) (x) = f (x) for all x ≤ n.
(B) ϕf (1) (x) = f (x) for all x ≤ n.
If (A) happens first, then output f (0). If (B) happens first, then output f (1).
If neither (A) nor (B) happens, then S(f n ) is not defined.”
By the definition of U , it is obvious that S(f n ) is defined for all f ∈ U and alln ∈ IN. Moreover, S is clearly consistent. Hence, it suffices to prove that (S(f n ))n∈IN
converges for all f ∈ U . But this is also an immediate consequence of the definitionof U , since either ϕf (0) 6= f or ϕf (1) 6= f . Hence S cannot oscillate infinitely often
between f (0) and f (1). Consequently, U ∈ CON Sϕ (S).
Next we show that U ∈/ R−CON S. Suppose there is a strategy S ∈ R such thatU ∈ R−CON Sϕ (S). Applying Smullyan’s Recursion Theorem, cf. Smullyan (1961),
we construct a function f ∈ U such that either S(f n ) 6= S(f n+1 ) for all n ∈ IN or
ϕS(f x ) (y) 6= f (y) for some x, y ∈ IN with y ≤ x. Since both cases yield a contradiction
to the definition of R − CON S, we are done. The wanted function f is defined asfollows. Let h and s be two recursive functions such that for all i, j ∈ IN, ϕh(i,j) (0) =ϕs(i,j) (0) = i and ϕh(i,j) (1) = ϕs(i,j) (1) = j. For any i, j ∈ IN, x ≥ 2 we proceedinductively.
Suspend the definition of ϕs(i,j) . Try to define ϕh(i,j) for more and more arguments
via the following procedure.
(T) Test whether or not (A) or (B) happens (this can be effectively checked, since
S ∈ R):(A) S(ϕxh(i,j) 0) 6= S(ϕxh(i,j) ),(B) S(ϕxh(i,j) 1) 6= S(ϕxh(i,j) ).
If (A) happens, then let ϕh(i,j) (x + 1) = 0, let x := x + 1, and goto (T).
In case (B) happens, set ϕh(i,j) (x + 1) = 1, let x := x + 1, and goto (T).
If neither (A) nor (B) happens, then define ϕh(i,j) (x0 ) = 0 for all x0 > x, andgoto (∗).
(∗) Set ϕs(i,j) (n) = ϕh(i,j) (n) for all n ≤ x, and ϕs(i,j) (x0 ) = 1 for all x0 > x.
By Smullyan’s Recursion Theorem, there are numbers i and j such that ϕi = ϕh(i,j)
and ϕj = ϕs(i,j) . Now we distinguish the following cases.
Case 1. The loop in (T) is never left.
Then we directly obtain that ϕi ∈ U , since ϕj = ij, and hence a finite function.
Moreover, in accordance with the definition of the loop (T), on input ϕni the strategy
S changes its mind for all n > 0.
Case 2. The loop in (T) is left.
) =Then there exist an x such that S(ϕxh(i,j) 0) = S(ϕxh(i,j) 1). Hence S(ϕx+1ix+1S(ϕj ), since ϕh(i,j) = ϕi , ϕs(i,j) = ϕj , ϕi (n) = ϕj (n) for all n ≤ x by (∗), as well as
ϕi (x+1) = 0 and ϕj (x+1) = 1. Furthermore, ϕi , ϕj ∈ R. Since ϕi (x+1) 6= ϕj (x+1),

we get ϕi 6= ϕj . On the other hand, ϕi (0) = i and ϕj (1) = j. Consequently, both functions ϕi and ϕj belong to U . But S(ϕx+1) = S(ϕx+1) and ϕi (x + 1) 6= ϕj (x + 1), henceijx+1
S does not work consistently on input ϕx+1orϕ
. This contradiction completesijthe proof.
q.e.d.
Note that even T − CON S, the most stringent type of consistent identificationconsidered above, is of remarkable power. Therefore, let NUM = {U there is ψ ∈ R2
such that U ⊆ Pψ } denote the set of all recursively enumerable classes of recursivefunctions. Then in Wiehagen and Liepe (1976) the following result was proved.
Theorem 4. NUM ⊂ T −CON S
Proof. Every class U ∈ NUM can be learned T-consistently by a slightly modified
version of Gold’s identification-by-enumeration strategy.
A class witnessing T −CON S \ NUM 6= ∅ can be defined as follows. Let ϕ ∈ Göd.
Let Φ be any complexity measure associated with ϕ, cf. Blum (1967). Then {Φi i ∈IN, ϕi ∈ R} ∈ T −CON S \ NUM . We omit the details.
q.e.d.
The next result provides a more subtle insight into the different power of T−CON S
and R−CON S.
Theorem 5.
(1) F IN # T −CON S(2) F IN ⊂ R−CON S
Proof. (1) T − CON S \ F IN 6= ∅ is proved in Wiehagen and Liepe (1976). Notethat the class {Φi i ∈ IN, ϕi ∈ R} where Φ is a complexity measure associated withϕ ∈ Göd in the sense of Blum (1967) also witnesses T −CON S \ F IN 6= ∅.
Let now U = {f f ∈ R, ϕf (0) = f }. Obviously, U ∈ F IN . On the other hand,U ∈/ T −CON S, cf. proof of Theorem 3. Hence T −CON S \ F IN 6= ∅. This proves(1).
Next, we prove Assertion (2). Since T−CON S ⊂ R−CON S, R−CON S \F IN 6= ∅is an immediate consequence of (1). The proof of F IN ⊆ R−CON S mainly relieson the decidability of convergence of any finite learning algorithm. Let U ∈ F IN ,and let S be any strategy witnessing U ∈ F INϕ (S). Furthermore, let s ∈ R be any
function such that ϕs(α) = α0∞ for all α ∈ IN∗ . The wanted strategy Ŝ is defined asfollows. Let f ∈ R and n ∈ IN. ThenŜ(f n ) = “In parallel, try to compute S(f 0 ), ..., S(f n ) for precisely n steps. Let k ≥ 1
be the least number such that all values S(f 0 ), ..., S(f k ) turn out to be defined,
and S(f k−1 ) = S(f k ).
In case this k is found, output S(f k ). Otherwise, output s(f n ).”It remains to show that U ∈ R−CON S(Ŝ). Obviously, Ŝ ∈ R. Now, let f ∈ U .
We have to show that Ŝ consistently learns f .
Claim 1. Ŝ learns f .
Since f ∈ U , the strategy S is defined for all inputs f n , n ∈ IN. Moreover, since
S finitely learns f , the sequence (S(f n ))n∈IN finitely converges to a ϕ–program of f .

Hence, Ŝ eventually has to find the least k such that S(f k−1 ) = S(f k ), and all values
S(f 0 ), ..., S(f k ) are defined. By the definition of F IN , ϕS(f k ) = f . Hence, Ŝ learns f .
Claim 2. For all f ∈ U and n ∈ IN, Ŝ(f n ) is a consistent hypothesis.
Clearly, as long as Ŝ outputs s(f n ), it is consistent. Suppose, Ŝ outputs S(f k ) for
the first time. Then it has verified that S(f k−1 ) = S(f k ). Since f ∈ U , and U ∈F INϕ (S), this directly implies ϕS(f k ) = f . Therefore, Ŝ again outputs a consistenthypothesis. Since this hypothesis is repeated in any subsequent learning step, theclaim is proved.
q.e.d.
The next result points out another difference between the types CON S, R−CON S,
on the one hand, and T −CON S, on the other hand.
Theorem 6.
(1) CON S and R−CON S are not closed under finite union.
(2) T −CON S is closed under recursively enumerable union.
Proof. (1) is a direct consequence of a more general result of Barzdin (1974b). Let
U = {f f ∈ R, ϕf (0) = f } and let V = {α0∞ α ∈ IN∗ }. It is easy to see that
U, V ∈ R−CON S, and hence U, V ∈ CON S. On the other hand, U ∪ V ∈/ LIM asshown in Barzdin (1974b).
In order to prove (2), we restate this assertion more formally. Let (Si )i∈IN be arecursive enumeration of T –consistent strategies. Then there exists a strategy S such
S
that T −CON S(S) = i∈IN T −CON S(Si ).
Without loss of generality, we may assume that all the strategies Si output as
hypotheses programs in some fixed Gödel numbering ϕ. Note that the following proof
mainly uses a proof technique of Minicozzi (1976). Let f ∈ R. Then two cases are
possible. Either there is a strategy Si that learns f or all strategies fail to learn it.
However, in the latter case each of the strategies Si has to change its mind infinitely
often. On the other hand, if f is learned by some Si then at least one strategy
stabilizes its output. The wanted strategy S searches for an enumerated machine thatmight learn f as follows.
The strategy S dovetails the computation of more and more outputs of the enumerated strategies. For each strategy Si that is already included in its dovetailed
computations, it counts the number of equal outputs. This number is called weight.
As long as a strategy repeats its actual guess on the next input, the weight increments.
If a strategy performs a mind change, its weight reduces to zero. After having readthe initial segment f k of the function f the strategy S favors from the first k + 1
strategies S0 , ..., Sk that one which actually has the greatest weight. In case there are
two strategies Si and Sj taking the greatest weight the strategy S chooses that one
having the smallest index.
We formally define S as follows. Let f ∈ R, and k ∈ IN.
S(f k ) = “Compute in parallel
S0 (f 0 ), ..., S0 (f k ),

S1 (f 0 ), ..., S1 (f k ),–––Sk (f 0 ), ..., Sk (f k ),and assign to each strategy Si , i ≤ k, its weight, i.e., the greatest number m ≤k − i satisfying the condition that Si (f k−i−m ) = Si (f k−i−m+1 ) = ... = Si (f k−i ).
Note that we calculate the weights in a triangular fashion. This is necessary inorder to achieve convergence of S. Choose w(k) to be the smallest i ≤ k suchthat the strategy Si has the greatest weight.
In case all considered machines have weight zero, output a ϕ–program of f (0) ·· · f (k)0∞ .
If w(k) = w(k − 1), then output Sw(k) (f k ). Otherwise, output a ϕ–program off (0) · · · f (k)0∞ that is different from S(f k−1 ).”S

It remains to show that T−CON Sϕ (S) = i∈IN T−CON Sϕ (Si ). Obviously, S works
consistently on any initial segment it is fed, since all of the strategies Si , i ∈ IN, do
so. Now, let f ∈ R and suppose that f is learned by some strategy Si . Consequently,
there exists numbers j, n0 such that Si (f n ) = j for all n ≥ n0 , and ϕj = f . Hence,
for any strategy that learns f its weight increases after some point in each step of
S’s computation. Therefore, for almost all k the strategy S must favor exactly one of
the strategies Si that learns f and, after some point, S outputs always Si (f k ). Notethat the computation of weights in a triangular fashion really ensures the desired
convergence, since any new strategy included in S’s computation initially gets weightzero.
On the other hand, if none of the strategies Si , i ∈ IN, learns f , then each strategy
Si has to perform infinitely many mind changes. This is ensured by our assumptionthat each Si is T –consistent. Hence, the case w(k) 6= w(k − 1) occurs infinitely often.
But each occurrence of this case forces S to perform a mind change. Consequently, S
cannot converge.
q.e.d.
We finish this subsection with characterizations of T−CON S and R−CON S which
are similar to that of CON S presented in Theorem 2. Therefore let ψ ∈ P 2 be any
numbering. Then we say that consistency with respect to ψ is decidable iff there is apredicate cons ∈ R2 such that for every α ∈ IN* and all i ∈ IN, cons(α, i) = 1 if andonly if α < ψi .
Theorem 7. U ∈ T −CON S iff there is a numbering ψ ∈ P 2 such that
(1) U ⊆ Pψ ,(2) consistency with respect to ψ is decidable.
Proof. Necessity. Let U ∈ T −CON Sϕ (S) where ϕ ∈ P 2 is any numbering and S
is a T –consistent strategy. Let M = {(z, n) z, n ∈ IN, ϕz (x) is defined for any x ≤n, S(ϕnz ) = z} be recursively enumerated by a function e. Then define a numbering
ψ as follows. Let i, x ∈ IN, e(i) = (z, n).

if x ≤ n
ϕz (x),
if x > n and, for any y ∈ IN such that n < y ≤ x,
ψi (x) =ϕz (y) is defined and S(ϕyz ) = z
undefined, otherwise.
ϕz (x),
In order to show (1) let f ∈ U and n, z ∈ IN be such that for any m ≥ n, S(f m ) = z.
Clearly, ϕz = f . Furthermore, (z, n) ∈ M . Let i ∈ IN be such that e(i) = (z, n).
Then, by definition of ψ, ψi = ϕz = f . Hence U ⊆ Pψ .
In order to prove (2) we define cons ∈ R2 such that for any α ∈ IN∗ , i ∈IN, cons(α, i) = 1 iff α < ψi . Let α = (α0 , . . . , αx ) ∈ IN∗ and i ∈ IN. Let e(i) = (z, n).
Then define
if x ≤ n and, for any y ≤ x, αy = ψi (y)1, if x > n, αy = ψi (y) for any y ≤ n, and,cons(α, i) =for any y ∈ IN such that n < y ≤ x, S(α0 , . . . , αy ) = z0, otherwise.

1,





It is not hard to see that cons ∈ R2 and, for every α ∈ IN∗ , i ∈ IN, we havecons(α, i) = 1 iff α < ψi .
Sufficiency. Let ψ ∈ P 2 be any numbering. Let cons ∈ R2 be such that for allα ∈ IN∗ , i ∈ IN, cons(α, i) = 1 iff α < ψi . Let U ⊆ Pψ . In order to consistently learn
any function f ∈ U it suffices to define S(f n ) = min{i cons(f n , i)}. However, S is
undefined if, for f ∈/ U, n ∈ IN, there is no i ∈ IN such that f n < ψi . The following
more careful definition of S will circumvent this difficulty. Let ϕ ∈ Göd. Let aux ∈ R
be such that for any α ∈ IN∗ , ϕaux(α) = α0∞ . Finally, let c ∈ R be such that for alli ∈ IN, ψi = ϕc(i) . Then, for any f ∈ R, n ∈ IN, define a strategy S as follows.
(nS(f ) =

c(j),if I = {i i ≤ n, cons (f n , i) = 1} =6 ∅ and j = min Inaux(f ), I = ∅.

Clearly, S ∈ R and S outputs only consistent hypotheses. Now let f ∈ U . Then,obviously, (S(f n ))n∈IN converges to c(min{i ψi = f }). Hence, S witnesses U ∈T −CON Sϕ .
q.e.d.
Finally, let U ⊆ R and ψ ∈ P 2 be any numbering. Then we say that U –consistency
with respect to ψ is R–decidable iff there is a predicate cons ∈ R2 such that for everyα ∈ [U ] and all i ∈ IN, cons(α, i) = 1 if and only if α < ψi .
Theorem 8. U ∈ R−CON S iff there is a numbering ψ ∈ P 2 such that
(1) U ⊆ Pψ ,(2) U –consistency with respect to ψ is R–decidable.
The proof of Theorem 8 is similar to that of Theorem 7.
The characterizations of T − CON S, R − CON S and CON S give rise to pointout some relationship between the problem of deciding consistency and the halting

problem. As it follows from Theorem 3 and Theorem 4, for any of the learning types
LT ∈ {T −CON S, R−CON S, CON S}, we have NUM ⊂ LT . On the other hand,as it was shown in Wiehagen and Zeugmann (1994), for any class U ⊆ R and any
numbering ψ ∈ P 2 , if U ∈/ NUM and U ⊆ Pψ , then the halting problem with respectto ψ is undecidable, i.e., there is no h ∈ R2 such that for any i, x ∈ IN, h(i, x) = 1 iffψi (x) is defined.
Consequently, for any U ∈ LT \ NUM and any numbering ψ ∈ P 2 from thecorresponding theorem above characterizing LT , the halting problem with respect toψ is undecidable. On the other hand, the corresponding version of consistency withrespect to ψ is decidable. Hence this version of consistency cannot be decided byfirstly deciding the halting problem and secondly, if possible, computing the desired
values of the function under consideration in order to compare these values with thegiven ones. More formally, in general, cons(f n , i) cannot be evaluated by deciding
whether or not ψi (x) is defined for all x ≤ n and, if it is, then computing ψin andcomparing it with f n .
Informally, though consistency is decidable in the “characteristic” numberings ofTheorems 2, 7, 8 it is not decidable in a “straightforward way.”

3.3. Consistent Learning on Arbitrary Input Order
In applications it is often highly desirable to make no assumption concerning theorder in which input data should be presented. Therefore, we now state a characterization of the type T −CON S arb due to Blum and Blum (1975). This characterization
easily yields a “lower bound” on the power of T −CON S arb .
Definition 7. A numbering ψ ∈ P 2 is said to be measurable iff the predicate“ψi (x) = y” is uniformly recursive in i, x, y.
Theorem 9. (Blum and Blum, 1975)
U ∈ T −CON S arb iff there is a measurable numbering ψ ∈ P 2 such that U ⊆ Pψ .
Note that the measurability of ψ allows deciding consistency with respect to ψ ina “straightforward way.”
Corollary 10. NUM ⊂ T −CON S arb
Proof. NUM ⊆ T−CON S arb can easily be proved by a slight modification of Gold’s
identification by enumeration.
For proving the proper inclusion, let ϕ ∈ Göd and Φ ∈ P 2 be a complexity measureassociated with ϕ, cf. Blum (1967). Let U = {Φi i ∈ IN, ϕi ∈ R}. Then U 6∈ NUM ,since otherwise R ∈ NUM could be proved, a contradiction. On the other hand,U ∈ T −CON S arb via Theorem 9, since Φ ∈ P 2 is a measurable numbering.
q.e.d.
As far as we now, it is still an open problem whether T − CON S arb is a proper
subset of T −CON S. But, of course, any solution to this problem will not influence
the “lower bound” on the power of T −CON S arb by Corollary 10.
The reader is encouraged to consult Jantke and Beick (1981), Zeugmann (1983)
and Fulk (1989) for further investigation concerning consistent identification.

4. Exact Learning in Polynomial Time and Inconsistency
The results presented in the previous section may lead to the impression that theinconsistency phenomenon may be far beyond any practical relevance, since it has
been established in a setting where the consistency problem is undecidable in general.
Therefore now we ask whether the inconsistency phenomenon does survive in settings
where consistency is decidable. Moreover, we additionally restrict ourselves to deal
exclusively with learning strategies that are polynomial time computable. Then, ofcourse, the superiority of inconsistent strategies, if any, has to be established in termsof complexity theory. We present a learning problem which is generally consistently
solvable but which cannot be solved consistently in polynomial time unless P 6= N P.
The desired goal is achieved by elaborating an algorithm inconsistently solving thesame learning problem in polynomial time. As far as we know this is the first learning
problem for which the announced properties are rigorously proved. In our opinion,
this result gives strong evidence of seriously taking inconsistent learning strategies
into consideration.
The setting we want to deal with is the learnability of pattern languages introducedby Angluin (1980). Subsequently, Shinohara (1982) dealt with polynomial time learnability of subclasses of pattern languages. Nix (1983) outlined interesting applicationsof pattern inference algorithms. Recently, Jantke (1991) and Lange and Zeugmann(1993) as well as Zeugmann, Lange and Kapur (1995) dealt with the learnability ofpattern languages under monotonicity constraints. Moreover, Kearns and Pitt (1989),
Ko, Marron and Tzeng (1990) and Schapire (1990) intensively studied the learnabilityof pattern languages in the PAC–learning model; thus, Schapire (1990) proved thatthe class PAT of all pattern languages is not PAC-learnable unless P/poly = N P /poly .
So let us define pattern languages. Let Σ = {a, b, ..} be any non–empty finite
alphabet containing at least two elements. Furthermore, let X = {xi i ∈ IN} be
an infinite set of variables such that Σ ∩ X = ∅. Patterns are non–empty strings
from Σ ∪ X, e.g., ab, ax1 ccc, bx1 x1 cx2 x2 are patterns. L(p), the language generated
by pattern p is the set of strings which can be obtained by substituting non–null
strings from Σ∗ for the variables of the pattern p. Thus aabbb is generable frompattern ax1 x2 b, while aabba is not. Pat and PAT denote the set of all patterns andof all pattern languages over Σ, respectively. In order to deal with the learnability ofpattern languages we have to specify from what information the learning strategies
should do their task. Following Gold (1967) we distinguish between learning from text
and from informant. Formally, let L ⊆ Σ∗ ; we call a mapping I : IN → Σ∗ × {+, −}informant of L iff(1) For every w ∈ Σ∗ , there are an n ∈ IN and λ ∈ {+, −} such that I(n) = (w, λ),(2) for every n ∈ IN, w ∈ Σ∗ , and λ ∈ {+, −}, if I(n) = (w, λ) then w ∈ L iff
λ = +.
Let Info(L) denote the set of all informants of L. Furthermore, for I ∈ Info(L)and n ∈ IN, let I n = cod(I(0), ..., I(n)), where cod denotes an effective and bijective
mapping from the set of all finite sequences of elements from Σ∗ × {+, −} onto IN.

Finally, we set In = {w ∈ Σ∗ there are i ≤ n, λ ∈ {+, −} s.t. I(i) = (w, λ)}, andIn+ = In ∩ L, In− = In \ In+ .
Any mapping T from IN onto L is called a text for L. By Text(L) we denote theset of all texts for L. The sets Tn , Tn+ as well as Tn− are analogously defined as above.
Intuitively, a text for L generates the language L without any information concerning the complement of L, whereas an informant of L decides L by informing thestrategy whether or not any word from Σ∗ belongs to L. Note that we allow a text
and an informant to be non–effective.
Definition 8. PAT is called learnable in the limit from informant (abbr. PAT ∈LIM − IN F ) iff there is an effective strategy S from IN into Pat such that for all
L ∈ PAT and every I ∈ Info(L),(1) for all n ∈ IN, S(I n ) is defined,(2) there is a p ∈ Pat such that L(p) = L and for almost all n ∈ IN, S(I n ) = p.
Definition 9. PAT is called consistently learnable in the limit from informant(abbr. PAT ∈ CON S−IN F ) iff there is an effective strategy S from IN into Pat suchthat
(1) PAT ∈ LIM −IN F by S,(2) for all L ∈ PAT , I ∈ Info(L) and n ∈ IN, In+ ⊆ L(S(I n )) and In− ∩L(S(I n )) = ∅.
Note that a consistent learning strategy is required to correctly reflect both thepositive as well as the negative data it has already seen. Next we sharpen Definition
8 and 9 by additionally requiring polynomial time computability of S.
Definition 10. PAT is called (consistently) learnable in the limit from informant
in polynomial time (abbr. PAT ∈ Poly −LIM −IN F (PAT ∈ Poly −CON S−IN F ))iff there are a strategy S and a polynomial pol such that
(1) PAT ∈ LIM −IN F (PAT ∈ CON S −IN F ) by S,(2) for all L ∈ PAT, I ∈ Info(L) and n ∈ IN,
time to compute S(I n ) ≤ pol(length(I n )).
Learning from text is analogously defined in replacing everywhere “informant” by“text.” However, one point should be stated more precisely, namely that consistentlearning from text does only require consistency with the data contained in the text.
In order to have an example illuminating the difference we could define a strategy
that initially outputs x1 . Since L(x1 ) contains every string over Σ but the empty
one, this hypothesis is consistent on text for every finite input. However, since thestrategy has to converge, it cannot maintain this hypothesis ad infinitum. Finally, we
use LIM −T XT , CON S−T XT , Poly −LIM −T XT as well as Poly −CON S−T XT
to denote the corresponding learning types from text.
Now we can state the result mentioned above.

Theorem 11.
(1) PAT ∈ CON S −IN F ,(2) PAT ∈/ Poly −CON S −IN F , provided P =6 N P,(3) PAT ∈ Poly −LIM −IN F .
Proof. Assertion (1) is proved in applying Gold’s (1967) enumeration technique.
Therefore, let (pi )i∈IN be any fixed effective enumeration of Pat. Let L ∈ PAT , let I ∈Info(L) be any informant, and let n ∈ IN. Define S(I n ) to be the first pattern p in theenumeration of Pat satisfying In+ ⊆ L(p) and In− ∩ L(p) = ∅. Since membership for
pattern languages is uniformly decidable, cf. Angluin (1980), S is computable. Dueto the definition of S, consistency is obvious. Moreover, the strategy converges to thefirst pattern in the enumeration that generates the language L to be learned. Notethat S cannot be computed in polynomial time, unless P = N P, since membershipfor pattern languages is N P–complete, cf. Angluin (1980).
Next we have to show that there is no strategy at all consistently learning PATfrom informant that is computable in polynomial time, if P 6= N P. This part of theproof is done by showing the N P–hardness of an appropriate problem defined below.
For any information concerning reducibility as well as N P–complete problems thereader is referred to Garey and Johnson (1979). First we define the following decision
problem SEP . Let W + , W − ⊆ Σ∗ . We say that W + , W − are separable iff there isa pattern p such that W + ⊆ L(p) and W − ∩ L(p) = ∅. SEP denotes the problem ofdeciding whether any W + , W − ⊆ Σ∗ are separable. Moreover, by CSEP we denotethe problem of constructing a separating pattern p for any given W + , W − that are
separable. The proof of Assertion (2) is completed via the following lemmata.
Lemma A. (Ko, Marron, Tzeng, 1990)
3−SAT is polynomial time reducible to SEP .
Lemma B. CSEP is N P–hard.
Proof of Lemma B. Let C3 − SAT denote the problem to construct a satisfying
assignment to any satisfiable instance from 3−SAT .
Claim 1. C3−SAT ∈ P implies 3−SAT ∈ P.
Assume there is an algorithm A having a running time that is bounded by somepolynomial pol in the length of its input, and that, moreover, on input C returns
a satisfying assignment of C, if C is satisfiable. Now let C be any instance of 3 −SAT . Start A on input C. Since any polynomial is time constructible, we may
combine A with a clock, i.e., we can efficiently stop A on input C after at mostpol(length(C)) steps of computation. Then two cases are possible. Either A returns
nothing. Consequently, C cannot be satisfiable. Otherwise A outputs an assignmentass within the given time bound. Then one can check in polynomial time whether or
not ass indeed satisfies C. In case it does, we know that C is satisfiable. In case it
does not C is again not satisfiable, since otherwise A would fail.
Note that we cannot prove the N P–hardness of CSEP in the same manner as inshowing Claim 1, since membership for pattern languages is N P–complete. Hence,
one cannot check in polynomial time whether a pattern eventually returned on input

(W + , W − ) does indeed separate these sets. However, we overcome this difficulty byshowing the following claim.
Claim 2. CSEP ∈ P implies C3−SAT ∈ P.
In accordance with Lemma A let red be any polynomial time reduction of 3−SAT
to SEP . Suppose, there is an algorithm B solving CSEP in polynomial time. Now let
C be any satisfiable instance of 3−SAT . The wanted satisfying assignment may becomputed as follows. First, compute red(C) = (W + , W − ). Since C is satisfiable, we
get that (W + , W − ) are separable. Next compute p = B(W + , W − ). Finally, let ass
be the assignment constructed to p in the proof of the “only–if” direction of Lemma
A. Since red is computable in time bounded by a polynomial in the length of C, thelength of (W + , W − ) is bounded by a polynomial in the length of C, too. Consequently,
ass is polynomial time computable. Hence, C3−SAT ∈ P, if CSEP ∈ P.
Finally, Claim 1 and Claim 2 directly yield Lemma B.
The proof of Assertion (2) is completed by showing the next claim.
Claim 3. PAT ∈ Poly −CON S −IN F implies CSEP ∈ P.
Suppose PAT ∈ Poly −CON S −IN F by some strategy S. Let W + , W − be any
two separable sets, and let p be any pattern separating them. Let I ∈ Info(L(p)) bean arbitrary informant such that, for some n, In+ = W + and In− = W − . In accordancewith the definition of separability, I obviously exists. Consequently, S(I n ) has to be
defined, and furthermore, q = S(I n ) has to be a pattern separating W + , W − . Finally,
S is polynomial time computable. Hence we get CSEP ∈ P.
It remains to prove Assertion (3). In Lange and Wiehagen (1991) PAT ∈ Poly −LIM −T XT has been shown. The corresponding strategy witnessing PAT ∈ Poly −LIM − T XT works by “overlooking” data, namely it ignores all but the actuallyshortest strings of the language to be learned. It turns out that sufficiently many reallyshortest strings of a pattern language do suffice to learn it. From these remaining
strings a hypothesis is generated in time that is even polynomial in the length ofthese strings. However, this hypothesis may be inconsistent, while being correct
in the limit. Let S denote the strategy from Lange and Wiehagen (1991) proving
PAT ∈ Poly−LIM−T XT . We define a strategy S̃ witnessing PAT ∈ Poly−LIM−IN F
as follows. On any input I n we set S̃(I n ) = S(In+ ). This proves (3) and hence thetheorem.
Note that S̃ even works semi–consistently, since In− ∩ L(S̃(I n )) = ∅ is valid for alln ∈ IN. Moreover, S̃ works iteratively as S does.
q.e.d.
At this point some remarks are mandatory. It should be mentioned that any
consistent strategy S, independently of how complex it is, may be trivially converted
into an inconsistent one that works in quadratic time. This is done as follows. On
input I n , one simulates S on input I 1 , I 2 ,...,I n no more than n steps, and outputs
S(I k ), where k is the largest number y ≤ n for which S(I y ) is computable within at
most n steps.
However, it is obvious that this simulation technique does not yield any advantage.
It does neither increase the efficiency of the learning algorithm, if one sums up all stepsof computation until the learning task is successfully solved; nor does it enlarge thelearning power. What we are looking for are “intelligent” inconsistent techniques.

In our opinion, Lange and Wiehagen’s (1991) refined strategy behaves thus by thefollowing reasons. First, it avoids membership tests at all. Second, it iteratively
computes its current hypothesis. Third, the test whether or not it should eventuallychange its mind is extremely simple and may be executed in linear time. Moreover,
the algorithm yielding an eventually new hypothesis performs exclusively syntacticalor formal manipulations over strings.
Finally, let Poly−CON S−LEXIN F (Poly−CON S−LEXT XT ) be the learning
type obtained from Poly −CON S −IN F ( Poly −CON S −T XT ) by restricting theinformation presentation from any informant I ∈ Info(L) (any text T ∈ Text(L))
to the lexicographically ordered one. Furthermore, let S be a strategy such that
PAT ∈ LIM −IN F (LIM −T XT ) by S. Then, for any L ∈ PAT and D ∈ Info(L)∪ Text(L), letConv(S, D) = the least number m such that for all n ≥ m, S(Dn ) = S(Dm )denote the stage of convergence of S on D.
The following theorem actually states that the inconsistent learning strategy ofLange and Wiehagen (1991) may behave both consistently and efficiently, if it receives
the crucial information on the language to be learned in an appropriate order.
Theorem 12.
(1) There are a strategy S̃ and a polynomial pol such that(i) PAT ∈ Poly −CON S −LEXIN F by S̃,(ii) for every p ∈ Pat, there are uncountably many informants I ∈ Info(L(p))
such that– S̃ works consistently on I,
Conv(S̃,I)– Σn=0time to compute S̃(I n ) ≤ pol(length(p)).

(2) There are a strategy S and a polynomial pol such that(i) PAT ∈ Poly −CON S −LEXT XT by S,(ii) for every p ∈ Pat, there are uncountably many texts T ∈ Text(L(p)) suchthat
– S works consistently on T ,Conv(S,T )– Σn=0time to compute S(T n ) ≤ pol(length(p)).
Sketch of proof. Assertion (1), part (i) is proved using the strategy S̃ from the proofof Theorem 11, Assertion (3) above. Then part (i) follows by Lemma 2 of Lange andWiehagen (1991). Part (ii) directly follows from Theorem 2, Assertion (3) of Lange
and Wiehagen (1991).
The first part of Assertion (2) is an immediate consequence of the proof of Theorem
1 in Lange and Wiehagen (1991), while the second follows as above.
q.e.d.

We conjecture that Theorem 11 remains valid after replacing IN F by T XT . The
corresponding Assertion (1) has been proved by Angluin (1980). As already mentioned above, the strategy from Lange and Wiehagen (1991) directly yields (3). Consequently, the only part not yet proved is (2). One reason why (2) seems to be easierprovable for informant than for text is the following. A strategy working consistently
on informant has to work “hard” at any step of the learning process in order to build
its actual “biconsistent” hypothesis, while a consistent strategy on text may output
the trivially consistent hypothesis x1 for an “unbounded” number of steps.

5. Conclusions
We have investigated the problem of consistent versus inconsistent learning. In
spite of the remarkable power of consistent learning it turns out that this power is notuniversal. There are learning problems which can exclusively be solved by inconsistent
strategies, i.e., by strategies that do temporarily incorrectly reflect the behavior of theunknown object on data for which the correct behavior of the object is already knownat the current stage of the learning process. This phenomenon has been investigated ina “highly theoretical” setting, namely in inductive inference of recursive functions. In
this setting the seemingly senseless work of inconsistent strategies could be completely
explained by the undecidability of consistency.
However, it turned out that the inconsistency phenomenon is also valid in more
realistic situations, namely in domains where consistency is always decidable and thelearning strategies have to work in polynomial time. The reason is quite analogous
to that in the setting of arbitrary recursive functions. Providing P 6= N P, theN P-hardness of problems can prevent learning strategies from producing consistenthypotheses in polynomial time. Note that the validity of our main result, Theorem 11,
crucially depends on the fact that membership testing for pattern languages (hence
also deciding consistency for hypotheses patterns, in general) is N P-complete.
On the other hand, inspired by Wiehagen and Zeugmann (1992), Kummer (1992)
has proved that the inconsistency phenomenon also holds in domains where the membership problem is even decidable in polynomial time for any single object to belearned, but not uniformly decidable in polynomial time with respect to the wholeclass of objects to be learned.
Finally, one can easily show that in domains where the membership problem is uniformly decidable in polynomial time, under weak assumptions any polynomial timelearning algorithm can be effectively transformed into a polynomial time algorithm
possessing at least the same learning power and being even consistent. Nevertheless, just in these domains we conjecture that there are learning problems solvableconsistently in polynomial time, but solvable inconsistently (much) faster.
Moreover, we conjecture that our results may be extended to incremental learningof finite classes of finite objects such as Boolean functions, too.
In any case, we regard the results obtained as giving strong evidence to take fast
inconsistent strategies seriously into account.
Finally, the presented results do suggest directions of further research such as

– finding fast inconsistent learning techniques,– deriving conditions yielding that a given learning problem has no fast consistentsolution, but it has a fast inconsistent one.
Acknowledgements
The first author has been supported by the German Ministry for Research andTechnology (BMFT) within the joint project (BMFT–Verbundprojekt) GOSLER under grant 01 IW 101 B9 and E7.
Substantial part of this work has been performed while the first author was visiting
TH Darmstadt. He is grateful indebted to Rüdiger Reischuk and Wolfgang Bibel for
providing inspiring working conditions.
Both authors heartily acknowledge many enlightening discussions with Steffen
Lange (HTWK Leipzig) and with Andreas Jakoby and Christian Schindelhauer (THDarmstadt).

6. References
Angluin, D. (1980), Finding patterns common to a set of strings, Journal of Computer and System Sciences 21, 46 – 62.
Angluin, D., and Smith, C.H. (1983), Inductive inference: theory and methods,
Computing Surveys 15, 237 – 269.
Angluin, D., and Smith, C.H. (1987), Formal inductive inference, in “Encyclopedia of Artificial Intelligence” (St.C. Shapiro, Ed.), Vol. 1, pp. 409 – 418,
Wiley-Interscience Publication, New York.
Barzdin, J. (1974a), Inductive inference of automata, functions and programs, in“Proceedings International Congress of Math.,” Vancouver, pp. 455 – 460.
Barzdin, J. (1974b), Dve teoremy o predel~nom sinteze funkciĭ, in “Teori Algoritmov i Programm,” (J. Barzdin, Ed.), Vol.1, pp.82 – 88, Latvian
State University.
Blum, L., and Blum, M. (1975), Toward a mathematical theory of inductive
inference, Information and Control 28, 122 – 155.
Blum, M. (1967), Machine independent theory of complexity of recursive functions,
Journal of the Association for Computing Machinery 14, 322 – 336.
Fulk, M. (1988), Saving the phenomena: requirements that inductive inferencemachines not contradict known data, Information and Computation 79, 193 –209.
Garey, M.R., and Johnson, D.S. (1979), “Computers and Intractability. A
Guide to the Theory of N P–completeness,” San Francisco, Freeman and Company.
Gold, M.E. (1965), Limiting recursion, Journal of Symbolic Logic 30, 28 – 48.

Gold, M.E. (1967), Language identification in the limit, Information and Control
10, 447 – 474.
Jantke, K.P. (1991a), Monotonic and non-monotonic inductive inference, New
Generation Computing 8, 349 – 360.
Jantke, K.P., and Beick, H.R. (1981), Combining postulates of naturalness ininductive inference, Journal of Information Processing and Cybernetics (EIK)
8/9, 465 – 484.
Kearns, M., and Pitt, L. (1989), A polynomial-time algorithm for learning k–variable pattern languages from examples, in “Proceedings 1st Annual Workshop on Computational Learning Theory,” (D. Haussler and L. Pitt, Eds.), pp.
196 –205, Morgan Kaufmann Publishers Inc., San Mateo.
Ko, Ker-I, Marron, A., and Tzeng, W.G. (1990), Learning string patterns
and tree patterns from examples, in “Proceedings 7th Conference on Machine
Learning,” (B.W. Porter, and R.J. Mooney, Eds.), pp. 384 – 391, Morgan
Kaufmann Publishers Inc., San Mateo.
Kummer, M. (1992), personal communication to T. Zeugmann.
Lange, S., and Wiehagen, R. (1991), Polynomial-time inference of arbitrary
pattern languages, New Generation Computing 8, 361 – 370.
Lange, S., and Zeugmann, T. (1992), Types of monotonic language learning andtheir characterization, in “Proceedings 5th Annual ACM Workshop on Computational Learning Theory,” (D. Haussler, Ed.), pp. 377 – 390, ACM Press, NewYork.
Lange, S., and Zeugmann, T. (1993), Monotonic versus non-monotonic language
learning, in “Proceedings 2nd International Workshop on Nonmonotonic andInductive Logic,” (G. Brewka, K.P. Jantke and P.H. Schmitt, Eds.), Lecture
Notes in Artificial Intelligence Vol. 659, pp. 254 – 269, Springer-Verlag, Berlin.
Michalski, R.S., Carbonell, J.G., and Mitchell, T.M. (1984), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 1, Springer-Verlag, Berlin.
Michalski, R.S., Carbonell, J.G., and Mitchell, T.M. (1986), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 2, Morgan Kaufmann Publishers Inc., San Mateo.
Minicozzi, E. (1976), Some natural properties of strong-identification in inductive
inference, Theoretical Computer Science 2, 345 – 360.
Nix, R.P. (1983), Editing by examples, Yale University, Dept. Computer Science,
Technical Report 280.
Osherson, D., Stob, M., and Weinstein, S. (1986), “Systems that Learn,
An Introduction to Learning Theory for Cognitive and Computer Scientists,”
MIT-Press, Cambridge, Massachusetts.

Porat, S., and Feldman, J.A. (1988), Learning automata from ordered examples, in “Proceedings 1st Workshop on Computational Learning Theory,”(D. Haussler and L. Pitt, Eds.), pp. 386 – 396, Morgan Kaufmann Publishers
Inc., San Mateo.
Rogers, H.Jr. (1967), “Theory of Recursive Functions and Effective Computability,” McGraw–Hill, New York.
Schapire, R.E. (1990), Pattern languages are not learnable, in “Proceedings 3rd
Annual Workshop on Computational Learning Theory,” (M.A. Fulk and J. Case,
Eds.), pp. 122 – 129, Morgan Kaufmann Publishers, Inc., San Mateo.
Shinohara, T. (1982), Polynomial time inference of extended regular pattern languages, in “Proceedings RIMS Symposia on Software Science and Engineering,”
Lecture Notes in Computer Science 147, pp. 115 – 127, Springer-Verlag, Berlin.
Smullyan, R.M. (1961), Theory of formal systems, Annals of Math. Studies 47.
Solomonoff, R. (1964), A formal theory of inductive inference, Information andControl 7, 1 – 22, 234 – 254.
Trakhtenbrot, B.A., and Barzdin, J. (1970) “Koneqnye Avtomaty (Povedenie i Sintez),” Nauka, Moskva,
English translation: “Finite Automata–Behavior and Synthesis, Fundamental
Studies in Computer Science 1,” North-Holland, Amsterdam, 1973.
Wiehagen, R. (1976), Limes–Erkennung rekursiver Funktionen durch spezielle
Strategien, Journal of Information Processing and Cybernetics (EIK) 12, 93– 99.
Wiehagen, R. (1978), Characterization problems in the theory of inductive inference, in “Proceedings 5th Colloquium on Automata, Languages and Programming,” (G. Ausiello and C. Böhm, Eds.), Lecture Notes in Computer Science62, pp. 494 – 508, Springer-Verlag, Berlin.
Wiehagen, R. (1992), From inductive inference to algorithmic learning theory,
in “Proceedings 3rd Workshop on Algorithmic Learning Theory,” (S. Doshita,
K. Furukawa, K.P. Jantke and T. Nishida, Eds.), Lecture Notes in Artificial
Intelligence 743, pp. 3 – 24, Springer-Verlag, Berlin.
Wiehagen, R., and Liepe, W. (1976), Charakteristische Eigenschaften von erkennbaren Klassen rekursiver Funktionen, Journal of Information Processing
and Cybernetics (EIK) 12, 421 – 438.
Wiehagen, R., and Zeugmann, T. (1992), Too much information can be toomuch for learning efficiently, in “Proceedings 3rd International Workshop on
Analogical and Inductive Inference,” ( K.P. Jantke, Ed.), Lecture Notes in Artificial Intelligence 642, pp. 72 – 86, Springer-Verlag, Berlin.
Wiehagen, R., and Zeugmann, T. (1994), Ignoring data may be the only way tolearn efficiently, Journal of Theoretical and Experimental Artificial Intelligence6, 131 – 144.

Zeugmann, T. (1983), A–posteriori characterizations in inductive inference of recursive functions, Journal of Information Processing and Cybernetics (EIK) 19,
559 – 594.
Zeugmann, T., Lange, S., and Kapur, S. (199x), Characterizations of monotonic and dual monotonic language learning, Information & Computation 120,
1995, 155 – 173.