INFORMATIONANDCOMPUTATION

92, 253-284(1991)

One-Sided
Error Probabilistic
and Reliable Frequency

Inductive
Inference
Identification

EFIM KINBER
Computing
29 Rainis

Cenler, Latvian Stale University.
Boulevard,
226250 Riga, U.S.S.R.

AND
THOMAS ZEUGMANN *Departmentof Mathematics,
Humboldl
University
P.O. Box 1297, Berlin 1086, German)

at Berlin,

For EX- and BC-type identification, one-sided error probabilistic inference andreliable frequency identification on sets of functions are introduced. In particular,
we relate the one to the other and characterize one-sided error probabilistic
inference to exactly coincide with reliable frequency identification, on any set 9R.
Moreover, we show that reliable EX and BC-frequency inference forms a new
discrete hierarchy having the breakpoints 1, l/2, l/3,
Et 1991 Academic Press. Inc

1. INTB~DUCTION

Inductive inference has its historical origins in the philosophy of science.
Within the last two decades it has attracted much attention from computerscientists. The theory of inductive inference can be considered as a form ofmachine learning with potential applications
to artificial intelligence(cf. Osherson et al., 1986). Nowadays inductive inference is a welldeveloped mathematical theory which has been the subject of collections ofpapers (cf. Barzdin, Ed., 1974, 1975, 1977) and of several excellent survey
papers (cf. Angluin and Smith, 1983, 1986; Daley, 1986; Klette andWiehagen, 1980). Part of the following work was suggested by an open
problem presented in Daley (1986).
As in previous studies, we deal with the synthesis of programs for recursive functions. An inductive inference machine (abbr. IIM) is a recursive
device (deterministic, probabilistic,or pluralistic) which, when fed more
* The results were obtained during the author’s visit to the computing center of the Latvian
State University.

253
0890-5401/91 $3.00
CopyrIght c! 1991 by Academic Press. Inc
All rights 01 reproductmn
in any form reserved.

254

KINBERANDZEUGMANNand more ordered pairs from the graph of some function, outputs more
and more hypotheses, i.e., programs. There are many possible requirementson the sequence of all actually created programs. Considering deterministic
and probabilistic IIM we shall study explanatory (EX, EX,,,) inference,
where the sequence of programs has to converge to a single program
correctly computing the function to be identified, as well as behaviorally
correct (BC, BC,,,,) in f erence; i.e., all but finitely many programs have tosatisfy the relevant correctness criterion. Furthermore,
the correctness
criteria range from absolute correctness to finite error tolerance. On theother hand, investigating pluralistic IIMs we shall distinguish between thefollowing two cases: First, the sequence of programs is required to containa particular correct hypothesis with a certain frequency (EX,,,). In thesecond case the sequence of programs is required to contain with a certain
frequency correct but possibly distinct programs (BC,,,). The reader is
encouraged to consult Case and Smith (1983), Pitt (1989), and Podnieks(1974, 1975) for further information.
Moreover, we generalize the reliability notion originally introduced byBlum and Blum (1975) and Minicozzi (1976) to all these modes of identification. For EX-type inference, an IIM works reliably on a certain set ‘$Iof functions (e.g., the total functions or the recursive functions) if for every
function from llJz the sequence of created programs does not converge to anincorrect solution. Hence the IIM itself recognizes whether its lasthypothesis may be or may not be correct. In the latter case it performs amind change; i.e., it outputs a program different from the previous one.
Thereby the IIM A4 implicitly transmits an error message to the outside
word. If A4 identifies some function from VJI then its sequence of error
messages is finite, otherwise it is infinite. Thus our generalization works asfollows: Instead of outputting programs, now the IIM M is required to
output ordered pairs (i,, b), where the i, are the programs and b E { 0, 1).
If b = 0, we interpret (i,, 0) as an error message. In other words, b = 1
indicates that M trusts in its current hypothesis. If M does not identify
some function from %II then it again produces an infinite sequence of error
messages. Otherwise, the output sequence contains only finitely many error
messages and among all created programs there are, with a certain
frequency, correct ones.
Transmitting
this approach to probabilistic IIMs we get that on somefunction from YA all possible computations yield either an infinite sequenceof error messages or a finite one, independently of the sequence of coinflips. Furthermore, in the latter case, with a certain probability, there mustoccur sequences of programs satisfying the particular
identification
criterion. Hence, all uncertainty lies in the domain of identilication. Consequently we can interpret this type of probabilistic identification as one-sided
error probabilistic

inference.

INFERENCEANDFREQUENCYIDENTIFICATION255

In the present paper, first we extent Pitt’s (1984, 1989) unification resultsin characterizing one-sided error probabilistic inference to coincide withreliable frequency identification.
Second we prove that the introduced
reliability notion ensures the useful properties known for the ordinary case,i.e., closure under union and finite invariance (cf. Minicozzi, 1976). Third
we investigate the power of reliable EX-type and BC-type frequency
inference in comparing
them with ordinary frequency identification.
Thereby we obtain the strongest possible result, i.e., we show that there areclasses that are reliable EX-identifiable on the set of all total functions withfrequency l/(k + 1) not contained in BC&,& l/k), for all numbers k. This
directly yields four infinite hierarchies. Finally we discuss open problems.
A picture showing the relationships between all the concepts of identification studied in the present paper is given at the end of Section 3.

2. BASIC DEFINITIONS AND NOTATIONS
Unspecified notations follow Rogers (1967). N = (0, 1,2, ....} denotes theset of all natural numbers. The classes of all partial recursive and recursivefunctions of n variables over N are denoted by [FD”and Iw”, respectively. For
n = 1 we omit the upper index. The classes of all partial and total functions
over N are denoted by W and TF, respectively. Let f o PF; then we set
Arg f = {x/f(x) is defined} and Val f = {f (x)/f(x) is defined). For n E N,
we denote by T[F, and [w, the classes of all functions f E PF and f E P,
respectively, for which card( N-Arg f) G n. The classes of all functions f E P
and f E l!J[Fwith colinite domains are denoted by [w, and TF,, respectively.
Let f, gE TF, and nE N; we write f(n) <g(n) if both f(n) and g(n) aredefined and f(n) is not greater than g(n). Furthermore, for f, g E Uff * andHEN we write f =,g
and f =*g
iff card({x/f(x)#g(x)})<nand
car4 {x/f(x) f g(x) >) <co, respectively. Let fCg iff {(x,f(x))/xsArgf}
E {(x3 dx))lx E Arg g}.
system ofBY cpo, ~1, (~2, . . .. we denote a fixed acceptable programmingall (and only all) the partial recursive functions, and by @,, @,, @,, .... anassociated computational
complexity measure (cf. Machtey and Young,1978). IffE P and iE N are such that vi = f then i is called a program for ,f:If q,(x) is defined (written: q,(x),), we also say that q,(x) converges;
otherwise q,(x) diverges (written q,(x) r ).
Sometimes it will be suitable to identify a recursive function with thesequence of its values; e.g., O’lOm denotes the function ffor which f (i) = 1
and f (x) = 0 for all x # i. Using a fixed effective encoding ( . . . ) of all finite
sequences of natural
numbers onto N we write fn instead of((f(O), ....f(n)>. for any nE N, fE PF, where f(x) is defined for all x~n.

256

KINBERANDZEUGMANN

Proper set inclusion is denoted by c in distinction from c; and by #we denote incomparabilityof sets.
A sequence (.LJneN of natural numbers is said to be convergent to anumber j iff j, =j for almost all II.
Now we define several concepts of identification. In the sequel we deal
only with the inference of everywhere defined functions, since this suffices
to get the desired results. Unless otherwise stated, an IIM M is just a partial recursive function. Suppose an IIM M is given the graph of some function f E U[F as input. We may suppose without loss of generality that f isgiven in its natural order (f (0) f (1) ....) to M (cf. Blum and Blum, 1975).
DEFINITION
1. Let a E N u ( * }, and let f E TIF. An IIM M EX”-identifies f iff M(f”) is defined for any n E N, and the sequence (J4(f”)),,N
converges to a number i such that ‘pi = J

If M does EX”-identify f, we write f E EXa(M). The collection of EX”inferrible sets is denoted by EX”; formally, EX” = ( U/3M [U 5 EX”(M)] }.
For a = 0 we omit the upper index.
EX-identification
was originally introduced by Gold (1965) (so-called
identification in the limit), whereas the a = * case was studied first by Blumand Blum (1975). Furthermore, Case and Smith (1983) have investigatedEX”-identification
for all a E N u { * 1, obtaining the hierarchy
EXcEX’c... c u EXUcEX*.
USN

Interesting results concerning the power of EX”-identification
found in Chen (1982).

can also be

DEFINITION
2. Let %JIs %[F, and let a E N u { * 1. An IIM ME [w worksEX”-reliably on the set 9JI iff for every function f E %R either the sequence
WW-YL, N converges to a number i such that ‘pi =,f or it diverges.
DEFINITION
3. Let a~fVu{*},and let !JJI s TF. An IIM M reliablyEX”-identifies f E U[F on the set 9JI iff M works EX”-reliably on the set YJI
and M EX”-identifies J:

If M does reliably EX”-identify f on the set YJI we write f E m-REX”(M).
The collection of reliably on ‘DI EX”-identifiable
sets is denoted by
m-REX”. Again, for a = 0 we omit the upper index.
Reliably working IIMs were originally introduced and studied by Minicozzi (1976) and Blum and Blum (1975) in case a = 0, *. In Kinber andINFERENCEAND

FREQUENCY

257

IDENTIFICATION

Zeugmann (1985) the collections UIF-REX” and [W-REX” have been
considered and the following hierarchy was pointed out:
TF-REXnc TF-REX’

c . . . c U TF-REX”cTF-REX*
ueN

n

n

[W-REX c [W-REX’ c . . c u

F&REX”Ac

E&REX*

utN

Next we consider behaviorally correct inference which has been introduced by Barzdin (1974) and which has been studied intensively in Caseand Smith (1983).
4.

DEFINITION

tiliesfiff

M(f”)

Let a E N u { * }, and let f~ UF. An IIM A4 BC”-idenis defined for all IZE N, and v~,~~, =,f, for almost all n.

We write f~ BCa(M),if M
BC”= { U/3M[UcBC”(M)]}.
Case and Smith (1983) proved that
EX*cBCcBC’c

does

BC”-identify

f

and

set

... c u BC”cBC*,
UEN

where the first inclusion was first shown in Barzdin (1974). Moreover, Leo
Harrington discovered that [wE BC* (cf. Case and Smith, 1983). The reader
is also encouraged to consult Chen (1981) for more results concerningBC”-identification(e.g., the complexity of the synthesized programs).
Now we introduce reliable BC”-identification.
As already explained in
the Introduction,
we now require the IIM to output ordered pairs (i,, h),where b E (0, l}, instead of only outputting programs. If b = 0, then (i,, 6)
is said to be an error message.
DEFINITION
5. Let ‘$I c UF, and let a E N u { * }. An IIM ME iw works
BC”-reliably on the set !JJI iff for every function fc’9Jl either the output
sequence (i,, b,) satisfies (i,, b,) = (i,, 1) and vie =0 5 for almost all n, or
there are infinitely many n such that (i,, b,) = (i,, , 0).

In other words, either M does BC”-identify f or it produces infinitely
many error messages. Note that we do not require (i,, 1) to imply ‘pi, =U f:
DEFINITION
6. Let a E N u { * }, and let YJI G UF. An IIM M reliably
BC”-identifies f E UF on the set 9JI iff M works BC”-reliably on ‘$I and M
does BC”-identify f:258

KINBERANDZEUGMANN

If M does reliably BC”-identify f on ‘33 we write f E %R-RBC”(M) and wedenote by YJI-RBC” the collection of reliably BC”-inferrible sets on %I.
Please note that it is not hard at all to encode the error messages into
the current hypotheses; e.g., we may force the IIM to output on fn insteadof (i,, 0) a program j, such that cpi,(x) 1 and cpi,(x) #f(x), for all x 6 n. On
the other hand, our formalization is technically much more convenient.
Next we deal with frequency identification due to Podnieks (1974).
DEFINITION
7. Let 0 <p < 1, and let f E TIF. An IIM
with frequency p iff M( f “) is defined for all n E h3 andThen we set BC,,,(p)= { U/S4

M BC-identifies f[M identifies every f E U with frequency

PI).
Podnieks (1974, 1975) shows that BC,,,( l/(n + 1)) c B&,,,( l/(n + 2)),for any n E IV. Moreover, he points out that the B&,,(p)hierarchy is discrete; i.e., given any p with l/n >p > l/(n + 1 ), then BC,,,,(p) = BC,,,( l/n).
Pitt (1989) has introduced what is essentially the EX version of Podnieks’and he has proved that the analogous
BC-frequency identification,
theorems are true.
DEFINITION
8. Let 0 <p < 1, and let f E Tff An IIM M EX-identifies fwith frequency p iff M(y) is defined for all n E N, and there is a particular
program i such thatand cpi=f:
By EX,,,(p)EX-identifiable

lim inf card( (n/M(f”)= i, 0 6 n < k} )k-mkwe denote the collection
with frequency p.

BPof all function classes U that are

In order to introduce reliable frequency identification, the IIMs are again
required to output pairs (i,, b,). Furthermore, looking at EX-frequency
inference we require the particular program i computing the considered
function to occur at least with frequency p. Moreover, the created output
sequence is only allowed to contain finitely many error messages; i.e., theprogram i is at almost all places accompanied by b = 1.
DEFINITION

BC-identifies

9. Let W c TIF, and let 0 <p < 1. An IIM ME Iw reliably(EX-identifies) f E [w on the set YJI with frequency p iff

INFERENCEAND

FREQUENCY

IDENTIFICATION

259(1) for all g E ‘3.R either the output sequence (M( g”)),, N contains
only finitely many error messages and M BC-identifies (EX-identifies) g
with frequency p OY in the sequence (M(g”)),, N error messages occur
infinitely often, and(2) A4 BC-identifies (EX-identifies) f with frequency p.
If M does reliably BC-identify (EX-identify) f on the set W withfrequency p we write f E%R-RBC,,,(p)(M)(f~ %I-REX,,(p)(M)).
Furthermore
we set YJI-RBC,,,,(p) = { U/3M[Uz
YJI-RBC,,,(p)(M)]},and analogously define !IJI-REX,,,(p).
Next we define team inference, which was originally introduced bySmith (1982). A team is a finite collection of IIMs. A team (M,, .... M,)
successfully BC-infers (EX-infers) a set U G [w if, for each fo U, someteam member Mj successfully BC-identifies (EX-identifies) f: Furthermore
we set BC team(n) = { U/j(M,,.. .. M,)[Uc_ BC(M1, .... M,)] ), and declareanalogously EXt,,,(n).
Smith(1982) proves that B&.,,(~)cB&&n+ 1) as well as
EXt,,,(n) c EXteam(n + 1) for any n 3 1. The unifying results stating that
BC,,,( l/n) = BC1,Bm(n) and EX,,,(l/n)= EXteam(n) are due to Pitt (1989).
Note that it is not meaningful to consider teams of BC”-reliably working
IIMs as well as of EX”-reliably working IIMs, since the classes !D2-REX”(cf. Minicozzi, 1976) and !IJI-RBC” (cf. Proposition 1) are closed under
enumerable union. However, reliable frequency identification is a powerfultool combining the advantages of reliability with those of bounded nondeterminism, as we shall show.
Finally, in this section we define one-sided error probabilistic inference.
For the sake of intuition as well as for any mathematical background thereader is referred to Pitt (1984, 1989).
A probabilistic IIM P is simply a deterministic IIM which is allowed toflip a “t-sided coin.” For any fixed sequence S of coin-flips P behaves likea deterministic IIM, which we denote by Ps. We again require P”, for any
sequence S of coin-flips, to output ordered pairs (i,, b,).
DEFINITION

probabilistic
ity p iff(1)u%“)L,

10. Let W G TIF, and let 0 <p < 1. An one-sided error
IIM P on YJI BC-identities (EX-identifies) f B [w with probabil-

for all g E W and all sequences S of coin-flips the output sequence
N satisfies either (a) or (p).
(@I V”k”)),,
N contains only finitely many error messages (independently of S) and the probability (taken over all sequences S) that Ps
BC-identifies (EX-identifies) g is greater than or equal to p.

260

KINBERANDZEUGMANNerror messages occur infinitely(/I) in the sequence (PS(g”)),,N
often (again independently of S).
(2) The sequence (PS(f”)),,M
fulfills (a).
If P does BC-identify f on %R with one-sided error probability p,
we write f E %R-RBC,,,,(p)(P)and set IIJI-RBC,,,,(p)= { U/3P[ U G~-RB’&,(PW’H 1. 1n an analogous way we define %R-REX,,,,(p)(P)and YJ&REX,,,,(p).
In the sequel we shall study the unknown
above defined modes of inference.

relationships

between the

3. RESULTS
3.1. One-Sided Error Probabilistic Inference and Reliable Frequency Identification

In this section we extend Pitt’s (1984) unification results to show that
one-sided error probabilistic
inference is exactly the same as reliablefrequency identification. Moreover, as an immediate consequence from thetheorem below one gets that, if there is any hierarchy for reliable frequency
identification, then it must be a discrete one. As it turns out, Pitt’s techniques of proof are powerful enough to show the desired results. Please notethat if one is only interested in the discretness result concerning reliablefrequency identification then shorter proofs can be obtained by applying
Podnieks’ (1975) techniques. However, since it is our goal to get moregeneral theorems, we shall follow Pitt. Because Pitt’s proofs work mutatis
mutandis in our setting we shall describe only the minor changes whichhave to be made. Therefore, the reader is advised first to consult Chapters 2
and 3 of Pitt (1989).
Let P be any one-sided probabilistic
IIM which is, without loss ofgenerality, equipped with a two-sided coin, and realized by a Turingmachine, and let fo TF. Then 2,, denotes the infinite complete binary
computation tree which represents all the possible computations of P on
input J
Now we are ready to present the first theorems.
THEOREM 1. Let nE N, and let llJl GT[F. Furthermore, let UE%R-RBC,,,(p)with 1 >p > l/(n + 1). Then
(1) there is an IIM A4 reliably BC-identqying U on ‘%Nwith frequencyl/n;iNFERENCEAND

FREQUENCY

IDENTlFICATION

261(2) for any f E (I the sequence ( (ik, bk)ke N of M’s hypotheses on f has
the property that there is some r E (0, .... n - 1 } such that (pik = f, for almost
all k with k ESr mod II.
Proof
The proof essentially coincides with Pitt’s (1989) proof that
B&,,(p)= BC,,,,(l/n).
Hence we describe only the IIM which will
reliably identify U on !lJI with frequency l/n, thereby satisfying (2).
Let U E !IJI-RBC,,,,(p)(P).
The idea underlying our construction is quite
similar to the idea used by Pitt to show that B&,,(p)= B&,,(n).
Wefirst ensure that for any f E W in which P produces infinitely many error
messages (remember that this happens independently of the sequence ofcoin-flips) each team member also outputs infinitely many error messages.
On the other hand, if P outputs only finitely many error messages on f e ‘9Jl
(again independently of the coin-flips) then each team member behaves
exactly as in Pitt’s team.
This modification is achieved as follows:
We introduce an auxiliary parameter d having the initial value 1. The
computation
tree 2,, is now constructed stepwise; i.e., for f E 9.R andk = 1, 2, 3, .... the ith team member builds the finite computation tree 2,
just consisting of the first k levels of 2,, Then it first tests whether eachpath in 2, contains at least d error messages. If the test is fulfilled, Mj outputs (k, 0) and increments d, i.e., d : = d + 1. Otherwise it tries to computea new hypothesis by inspecting all nodes at level k. This actually requires
the installation of a time regime in order to effectively execute instruction
4 in Pitt’s definition of the team member M,. If no new hypothesis can becomputed within the given time then Mi(f ‘) = Mi(f ‘- I). For completness
we define Mi(f ‘) : = (0,O).
NOW it is obvious that Mi produces infinitely many error messages if P
behaves thus. Suppose that P outputs only a finite number of error
messages. Let d,, be the least number of error messages taken over all paths
in 2,,. Consequently, for d> d,, the test introduced above cannot besatisfied. Moreover, in accordance with the definition of !IJ&RBC,,,i, theIIM P must infer J: Hence Mi behaves in the limit as Pitt’s ith team member does. Since in general not every team member identifies f, only those
ones that infer f behave reliably on ‘5X, i.e., at least one team member.
However, the desired IIM can now be defined. A4 simply outputs the
hypotheses of the team members MO, .... M,- i in a rotating order. Suppose
M, identifiesf: Then ‘pi, =f, for almost all k with k s r mod n.
Q.E.D.
THEOREM
2. Let !IXlc TIF, no N, and let UE~JI-RB&,(~)
with lap>l/(n + 1). Then there is an IIM A4 reliably BC-identifying U with frequency
I/n. Moreover, the output sequence ((ik, bk))ks N of M’s hypotheses has for262

KINBER AND ZEUGMANN

any f E U the property that there is an r E { 0, .... n - 1) such that ‘ps = f foralmost all k = r mod n.
Proof. The theorem is shown in the same way as Pitt (1989) proves his
theorem stating B&,(p)c BCteam(n), with the following minor differences.
Let fe8J& and let kefV. Suppose UE%JGRBC,,,(~)(M’).
If M'(fk)=(ik, 0) then each team member M,, .... M, _ i straightforwardly
outputs(ik, 0). Otherwise the team behaves exactly as Pitt’s team does, but accompanies each guess with b, = 1. Finally, the wanted IIM M again outputs the
hypotheses of the team members in a rotating order.
Q.E.D.
COROLLARY 3. Let W G T[F. Then m-RBC,,,,(
for any number n 2 1.

I/n) = LIJZ-RBC&( l/n),

Proof. Due to Theorem 1 we have W-RBC,,,,( l/n) z !Il&RBC,,,( l/n).
In order to prove the other inclusion, first we apply Theorem 2. Without
loss of generality we may assume that the desired probabilistic IIM P isequipped with an n-sided coin. P flips the coin once and obtains, withprobability l/n, a particular value r E (0, .... n - 1 }. Then it outputs only theguesses (ik, bk) with k zz r mod n.
The rest is obvious.
Q.E.D.

Finally, in this section we show that Theorems 1 and 2 as well as
Corollary 3 remain valid if reliable BC-frequency identification is replacedby reliable EX-frequency inference.
THEOREMnEN, and let 93 c U[F. Furthermore,with 1 >p > l/(n + 1). Then

4. Let%&REX,,,,,(p)(1) there is an IIM

M reliably EX-identifying

let

UE

U on YJI with frequencyl/n;(2) for any fc U the sequence((ik, bk))kcN of M’s hypotheses on f issuch that there are some r E (0, .... n - 1 > and j E N satisfying ik = j and ‘pi = f
for almost all k with k E r mod n.
Proof. The proof mainly follows Pitt’s (1989) demonstrationof thetheorem, which actually states that EX,,,,(p) c EXteam(n), except for thesame minor changes we made in proving Theorem 1. That means thedesired machine A4 again simulates the EX-team M,, .... M,- i. Each Mi
first tests whether any path in Zk exceeds a certain threshold d of error
messages. In case it does, Mi outputs (k, 0), increments d, and continues on
f k+ ’ . Otherwise it works exactly as Pitt’s machine Mi does. Finally, A4 outputs the guesses of the team members in a round-robin fashion. We omit
Q.E.D.
the details

INFERENCEANDFREQUENCYIDENTIFICATION

263

THEOREM 5. Let 9Jl G UIF, n E N, and let UE%N-REX~,&)with
1 3p > 1(n + 1). Then there is an IIM A4 reliablv EX-inferring U with frequency l/n. Moreover, the output sequence((ik, bk))ks N of M’s hypotheses
on any f E U behaves such that there are an r E (0, .... n - 1) and a jg N
satisfying ik = j and vi = f for almost all k z r mod n.

Proof: Using
Pitt’s(1989) proof of Theorem
statingthatEX,,,(p) s EX,,,,( n ) our theorem is shown in adding the following:
Let f E %R, and let kE N. Assume UEW-REX,,,(p)(M’),
for some
IIM M’. If A4'(fk) = (ik, 0) then each team member M,, .... M, _, again

straightforwardly outputs (ik, 0). Otherwise, the team works as Pitt’s team
does, but accompanies each guess i, with b, = 1. The desired IIM M now
Q.E.D.
simulates the team and outputs its hypotheses in rotating order.
6. Let ‘9Jlc T[F. Then YJ&REX,,,,(
for any number n 3 1.
COROLLARYl/n) = ‘%R-REX,,,(l/n)

One-sided error probabilistic inference is thus completely characterized.
Consequently, in the sequel it suffices to deal with frequency identification.
3.2. Closure Properties

In this section we show that the reliability notions introduced above
preserve the closure properties originally pointed out by Minicozzi (1976)
for reliable EX-identification.
For all a E N u { * ) the WI-REX” case has
already been handled in Kinber and Zeugmann (1985). Thus it remains todeal with Il;n-RBC,,,( l/n), !JJL-RBC”, and ‘9JI-REXf,,q( l/n).
The following proposition states that any reliable inference is closed
under recursively enumerable unions.
1. Let !lJl E T[F, and let ID E {RBC,,,,(l/n),
RBC”,
nEFV, aENu (*}}.
Furthermore, let (IV,),.,,
be arecursive enumeration of IIMs working in the senseof m-ID. Then there
exists an IIM A4 such that m-ID(M)= U;, N mm-ID(Mj).
PROPOSITION

REX,,,(l/n)/nal,

ProoJ: In essence we transform Minicozzi’s (1976) basic idea into our
setting. Let (Mi)iE N be a recursive enumeration of IIMs working in thesense of W-ID, and let f E %R.If a machine Mj identifies the function f thenMj(fk) = (ik, 1) for almost all k. On the other hand, each machine Mj notinferring the function f produces infinitely many error messages, i.e.,Mj(fk) = (ik, 0) infinitely often. The wanted IIM M identifying Ui, N %HID(M,) searches for an enumerated machine that eventually identifies thefunction f as follows:
The machine A4 dovetails the computation of more and more outputs ofthe enumerated machines. Moreover, the IIM M counts for each machine
643,9x-9

264

KINBERANDZEUGMANNMi already included into the computation
the number of successively
produced hypotheses that uniformly contain a 1 in its second component.
This number is called weight. As long as a machine Mi trusts in its current
guesses the weight successively increments. If Mi produces an error message
then the weight of the IIM Mi reduces to zero. After having read the initial
segment f" of the function f the machine M favors from the first k
enumerated machines that one which actually has the greatest weight. In
case the maximal weight is taken by at least two IIMs Mi and Mj themachine M chooses that one which has the smallest index.
We formally define the IIM A4 as follows:
LetfeSJ3, and k~fV.
M( f k, : = “Compute in parallel-

Mk-l(f”),Mk-I(fl),Mk(f “)and assign to each IIM Mi, i < k, its weight, i.e., the greatest m <k - isatisfying
that
every guess of M,(fkpi-"),the condition
A&(fk-i--mfl),...,
Mi(fk- i, uniformly contains a 1 in its second component. Choose w(k) to be the smallest i 6 k such that the IIM Mj has
the greatest weight.
In case all considered machines have weight zero, output (k, 0). If not:If w(k) = w(k - l), then output Mw,(k)(fk-W(k)). Otherwise output(k, O).”
Note that M outputs an error message at least in case it favors a newmachine possibly inferring f:
Now let f E ‘9JI and assume f E YJI-ID(M,) for some j. Hence there is an j,such that M,(f “) = (jk, 1) for any k 2 j,. Consequently, 44,‘s weight grows
continously for k > j,. Moreover, any machine Mi not identifying f outputs
infinitely many hypotheses of the form (i,, 0). Therefore, after computing
an error message Mi has weight zero. Thus, for almost all k the machine
M must favor exactly one of the Mj’s inferring f, i.e., M( fk) = Mj(fkpj).
Hence A4 identifies f, since the linite delay does not affect the frequency. On
the other hand, if no machine recognizes f EIlJZ then either all machines
under consideration have weight zero, or w(k) # w(k - 1) infinitely often.

265

INFERENCE AND FREQUENCY IDENTIFICATION

The latter follows from the fact that every Mi produces an infinite numberof error messages. In both cases, M also outputs an error message. Hence
Q.E.D.
M works ID-reliably on YR.
The next proposition states that reliable identification is closed underfinite variance. For any class UE (w, let [IV] = {g/gE Iw, 3fl-f~ U,

f =*ba.
PROPOSITION

REX,,,,(l/n)/n>
W-ID.

2. Let 1132
G Tff, and let ID E (RBCr,,J l/n),
RBC”,
1, no N, a~ N u { *}}. Then UE‘ZR-ID implies [U] E

The proof is analogously done as in Minicozzi
we omit the proof here.
ProoJ(1976). Therefore
Q.E.D.

3.3. Hierarchy Results

The main goal of this section consists in clarifying the basic identification
power of reliable frequency inference on sets %I, We confine ourselves toconsider exclusively the cases Y.JI= %[F and %R= [w, since they are of basic
interest. We start with several fundamental observations that give a firstanswer to the question of what actually can and cannot be reliably inferredwith a certain frequency. Above all, in accordance with our theorems in
Section 3.1, it generally s&ices to deal with the discrete frequencies 1, l/2,
l/3, ... . Note that by definition
U[F-REX,,( l/n) E T[F-RBC,,,( l/n) E[W-RBC,,,( l/n), for any number n Z 1. In order to obtain results as sharp
as possible we proceed in the sequel almost always as follows: Studying thepower of reliable frequency inference we deal, whenever appropriate, withUIF-REX,,,( l/n) or Uff-RBC,,,,(l/n);
whereas its limitations are shown indealing with lR-RBCrreq( l/n).
First of all, we point out that reliable frequency identification is generally
less powerful than the ordinary frequency inference.
THEOREM

7. EX\IW-RBC,,,(l/n)#@forevery number n 2 1.

Proof: Podnieks’(1974) BC-frequency hierarchy theorem directly
implies that [wI$ BC,,,(l/ n ), and hence iw# R-RBC,,,( l/n), for any n 2 1.
We set U= {f/feR, cp
f(o) =f}. Assume that UE [W-RBC,,,( l/n). Then
Proposition 2 implies that [U] E IW-RBC,,,( l/n), which is a contradiction
because [U] = [w.On the other hand, UE EX.
Q.E.D.

As an immediate
COROLLARY(1)(2)

consequence one gets:

8. For any number n B 1:

R-RE&,,,(lln)~-RBGr,,(l/n)= EX,,,(lIn),= JGr,,(lIn).

266

KINBERANDZEUGMANN

Next we ask whether %%REX,,,(l/n)
is always properly contained in
m-RBC,,,( l/n). The affirmative answer is given by the following theorems
which, beyond that, lead to a much deeper insight into the capabilities ofreliable frequency inference.
THEOREM

9.

%[F-RBC\EX*# $Z?

Proof: In the sequel we mainly use Gold’s (1965) diagonal arguments.
Showing that EX c BC Barzdin (1974) has refined Gold’s (1965) proof
technique in such a way that he gets a BC-inferrible function class.
Barzdin’s (1974) technique is powerful enough to prove the theorem.
We interprete every partial recursive function as an IIM. As was alreadyshown by Gold (1965), there is an effective procedure g E [w such that
EX*((p,) E EX*((p,,,,) and (POE [w,for every ie N. For convenience we set
Mi : = ‘pgcij for every in N. Let i be given. Now we define a class Ui suchthat Ui$ EX*(M;). We set f,(O) = i. Compute ni, = Mi( (i)).
For k = 1, 2, 3, .... check by dovetailing whether (CI) or (p) happens:ta)

Mi(<i1k))(B)

Mi(<iok))Zni,.

Zni,,

If neither (CI) nor (p) happens we set Ui= {iOm, il O”>. Consequently,
Ui#EX*(Mi).
Now suppose a k, is found satisfying (CI) or (p).
If (a) happens, then delinef.(x) = 1, for 1 <x< k,.
If (fl) happens, then define fj(x) = 0, for 1 < x 6 k, .
In both cases continue as follows:
Compute ni, = Mi(ffl).
For k = 1, 2, 3, .... check in dovetailing whether(a) or (/?) happens:(Co ~i(G-i(O)~~~fi(k,)
lkN+ni,>(B) M;((f,(0)..‘~(k,)Ok))#niz.
In case neitherf,(O)....L(k,)(CI) nor (p) happens

we set Ui= (fi(0) . ..fi(k.) O”,
If a k, is found which1”). Then we again get Ui $ EX*(M,).

fulfills (c() or (a) proceed as follows:
Suppose (c() happens. Define L(x) = 1, for k, + 1 <x d k, + k, + 1.
Incase(/?)happensdefinefi(x)=0,fork,+1<x<k,+k,+1.
Iterate the construction. Now assume infinitely many k, are foundsatisfying the relevant conditions (~1) or (b). Then fie [w and the sequence
does not converge . Hence in this case we set Ui= {fi}C”i(fl))neN
yielding Ui# EX*(M;). Finally, let U= uis rmUi. Thus Uq! EX*.
It remains to prove UE TF-RBC(M),for some IIM M. Let fe U[F and let
ne N. We define:M(f”)=“Simulate

the constructionof U,,,, in computing

just the firstINFERENCEAND

FREQUENCY

ij

coincides
valuespresented

f(n)
f(O)

with
reby this

the

f(l)

-...

267

IDENTIFICATION

branchf------FIGURE1

II levels of the tree which actually represents the possible structure ofu f(O,. This finite tree has at most two branches since one branch will bedeleted whenever the relevant (c() or (p) happens. If the initial segment
f(O). . .f(n) turns out to be different from all branches just existing thenoutput (n, 0).
Otherwise, output (e, l), where e is a canonical program of thefollowing function q. For every x < n we set q(x) =f(.u). The algorithm
computing 11for x > il works as follows:
Continue to completely simulate the construction of U,,,,,. Two cases
are possible.
Case 1. No relevant (a) or (B) happens. Then the values of 4 areequal to thoses represented by this branch (cf. Fig. 1).

Case 2. The relevant (a) or (B) happens. Remember that one branchcorresponds to the computation
performed in (a) while the other one
corresponds to the computation
performed in (/I). Now we have to
distinguish between the following subcases:
Subcase 2.1. The branch coinciding
with q(x), for all x <n,represents the computation
performed in (a), and (8) happens. In
accordance with our construction the branch representing the computation performed in (a) is then deleted. As long as the computation in (a)is performed q(x) is defined. After the deletion of that branch q(x) is
undefined (cf. Fig. 2).
qcoincides
valuespresentedf(n)- . e-0
f(O)
w-.

f(l)
_ _

--m--theat

FIGUREwith
repreby
this

the

2

:

branchI’i

undefined
has

point
which

and

remains

after
happend(8)

happens

(/3)

268

KINBER AND ZEUGMANN

Subcase 2.2. The branch coinciding
with q(x), for all x<n,represents the computation performed in (/I), and (cc)happens. This caseis handled analogously to Subcase 2.1.
Subcase 2.3. The branch coinciding
with q(x), for all x 6n,
represents the computation performed in (oz), and (ct) happens. Then the
branch representing the computation performed in (fl) is deleted. The
construction is iterated; i.e., (a) and (/I) are restarted with new values.
The function ye will not be computed further until (c() or (fi) happens
again. Suppose (a) or (8) happens. Then one branch will be deleted.
Now the function ye can be defined for all those arguments that
correspond to the branch not beeing deleted, i.e., 9 coincides with thevalues between these ramification points. By iterating this construction,u] can eventually be computed for more and more arguments (cf. Fig. 3).
Subcase 2.4. The branch coinciding
with q(x), for all x < n,represents the computation performed in (fl), and (fl) happens. This casecan be handled analogously to Subcase 2.3.”

It remains to show that the IIM

A4 identifies U.

U ETIF-RBC(M)Claim.

Case 1. f$ U. By construction we get f$ Uf(OJ. Therefore, almost all
initial segments off differ from the actually created tree. Hence, M(f”) =(n, 0) for almost all n.
Case 2. f~ U. Thus we conclude f~ U,,,,. Suppose card( Ufco,) = 2.
Then U&) is represented by a tree consisting of an initial segment which
ramifies at a certain point n, into two infinite branches. The constructionof A4 now ensures that M’s output is correct for any n > n,.
If card( U,(o,) = 1 then A4 outputs only correct hypotheses.
Q.E.D.
THEOREM

10. Let ‘98~ {TF, R}, and let aE N u { * }. Then YJ&REX”c

mm-RBC.
the

(a)
f(O)
o--.

pt-++t+t+Hl

point
happened
0 thisatwhichbranch___ _ .--D“\cl-.

- /-c---t

has
j

been

deletedthisbranchrepresents
T-J

i7
\

D--.-.-El
the(8)

FIGURE3

point
happensi this; willat whichagain

branchbe deleted

INFERENCE AND FREQUENCYIDENTIFICATION

269

Proof: Due to the preceding theorem YJI-RBC\%R-REX* # @ isobvious. Hence it suflices to show that ‘5%REX”&%&RBC,
for everya E N u ( * }. This is done as in Case and Smith (1983), whereas every mindchange of M witnessing that U E ‘%&REX” is reflected by an error message.
Q.E.D.

The following
BC-inference.
COROLLARY

corollarysummerizes

the results concerning

reliable

11. EX* # T[F-RBC and EX* # I&RBC.

Since EX c EX * and IW-RBC = IW-RBC,,,( 1) the corollary is an
Q.E.D.
consequence of Theorem 7 as well as of Theorem 9.

ProojI

immediate

By the next theorem we heighten the known results dealing with thecapabilities of reliable EX”-identification.
THEOREM

12. TlF-REX”\EX,,,,(a)# @for any a E N.

Proof: The a= 1 case has already been proved by us previously(cf. Kinber and Zeugmann, 1985). In the sequel we demonstrate how thegeneral case can be handled. However, we present the proof for the casea = 2 only since thereafter the generalization is straightforward. Every number i is interpreted to be just the encoding of two IIMs M,, M, which wewant to fool. Without loss of generality we can assume that M,, M, E [w(cf. the proof of Theorem 9). Now, for every ie N we effectively construct
a functionf,E Iw, such that there is a total extension off, (possiblyfi itself)
on which the related team M,, M, fails.
Let i be given. Compute n and m. We set J;(O) = i. Then define fi (2),f,(3), *..>to be zero until a k, is found such that

(~1
(B)
(7)
(6)

M,((i))ZM,((ilOkl)),orM,((i))
ZM,((iOOk’)),orM,((i))ZM,((ilOk’)),orM,( (i)) # M,( ( iOOk’)) happens.

If no such k, is found then f, is already defined for all but one argumentx (namely x = 1).
If (g) or (p) happens then set A.( 1) = 1 or fi (1) = 0, respectively. Furthermore, let 1 = m, and r = n.
If (y) or (6) happens then set f, (1) = 1 or h( 1) = 0, respectively, but let
l=n, and r=m.
In the parameter r we remember which machine has made the mindchange. In order to fool the whole team now we are mainly interested in270

KINBERANDZEUGMANNa mind change of the machine M1. However, M, may not behave thus.
Therefore we introduce a second trap.
LOOP.
Set r=fi k’fl . Now define fi(k, +4), fi(k, + 5) .... to be zero until a k,
is found such that either
(a)
PO)
(D,)
&J
h)
(yd
(yii)

‘PM,(r) (k, + 2) turns out to be delined within k2 steps, orM,(z) # M,(zOk2+ 2), or
Ml(~) # M,(r10k2+ ‘), or
M,(r)
M,(z)
M,(z)
M,(r)

f M,(TO~*+~), orf M,(zOIOk*), orf M,(z10k2 + ‘L or# M,(zllOkz) happens.

If nothing

happens thenf,

x=k,+2,k,+3).

is defined for all but two arguments x (namely

Suppose (a) happens first. Then we set fi(k, + 2) = 1 2 cpM,(kl + 2) and+ 3) = 0. Swap 1 and r. Goto LOOP and iterate the construction.
In case (&,) or (/IL) happens first, we set fi(kl + 2) = 0 or fi(kl + 2) = 1,
respectively, and define fi(k, + 3) = 0. Swap 1 and r. Goto LOOP and
iterate the construction.
Now we assume one of the (ycd) cases happens, where c, dE (0, 1 }. Stop
all procedures. Define fi(kl + 3) = d and set z = c.

f;(k,Remark.

fi(k,+ 2) remains undefined yet.

LOOP 1
Proceed as follows:
Define fi(k, + k,+6),
such that either
(A)
(B,)
(B,)
(C,)
(C,)

fj(k,

+ k,+7),.... to be zero until a k, is found(PM,(T)(k, + 2) turns out to be defined within k, + k, steps, or+ 3) Okz) # M,(zzfi(k,+ 3) Ok20k3+ ‘), orM,(rzfi(k,+ 3) Ok*) #M,(rzfi(k,+ 3) Ok210k3), orM,(z) # M,(zzfi(k,+ 3) Ok20k3+ ‘), orM,(z) # M,(rl - zx.(k, + 3) Ok20k3+‘) happens.
M,(zzfj(k,Comment.
By (B,) and (B,) we actually search for the next mindchange of machine M,. In (C,), (C,) we essentially proceed to test whether
the former (PO) or (/Ii) happens, but we take into consideration thatmeanwhile fi(k, + 3) has been defined. The earlier step (a) is replaced by(A), i.e., augmenting the number of allowed steps.

INFERENCEAND

FREQUENCY

IDENTIFICATION

271

Now, if (A) happens first then we set J.(k, + 2) = 1 I (~~,(~)(k, + 2) andswap r and 1, and go to LOOP in order to iterate thefi(k,+k,+5)=0,
construction.
Similarly, if (C,) or (C,) happens first then define L.(k, +2)=zor
f;(k, + 2) = 1 -z, respectively, and set fi(k, + k, + 5) = 0. Perform the swapof r and 1, go to LOOP, and iterate the construction.
In case that (B,) or (B,) first turns out to be fulfilled we define only
L.(k, + k, + 5) = 0 or fi(k, + k, + 5) = 1, respectively. Then we return to
LOOP 1 and iterate the subconstruction.
Let us now discuss what different variants off, may occur. Suppose bothmachines do perform only finitely many mind changes, and for the relevantk the value (Pi,,/,) k (k + 1) is not defined. Therefore, fi is defined everywhere,
but for two arguments. Moreover, M,‘s guesses are almost everywhereequal to M,(ff),which cannot be correct, since cpMlc?,(k + 1) is notdefined. On the other hand, in (B,) and (B, ) machine M, is forced to makea mind change. Because this mind change does not occur, there is a total
extension off, on which M, and M, fail.
Next assume that only M,. performs infinitely many mind changes andagain cpMIcf.;)(k + 1) diverges. Hence fj is defined for all but the argument
k. Let f(x) =f.(x), for all xf k, and set f(k) =z, where z is due to theabove construction. Then the team M,, M, again fails.
Finally, infinitely many swaps of the appropriate 1 and r are performed.
Consequently, fin Iw but neither M, not M, succeeds.
Now we set U = {flf~ iw and f is a total extension of some f.).
Obviously, U $ EX,,,,(2).
The wanted machine M is defined as follows: Let t E TF and x E N.
M(Y) = “Compute f&z)
for all but at most two arguments z 6 x, wheref t(oj is defined as in the above construction. Then test whethert(z) = f&z) for all but at most two arguments z < x. For if not, output(x, 0). Otherwise, output (e, l), where e is a canonical program performing the above construction.”
Q.E.D.
The verification of UE UIF-REX’(M)is left to the reader.
Through explorationof the above results the announced relation
between the two reliable frequency identification modes (i.e., EX and BC)
can now be obtained.
THEOREM

13. Let ‘9.RE {UF, R}. Then
!IJI-REXr,,,(

Proof The simple
containment
by first
U E !I%REX”\EX,,,,(n).

l/n) c YJI-RBC&(

l/n).

inclusion c is obvious. We show the proper
applying Theorem 12. Hence there is a class
Therefore, UE YJI-REX”\W-REX,,,(l/n) since272

KINBER AND ZEUGMANN

EX,,,( l/n) = EX,,,,( l/n) (cf. Pitt, 1989) and !JJI-REXr,,,( l/n) c EXrreq( l/n)
by Corollary 8. Due to Theorem 10 we have U E %R-RBC. Finally,!IR-RBC G 9J&RBCr,,9( l/n) for any number n 2 1.
Q.E.D.
Smith (1982) completely relates the EX and BC team hierarchies,
thereby in particular showing that EXteam(n + l)\BC,,,,(n)# a. Unfortunately, none of his proofs can be applied in our setting. This is caused by
the fact that the capabilities of pluralism are mainly based on non-union
problems. Therefore, at first glance it may seem to be hopeless to transfer
the power of team inference, at least partially, to reliable frequency identification. However, this is a misleading impression. Reliable frequency
inference is closed under union since all the inferrible classes U share thecommon property that functions not contained in U lead to infinite sequences of error messages. Nevertheless, even in the limit it may be undecidable
into which subclass of U the considered function falls. Yet we were
surprised to find the next theorem.
THEOREM

14, TF-REX,,,(l/(n+ l))\BC,,,,(n)# $3 forany numbern> 1.
Proof: Since the following demonstration
is technically involved we
explain the basic ideas in handling the case n = 1. Then we describe indetail how the construction can be generalized, thereby dealing with n = 2.
The rest is straightforward.
We again interprete every partial recursive function as an IIM. In
Barzdin (1974) it has been pointed out that there exists an effective procedure hi [w such that BC((p,) E BC((p,,,,) for all ie N, and (POE R. We set
Mi = qhCij. Next we noneffectively construct classes Ui fulfillingUi$
BC(A4,). Hence we set U= Ui, N U, and obtain that U$ BC. As we shallsee later U will be reliably EX-inferrible on %[F with frequency i. Let ie kJ
be arbitrarily fixed. Ui is uniformly defined as follows:
Fix a strictly monotone function r E [w such that Qj = ‘p,ci, for all j E k,(cf. Blum, 1967). Hence Val r is recursive. Let g E R be chosen such that forallj (cf. e.g., Machtey and Young, 1978) it holds
cPg(j,(O)=iif there is a k with r(k) =j
otherwise(Pg(j)C2)= O.

The definition of (pgcjj p roceeds in stages. At the beginningsuppose ‘pgcjj(z) is already defined for all z d G,~_ 1.

of stage s

INFERENCEAND

FREQUENCY

273

IDENTIFICATIONWe set co = 2, and for s > 1 we define:Stage S. Let r = (pi;:. For ,u = 1, 2, 3, .... dovetail the computationofm, = M,(zOp) and (P,+(cJ- i +p + 1) until a (P,JcJ+, + p + 1) turns out tobe defined. If no such p is found, stage s never terminates.
Now suppose a p has been found such that (P,,,(o~- I + ,U+ l)l.
defineif gSP, <xdp+cT-1
f 0,
%&Ll

+P+

l)+ 13max { cPjCz)lz
<a,-,

if

x=~++.~-,+lif

x=P+cJ..,+~,

Wecp,(~)~ for all+p+1}+1,z<a,-,+11+1‘pg(j,(X) = (undefined,if

x=~+cT-~+2,cp,(~)~ for az<a,-,+p+l
\ 0,

if

.~=fr-~CJs ‘=o.
s-l +p+3
got0 stage s + 1+~+3

end stage s.

By the Recursion Theorem (cf., e.g., Rogers, 1967) a number b can effectively be found such that CJP~,~(~))= qDb. In accordance with the above
construction one gets (~~(0) = i.
Comment.

Later on this will deliver the information

which IIM

has tobe simulated.
Furthermore,
Claim.

(PJ 1) = 6, and (p,(2) = 0.

After stage s has been left, the values (PJz) for z < rrS are all

defined.
We prove the claim inductively. In order to leave stage s a certain ,u has
to be found such that (P,,J~~-, + p + 1) is defined. By construction we get(Pi= 0 for all x E {a,?- r + 1, .... u,~-, +p}, and therefore, from the induction hypothesis, it follows that @Jx) is defined for all x < p + B,+ 1.
Moreover,(P~(D~-, + P + 1) = (P~~(cJ-, + P + 1) + 1, and consequently@,(a,-, +~+l)also converges. Thus the max{rp,C,,(z)/zdo,P,+~+1) =max ( Gh(z)/z 6 cr- 1 + P + 1 > does exist. So we obtain that ‘pb(a,_ 1 + p + 2)
is defined. Finally, cpb(a, - r + p + 3 ) = 0 obviously converges. This proves
the claim.
If stage s is left for all s E N then set U, = {(Pi}. By the claim it follows

274

KINBERANDZEUGMANN

that (PbE [w. On the other hand, there are infinitely many guesses mj of themachine Mi when applied to (Pi satisfying ‘pm, # (Pi. Hence, Mi does notinfer lJi.
Otherwise, stage s is left only finitely many times. Let s’ be the last s forwhich stage s has been successfully finished. Now let r= cpp’. We set
Ui= (rOm}.
In accordance with the construction
one obtains
straightforwardly
that almost all of M;s hypotheses on ~0” fail to becorrect. Again it follows that Ui$ BC(M,).
Please note that the above b can be computed effectively by knowing M,
only. Let U= UiEN Ui. It remains to show that there is an IIM M reliably
EX-identifying
the class U on the set T[F with frequency 4. Let LIZ T[F andnE N. We define:M(f”): = “If n = 0, then output (f(O), 1)”
Compute fromf(0) the appropriate fixpoint 6.
If n = 1, then test whether f(1) = b. For if not, output (LO), andcancel f: Otherwise output (b, 1).
For all n> 1:
If f has already been cancelled in a previous stage then output (n, 0).
Goto (A).
Otherwise, output (f(l), l), if n is even, and (e,, l), if n is odd, wheree, is a canonical program of the following function qn: Let z be thegreatest x Q n for which f(x) # 0. Then definev,(Y)=

f(Y), if ydz
if y>z.
Lo

Before reading the next value off (i.e., f(n + 1)) execute the following
procedure, CANCEL.
CANCEL(1) Test whether there is a number y with O<y <n--2 such that
all the values f(y), f( y + l), f( y + 2) are not equal to zero. If such a y
has been found then cancelf, and return.
(2) Test whether there is a number 0 < y 6 n - 1 such that f( y) # 0
butf(yl)=f(y+l)=O.
If there is such a y then cancelf, and return.
(3) Simulate the computation of ‘pr(i,(x) for all x < n in parallel
exactly n steps. For any ‘pr(i,(x) turning out to be defined test whether
or not cpfc,,(x) =f(x). For if not, cancel f, and return.
(4) Test whether there is a y Q n - 2 such that f(y) # 0 #f( y + 1)
and f( y - 1) = 0 =f( y + 2). If such a y has been detected test whether
0,,,(x) <f(x + 1) for all xd y. In case the inequality is not fulfilled
cancel f and return. Otherwise test whether ‘pr(i,(x) =f(x) for all x < y.

INFERENCEAND

FREQUENCY

IDENTIFICATION

275

Comment.
qfcI ,(x) converges for all x < y since Gjfcl ,(x) <f(x + 1). If
there is an x < y with qfcl ,(x) #f(x) cancel f and return.
end CANCEL(A) Request the next value of,t”
We finish the proof by showing that M behaves as required.
Claim.

M works reliably in the sense of BIF-RI&,,(i).

Let f~ TIF. Suppose M outputs for almost all n hypotheses of the type(i,, 1). We have to prove that there is a particular guess i occurring withfrequency i such that (pi =J: Note that after f has been cancelled once, M
outputs hypotheses of the form (i,, 0) only. Therefore, all guesses must beof the type (i,, 1). Moreover, f will never be cancelled.
Case 1. vrc,,~ !J& Then, in exectution (4) of procedure CANCEL weverify that ‘p/(,) =J To see this assume the converse. Let x be fixed suchthat ‘prci,(x) #f(x). Hence after Q1,-(i,(.~) steps the function f will be cancelled; this is a contradiction. Consequently, for all even n the output of M
is correct.
Case 2. qYof(,,$ If& By construction
there is a k, such thatfor all x 6 k,. Furthermore, qpf(,,(x)~ for all= (prCl,(Xhand'p /(,,(x),Therefore, after max { @,.,,,(x)/x d k,} steps M verifies that
x>k,.
f
‘O
since otherwise f would be cancelled. Now it is easy to see that
@I, =Y(X) must be equal to zero, for all x > k,, since otherwise f will be cancelledagain.
Hence (e,, 1) is a correct guess for n 2 k 0; i.e., the required particular
guess i is e, at least for all n 2 k,. Consequently, for almost all odd n the
output of M is correct. This proves the claim.
The theorem follows since no function from U will be cancelled by M
(cf. the above construction). This completes the proof in the case k= 1.
NOW we consider the case k = 2, thereby learning how the generalization
has to be performed. Any i E N is interpreted as the binary encoding of justtwo numbers, n and rn. We construct, again noneffectively, a class
Ui $ BC<,,,(M,,M,). Without loss of any generality we may assume that
M,, M, E K!. Applying the above construction based on the Recursion
Theorem we define a function qb as follows: ~~(0) = i, qh( 1) = h, (p,(2) = 0,
and for x> 2 we proceed in stages. However, we have to deal with two
IIMs. Similarly to the proof of Theorem 12 this requires a priority regime
Using the parameter k we remember which machine has the greatest
priority. Furthermore,
we are again forced to deal with arguments on
which qb will eventually not be defined. These gaps possibly change fromstage to stage. Hence, in any stage s they are stored in the sets Ci, and Cz.
Finally, we introduce working initial segments T which will be updated at(PbcX)

276

KINBERANDZEUGMANNthe end of each stage. Whenever (Pi,,for x< us, then t(x) = qb(x),where CI~describes the length of the initial segment we are dealing with at
the end of stage s. For x E C, u C, and x d trs, we define r(x) = 0. Insteadof pairs, where the first component was preassigned to fool the machine,
and the second component was used to ensure inferribility in summarizing
the complexities, now we deal with 4-tuples, i.e., one pair for each machine.
Moreover, we can summarize only complexities on those arguments on
which qb has already been defined. We use even numbers to characterize
complexity bounds on all previous arguments and odd numbers in casegaps do actually occur.
Now we describe the construction formally. Let crO= 2 and r(x) = qb(x)for all x d oO.
Sage 1. For p = 1, 2, 3, .... dovetail the computationof r(n, p)=
Mn(POr)and r(m, p)= M,(ruoOP) as well as (~~(~,~)(cr~+ pf 1) andcp,(,, pj(co + P + 3) until (P~(~,Ju~ + CL+ 1) or (P~(~,J~~o + P + 3) turns out
to be defined for some p.
Case 1. A ,u has been found such that cp,(,,,Pj(crO+ p + 1) is discovered
to be defined. Then set C,= (eo+~+3}
and C2= {a,+p+4}
and define(P*(x) =0,

ifo,<xdcr,+~(Pr(n,p)(ao + P + 1) + 1,if

x=~~+p+l

2.max

if

~=a,+~+2if

x=o,+~++.

{@b(z)/z<60+~+1}+2,

1 0,
Furthermore,

let e1 = crO+ p + 5 and k = m. Setz(x) = (P&)7
0,

if
if

x E {O, .... 01 )\Wl”
XEC, UC,.

Cd

got0 Stage 2
Case 2. A p has been found such that (P~(~.~)(o,, +p + 3) turns out tobe defined first. Then set C, = { crO+ p + 1 }, and C, = {cr,, + p + 2) anddefine0,1(Pr(rn,p)(Ucl + P f 3) + 1,

vb(x)=

ifo,<x<a,+p

if~=a,+~+3if

x=o,+p+4

if

x=aO+p++.

2-max{@&)/z4C,uC2,
z<o,+~+l}+l,0,

INFERENCE

Furthermore,AND

let g1 = a,+~+z(x) =(P/l(X),
i 0,

FREQUENCY

IDENTIFICATION

5 and k=n.

Set

if
if

x E { 0, .... 01 j\(GXEC~VC~.

277” Cd
got0 Stage 2

After having described the initialization

we declare stage s for s > 2.

Stage s. For ,u = 1, 2, 3, .... dovetailthe computations
Mn(rKT-lOP), and r(m, ,u) = Mm(r’+‘OP),and try to computer(n, cl) =(a) cprcn,/I) (a, ~ 1 + P + 1) and vp,(,. Jo, - 1 + P + 3 ),t/-3) q,,(y), for any y E C,, where yg = Mk(~-‘P’),
until one value in (u) or (,!I) turns out to be defined.
Case 1. For a y E C, the value cp,,(y) is discovered to be defined. Stopany computation and set
forall(Pbb) = 0x~(C,uC,)\{y,y+l},qP,(y) = CprJY) + 1,

andpb( y + 1) = 2 max {@&2)/z < y } + 2.

Let C, = C2 = 0 and z(x) := (P,,(X) for all x < us- 1. Restart Stage s.
Case 2. For a p the value (P~(~,~)(6, ~ 1 + p + 1) turns out to be defined.

0,1Subcase 2.1.

pb(x) =

k = n. Define
if o,_,<xda,_,+~orxECIuC2

cpr(n,Pj(Os-l+~+l)+l,
2 . max (@Jz)/z

if ~=a,+,+~+1+p+1}+2,

if ~=a,_,+~+2

<g*-,

0,

Furthermore,{oJP1 +p+4},

set o,=o,-,+p++
and
if
if

Moreover,if x=0,-,

+p++.

and

C,={a,-,+~+3),

x E (0, .... %)\(G
XEC~UC~.

C?=

” CJ

let k = m.
got0 Stage s + 1

278

KINBERANDZEUGMANN

Subcase 2.2. k # n. Define0,Pr(n, /Jo,qb(x)=1 + P + 1) + 1,

if

0 .?-.I <xda.%-, +pif

x=0,+,+/L+

1if

x=~~-~

if~=o,~,+p++.

2.max{@,(z)/z$C,uC,,
Z<d,-,+p+l}+l,i 0,
Furthermore, set o,=a,-,+p+5
as C2 := {~~-~+p++}uC~.
T(X) =+p+2

and C, := {a,+,+p+3)uC,
Actualizer as(Pbb),{ 0,

if
if

x E (0, ..,, a,l\(C,XEC,UC~as wellu C,)

and set k = m.
got0 Stage s + 1
Case 3. For a p the value (P,.,~,~~(a,-, + p + 3) turns out to be defined
first.
Subcase 3.1. k=m.
Then we set C,:=C,u(a,-,+p+l]
andC, := C,u (a,-I+p+2},
and define
if0,

fss-l <x<a,-,+p

orxEC,uC2%(m,r&L,+P+3)+
(P&l

=

17

if

x=cJ~,+~++

if

x=oXplif

x=o,_,+p+5.

2 . max { Qh(z)/zGO,-,+p+3}+2,
0,

+p+4

Now let C, = C, = @ and let cs = CJ-, + p + 5. We set r(x) = qb(x) for allx < gs. Finally, let k = n.
got0 Stage s + 1
Subcase 3.2. k#m.
We set C, := C,u {a,-,+p+l}
and C2:=C2 u {a,+ I + p + 2). The definition of qb is continued as follows:0,(Pr(m,p)(fJ-l +P+
qb(x) =

3)+ 12if(rr-,<X<~*-l+II

if.~=a,~,+p++if

x=0,-,+p+4

if~=a,~~,+p+i-.

2 .max {@Jz)/z+! C, u CZ,
z<a,-,+p+3}
0,

+ 1,

INFERENCEAND

FREQUENCY

279

IDENTIFICATIONWe set again CF,= csP, + p + 5 and and actualize r byif
ifz(x) = (P&)7i 0,
Finally,x E (0, .... d\{C,”
XEC~UC~Cd

let k = n.
got0 Stage s + 1

Now we define the wanted class Ui. Suppose that some stage s is neverleft. Then we set Ui = { tas~lOm >, and by the construction it must hold that
Ui $ BCteam(Mn >Mm I*
Assume that stage s is left for any s, and that (Pi E [w.In accordance withour construction this directly yields (Y)~} 4 BC,,,,(M,,M,). Hence we set
ui= hJ.
Finally, suppose stage s is left infinitely often but after a certain stage s0
the value of k remains unchanged. Then we consider the function (Pi. For
x < 2 we set q,(x) = (Pi.
Then cpais also defined in stages, but (Pi always
takes the values of the appropirate part of z, i.e., if Gus,then
cpb(x) = q,(x) for all x 2 ~,~0,and if (Pan, then q,(x) = 0. Let f = ~~‘0, andlet Ui= (fq,(0,+1) (Pa(Oso+2)... }.
Consequently, Uj 4 BC,,,,(M,,M,).
Now we set U= UipN Ui thus obtaining U$ BC,,,,(2).
It remains to show that UE UPRex,,,(1/3)(M),for some IIM A4. Let
f~ ll[F and n E N. We define: M(f”) : = “If n = 0, then output (f(O), 1).
Compute the appropriate fixpoint b.
If n = 1, then test whether f( 1) = b. In case it is not, cancel f and output (1,O). Otherwise output (b, 1).
For all n > 1: output
if

n-Omod3(en, I),

if

nElmod3(4, 11,if

n=2mod3(f(l),

113

until f has been cancelled. Thereby e, is again a canonical program of thefollowing function q,. Let z be the greatest x < n for which f(x) # 0.
Then define q,(y) = f (y) for y d z and q,(y) = 0, if y > Z. Furthermore,
let d, be a program of the function 6, defined as follows:
Let z be the greatest x Q n for which f(x) # 0 and f(x) is even. Thenset
if y<zf(Y)>CP,(Y), if Y >z,

I, =1

where cp, is defined as described above.
643/92/2-IO

280

KINBERANDZEUGMANN

Now it is not at all hard to generalize the procedure CANCEL. Hence
we omit the details.”
Moreover, using similar arguments as we did in the case k = 1 one
straightforwardly proves that M behaves as desired.
Q.E.D.
The latter theorem directly yields infinite hierarchies of reliable frequency
identification
starting from ‘%R-REX and YJI-RBC, respectively, where‘lJk{UF,R}. H owever, until now we knew only a little about uniform
upper limitations concerning the power of reliable frequency inference. On
the other hand, the BC-frequency hierarchy is properly contained in BC*
since IR E BC *. Hence it would be interesting
to know whether
Y.R-RBC,,,(l/n) c ‘9JGRBC*. For %R= [w no new insight can be expected
since any IIM M which BC*-identifies [w obviously works BC*-reliably on
iw, i.e., K! E [W-RBC*. Nevertheless, the case 9R = T[F seems to be promising
if one looks to the next theorem.
THEOREM

15. EX # Tff-RBC*.

Proof: By Corollary
11 one immediately
obtains that UlF-RBC*\
EX # 0. For the other part we show first that lR$U[F-RBC*
and thenapply Proposition 1 to U = (fife !3, qfcO, =S).
Claim.

R $ TlF-RBC*.

Let A4 be any IIM working BC*-reliably on U[F. Furthermore, let (Cam rm
be a recursive enumeration of the functions of finite support defined on
initial segments (0, .... n} of natural numbers. We define a function f,,,, suchthat (fM) $ UIF-RBC*(M)as follows: Search for the least k, satisfyingM( ( ak, ) ) = (i, 0), i.e., after rxk, has been fed to M, A4 produces an error
message. If k, has been found we set f,,,J,u) = clkl(x) for all x E domain c+,.
Let ~zi : = max {x/x E domain Mu,}.
Otherwise fM will be the totally undefined function.
Now suppose such a k, has been found. We iterate the construction.
That means, now search for the least k, satisfying M( (elk, c+,)) = (e, 0).
In case k, has been found we define f,(li+x)= elk.(x), for all
x~domainakx. Otherwise fM will not be defined further. It remains toshow that fMe Iw. Assume that t E UF\R. Therefore, cpi# t for any in N.
Moreover, the IIM M is supposed to work BC*-reliably on UF. Consequently, the sequence M(P)), Erm must contain infinitely many error
messages. Let (M( tq)jG N be the subsequence defined by M(C) = (e,, 0),i.e., the sequence of all guesses with the second component being equal tozero. The finite sequences p,= t(nj+ 1) t(n,+ 2) ... t(n,+ i) can be regarded
as functions of finite support defined on { 0, .... n, + i - nj}. Since all thesefunctions fi, are contained in the enumeration (ai)ie N the search proceduremust terminate infinitely often. Consequently, fM c R.
Q.E.D.

INFERENCEAND

FREQUENCY

281

IDENTIFICATIONThe next theorem states that reliable frequency identification
less powerful than reliable BC*-inference.

is generally

16. T[F-RBCf,,4( l/n) c UlF-RBC* for all n 2 1.

THEOREM

Proof:Let M be an IIM witnessing U E T[F-RBC,,,( l/n). The desired
machine M’ reliably BC*-inferring
U on U[F works as follows: On fe T5
and for k E N first of all M(fk) = (ik, bk) is computed. If b, = 0 then M
outputs (k, 0). Otherwise, M’(fk) = (e,, l), where ek is just the program
which L. Harrington’s machine outputs on f” (cf. Case and Smith, 1983).
Now it can easily be seen that M’ behaves correctly. Details are omitted.
The proper inclusion follows by Theorem 14.
Q.E.D.

Summarizing
hierarchy:EL,&v

the results pointed1)cEX,,,(1/2)

out above, we obtaincEX,,,(l/n)

U!I%REX,,,(

1) c YJI-REX,,,(

n

n

n

l/2) c

BC,,,( l/2)

UIl/n) c ‘$R-RBC*nnl/n) c 1)32-RBC*

c !JJI-RBC,,,(
f-3

c

BC*

. . c 9%REX,,,(

n
c

c

U

Y.J&RBC,,( 1) c !&RBCFreq( l/2) c

BGre,( 1).. cthe following

.. c

B&(

l/n)

c

nl
BC*

However, several questions remain open. We shall discuss them in the final
section of this paper.
3.4. Conclusions

and Open Problems

A new notion of probability inference, as well as a new concept of
reliable identification, was introduced. These new types of inference wererelated to each other as well as to previously defined modes of identification. We characterized one-sided error probabilistic inference to coincidewith reliable frequency identification.
Furthermore,
four new infinite
hierarchies were established. We have compared them one to the other.
However, in performing this comparison we did not fully succeed. It
remained open whether TIF-REX,,& l/n) c aB-REXf,,J l/n) as well as
whether UPRBC,,,(l/n) c IW-RBC,,,,(l/n)
for any n > 2. For n = 1 theresult concerning the EX case can be found in Kinber and Zeugmann(1985). Since our technique of proof does not seem to be extendable to any
n 2 2 we omit the demonstration of Tff-RBC c R-RBC. Moreover, it would
be desirable to characterize reliable frequency identificationin terms ofcomplexity theory. After the pioneering paper of Blum and Blum (1975)

282

KINBERANDZEUGMANN

several identification
types were shown to be complexity theoreticallycharacterizable (cf. Wiehagen, 1978; Zeugmann, 1983). These characterizations generally led to a deeper insight as to what can actually be inferred.
The next open problem concerns reliable BP-inference on Iw and on UiF.
Using ideas from Daley (1983) one easily shows that ‘!JJI-RBC” c!JJI-RBCrres( l/(a + 1)) for any a E N. Nevertheless, the most interestingquestion, whether or not reliable BP-identification
is properly containedin reliable BP+ ‘-identification,
remains open. The problem would be
solved if one obtained the BC-analogue of Theorem 12. We have no idea
at all how to attack this difficult problem. Finally, Chen’s (1981; 1982)
results suggest two interesting open questions. First, Chen (1982) showed
that, with the cost of finitely many anomalies, nearly minimal
size
programs can be inferred without reducing the power of EX*-identification.
It would be interesting
to know whether this result can be extended toreliable EX*-identificationon IR and TLF. Second, Chen (1981) proved that,for every class U E EX”, there is a class U’ 2 U such that U’ E EX”+ ‘\EX”.
Does this theorem remain valid if EX” is replaced by YJGREX”, %R-RBC”,
9JI-REXr,,J l/a), and !JJI-RBC&( l/a), where W E { TIF, lQ}?
SUMMARY

One-Sided Error Probabilistic Inference
and Reliable Frequency Identification
UIF-REX,,&1) c TF-REX,&

l/2)

II

II

UF-REX,&

1) c TF-REX,,,b(nnl

IW-REX,,,,(

1) c IW-REX,,,,(l/Z)

II

II

F&REX,,,(l)ccW-RBC,,,(

v

R-RBC,,,b(c UF-RBC,,,b(IIII1) c UF-RBC,,,(cc UF-REX,&l/n) cnl
cc IW-REX,,,,(l/n)

c

II
c

c

IW-REX,,,(l/n)

t

n
l/2)

c

c

IW-RBC,,,(

l/n)

c

l/n)

c

II
l/2)

c

UI

UF-RBC,,,,(l)T-F-RB&(l/2) c

II
1) c

l/n)
II

F&REX,,,(1/2)

II[W-RBC&(c UF-REX,,&r-lnIW-RBC,,(l)c. c IW-RBC,,,,,(

VIl/2) cc UF-RBC,,,,(l/n)

c

II
l/2)

c

c UIF-RBC,,,,(

l/n)

c

283

INFERENCE AND FREQUENCY IDENTIFICATION

Reliable Inference and Its Relations to Team Identification
%&REX

c

n
Km,(l)!I%REX’== ‘.’ =

c .., c

!BI-REX”

c .,, c

!JJI-RBC’nnl1) c ‘JR-RBC,,,(

”

”

n
c

c‘JJ&RBC*

c %R-RBCr,,(l/(a+ 1)) cc %%RBC*”

II

c%R-REX,,(l/(a+#%R-RBC,,,(1) c !I%RBC,,,(1))~

cm-RBC*#

B&,(l)”

c . . cilR-REX*

9%RBC”#=+’nll/2) c~-REXt,,q(1)c‘J.R-REXr,,,(1/2)c
n

c ...

n

n
c

1))
#

m-REX2%R-RBC,,,(

BC

EX,,,(ll(~+

#
c

c ...

II

E&r,,(@)

n!UI-RBC

EX,,,(a+l)= ... =II#

c9JI-REX’n%,,,(2)IIc

lL%REX”n=

EX,e,(l)c ... c

9%REX’

c ... cBG,m(c . ..c

l/u)

BC*

#
l/2) c .

c !I%RBC,,,(l/( 1 + a)) c

c %I-RBC*ACKNOWLEDGMENT
The authors are very grateful to the reviewer for his careful
helpful commentson the preparationof this paper.
RECEIVED October

21, 1988; FINAL MANUSCRIPT

reading

RECEIVED November

and manyvaluableand7. 1989

REFERENCESANGLUIN,

D., AND SMITH.

C. H. (1983)

Inductive

inference:

Theoryand methods.

Comput.

Surveys 15, 237-269.
ANGLUIN,
D., AND SMITH, C. H. (1987),
Formalinductive“Encyclopediaof Artificial
Intelligence”(S. Shapiro,
Ed.).
Publication,
John Wiley & Sons, New York,BARZDIN, YA. M. (1974), Two theorems on the limiting
synthesis
Algorithms
and ProgramsI” (Ya. M. Barzdin, Ed.), pp. 82-88,
BARZDIN, YA. M. (Ed.) (1974, 1975, 1977) “Theoryof Algorithms
LatvianState University.

inference,
pp.409418,
Vol. 1, Wiley-Interscienceinof functions,in “TheoryofLatvianState University.
and Programs
I, II, III,”

284

KINBERANDZEUGMANN

BLUM. M. (1967) A machine-independent
theoryof the complexityof recursivefunctions,
Assoc. Comput. Mach. 14, 322-336.
BLUM. L., AND BLUM. M. (1975),
Towarda mathematicaltheoryof inductive
inference,
Inform. and Control 28, 122-155.
CASE, J. (1974)
Periodicity
in generationof automata,Math. Systems Theory 8, 15-32.
CASE, J., AND SMITH, C. H. (1983), Comparisonof identification
criteria for machine inductive
inference,
Theorei. Comput. Sci. 25, 193-220.
CHEN, K. J. (1981), Tradeoffs
in machine inductive
inference, Ph. D. thesis, SUNY,
Buffalo,NY.
CHEN, K. J. (1982), Tradeoffs
in the inductive
inference of nearly minimal
size programs,
Inform. and Control 52, 68-86.
DALEY, R. (1983) On the error correcting
power of pluralism
in BC-type
inductive
inference,
Theoret. Comput. Sci. 24, 95-104.
DALEY, R. (1986).
Towards
the developmentof an analysis of learningalgorithms,in“Proceedingsof the International
Workshopof Analogicaland Inductive
Inference,
Wendisch-Rietz,
October
1986” (K. P. Jantke, Ed.), pp. I-18, Lecture Notes in Computer
Science, Vol. 265, Springer-Verlag,
New York.
GOLD, E. M. (1965)
Limiting
recursion,
J. Symbolic Logic 30, 2848.
KINBER, E. B., AND ZEUGMANN,
T. (1985), Inductive
inference of almost everywhere
correct
programsby reliably working
strategies, J. Inform.
Process. Cybernet.
21, 91-100.
KLETTE, R., AND WIEHAGEN, R. (1980), Research in the theory of inductive
inference by GDR
mathematicians-A
survey, Inform.
Sci. 22, 1499169.
MACHTEY,
M.. AND YOUNG,
P. (1978) “An Introduction
to the General
Theoryof Algorithms,”
North-Holland,
New York.
MINICOZZI,
E. (1976), Some naturalpropertiesof strong-identification
in inductive
inference,
Theoret. Comput. Sci. 2, 345-360.
OSHERSON, D., STOB, M., AND WEINSTEIN, S. (1986)“Systems
that Learn.”
MIT
Press,
Cambridge,
MA.
PITT, L. B. (1984)
A characterizationof probabilistic
inference, in “Proceedingsof the 25th
AnnualSymposium
on Foundationsof Computer
Science,
Singer Island,
Florida,”pp. 4855494.
PITT, L. B. (1989)
A characterizationof probabilistic
inference, J. Assoc. Comput. Mach. 36,
383-433.
PODNIEKS, K. M. (1974), Comparing
various concepts of function
prediction
and program
synthesis, I in “Theoryof Algorithms
and Programs”(Ya. M. Barzdin,Ed.), pp. 68-81,
LatvianState University
PODNIEKS, K. M. (1975)
Comparing
various concepts of function
prediction
and program
synthesis, II, in “Theoryof Algorithms
and Programs”(Y. M. Barzdin, Ed.), Latvian State
University.
ROGERS, H., JR. (1967)“Theoryof Recursive
Functionsand Effective
Computability,”
McGraw-Hill,
New York.
SMITH, C. H. (1982), The power of pluralism
for automatic
programsynthesis, Assoc. Comput.
Mach. 29, 11441165.
WIEHAGEN,R. (1978)Characterization
problems
in the theoryof inductive
inference,
New York.
pp. 499-508
in “Lecture
Notes in Computer
Science,” Vol. 62, Springer-Verlag,
ZEUGMANN.
T. (1983)
A posteriori
characterizationsin inductive
inferenceof recursivefunctions.
J. Inform. Process. Cybernet.
19, 559-594.