Theoretical Computer Science 62 (1988) 289-310
North-Holland

289

ECURSIVE
Thomas ZEUGMANN
Department of Mathematics,

Humboltit University Berlin, 1086 Bedin, German Dem. Rep.

Communicated by R. Karp
Received March 1986
Revised January 1987
Abstract, Problems of the effective synthesis of fastest programs (modulo a recursive factor) forrecursive functions given by input-output examples or an arbitrary program are investigated. In
contrast to the non-existence result proved by Alton (1974, 1976) we show various existence
results. Thereby we deal in detail with the influence of the recursive factor in dependence of theconcrete formalization of a fastest program. In particular, we shall show that, even for functioq
classes containing arbitrarily complex functions, the effective synthesis of fastest programs (module
a simple recursive operator) can be achieved sometimes.

1. Introduction

The present paper deals with the theory of inductive inference, which has been
the subject of monographs (cf. [4]) and several survey papers (cf., e.g., [3,22]), as
well as books (cf., e.g., [26]).
In the following we study the question of effectively synthesizing the fastest
programs (modulo P,recursive factor) for recursive functions. That means, given aclass of functions, we ask whether there is a master program, a so-called “recursive
optimizer”, uniformly synthesizing the fastest programs in an effective way, for any
function contained in the considered function class. If we are given any complexity
measure in the sense of Blum 161,this problem arises naturally since in any Giidel
numbering every recursive function has infinitely many programs and among them
there are arbitrarily “‘bad” ones (i.e., plograms possessing ap extremely large
computational complexity). In [ li, 2, 71 the existence problem for such recursive
optimizers was firstly studied and generally answered in the negative. On the other
hand, the problem of finding grograms having nearly minimal size (i.e., an optimal
program -xith respect to a statical complexity measure) has been the subject ofintensive research too (cf. [4,13]). Recently it has been solved completely by Chen

WI
what we present here is a detailed analysis of the existence problem for recursive
optimizers. In doing so, we first obtain a sharpened version of Theorem 3.1 pointed
out by Alton [l]. Then, in contrast to this negative result, we shall show that, evenfor function classes containing arbitrarily complex functions, the effective synthesis0304-3975/88/$3.50@ 1988, Elsevier Science Publishers B.V. (North-Holland)

290

T. Zeugmannof fastest programs (modulo a simple recursive operator) can be achieved sometimes.
Xoreover, it will be proved that recursive functions possessing an unbounded range
and recursive predicates are extremely different with respect to the existence offastest programs.
Consequently, the capabilities of recursive optimizers working on recursive predicates are much more restricted as those working on arbitrary recursive functions.
In addition, we shall see that the choice of the recursive factor (e.g., recursivefunctions, computable operators,. . . ) has great influence on the power of recursive
optimizers.
In order to make the paper more readable, we structured it as follows: basic
definitions and notations are given in Section 2. Then we present basic results. In
Section 4 the main theorems are given. All proofs are contained in Section 5.

2. Basic definitions aud notations
Unspecified notation follows Rogers [27]. In addition to or in contrast with [27]
we use the following: N = (0,1,2, . . .} deno$ss the set of all natural numbers. By PF
and TF we denote the set of all partial and total functions of one variable over N
respectively.
The class of all partial recursive and recursive functions of one respectively twovariables is denoted by P,R,P2,R' respectively. Let f~ P, then Valf denotes theset (f(x)lx~lQ and f(x) is defined}. &-,,F denotes the set of all f~ R satisfying
Val f c_(0, 1) (recursive predicates). Following [23] we define: a measure of computational complexity is a pair ((9, @) where cp is an acceptable Giidel numbering of P
and @E P2 satisfies Blum’s E <ioms [d].
Instead of Ax&i, X) we often write Qia Let f~ P and i E hJ such that Qi =$ Theni is said to be a program for f: For convenience it is sometimes suitable to identify
a function from W with the sequence of its values; so OilOmdenotes the function $with f(i) = 1 and f(n) = 0 fpr all n # i. Let f e P; then minJ denotes the least i
satisfying Qi =$ A function fe R is called a point of accumulation for a class U G R
iff for all n E N there is a function f ’ E U with f’(x) =f(x) for all x G n, but $’ #fi
The set of all pairs, triples and finite sequences of natural numbers are denoted by
l+J2,NJ and lQ*.By (. , .), c3, and c we denote fixed recursive encodings of N2, f+J3
and
fU*onto N respectively. We write f” instead of c(f(O), . . . , $( n)) for any n E N, fe P,
where f(x) is defined for all x G n.
We say that a sequence (jn)nENof natural numbers converges to a number j iff j, = j
for almost all n. A sequence (j ,,) nENis said to be finitely convergent to a number jiff it converges and j, = j,+, , for any n, implies j, = j for all k 2 n.
The abbreviation a.e. (V”) stands for “almost everywhere” and means “all but
finitely iWUlj?“. We write i.o. as an abbreviation for “infinitely often”. By NUM wedenote the family of function classes U E R being embeddable in recursively
erable function classes (i.e., there is a g E such that i/ c {pg(i,1i E IV} s R).

Ihe power of recursive optimizers

291

For an arbitrary set M we denote the powerset of M by SPM. In the sequel cdenotes a proper set inclusion in contrast to E. Incomparability of sets is denotedby #.
Next we shall consider computable operators. Let ( Fx)xeNbe a canonical enumeration of the finite functions. Following Helm [19] we will distinguish between thefollowing types of computable operators.
A mapping 6 : PF+ PF is called a partial recursive operator iff there exists a
recursively enumerable set W such that, for any y, z E w1,it holds that 6(f)(y) = z
iff there is an x E N such that c&, y, zr E W and F, C$ A partial recursive operator
is said to be general recursive iff TFs domain 0, and fe TF implies 0(f) E TF.
A mapping 0 : P + P is called an e$ective operator iff there is a fun ‘on g E R
such that 6( pi) = pg(i) for all i EN. An effective operator 6 is said to be total e$ective
provided that R s domain 0, and pi E R implies 0( pi) E R.
The set of all general recursive operators and total effective operators is denotedby GRO and TEO respectively. See also [27,32] for more information about these
operators.
If 6 is an operator which maps functions to functions, we write S(f; X) to denotethe vXue of the function S(f) at the argument X. Any computable operator can berealized by a 3-tape Turing machi e T which works as follows: If for an arbitrary
functionfe domain 0, all pairs (x, f(x)), x E domain J are written down on the input
tape of T (repetitions are allowed), then T will write exactly all pairs (x, 6’(fl x))
OF the output tape of T (under unlimited working time).
Let 6 be a computable operator from GRO or TEO. Then, for f~ domain 0,m E IBI,we set: AO(Ct;m) = “the least n such that, for all x s n, f(x) is defined and,for the computation of S(f, m), the Turing machine T only uses the pairs (~,f(x))
with x < n; if such an n does not exist, we set A6’(f, m) = 00”. The functions h E R*
are sometimes regarded as operators of the form Q, (A X) = h (x, f(x)). Furthermore,
for r E R we write 0, to denote the set of all operators 0 E GRO with the property
that there is a Turing machine T realizing the operator 6 such that A6’(f, m) s r(m)holds for all functions fe domain 0 and all m EhJ.
Now we are able to formalize the concept of a fastest program (modulo a recursive
factor). In order to do so, we shall use optimal and weakly optimal programs (cf.
[ 11) and compression indices (cf. [8,30]).
Definition 2.1. Let (Q, @) be a complexity measure, C E TEO, f~ R.
(A) Then i EN is said to be a weakly O-optimal program for f (with respect to(Q, a)) iff(1) Qi=X(2) vaj [Qj =f+ @i( ?I) s 6( *I, n) i.0.).
(B) A!.-0 i E hl is called an 6’.optimalprogram for f (w.r.t. (rp, @)) iff(1) Qi=f,(2) vj [ Qj =f+ @i( F2) s 6( @“, II) a.%].
Then we also say that the function f is (weakly) O-optimal.

T.Zeugmann

292

Definition 2.2. Let (9, @) be a complexity measure, 0 E TEO, f~ R.
(A) Then i E f+Jis said to be an @compression index off (w.r.t. (9, @)) iff(I) Qi =f,I(2)

vj [Qj = f + VTl @i(n) s

6( @“,IllaX{i,j,?I})].

(B) Also i e l$Jis called an absolute 6’0cotnpfessionindex off (W.r.t.
(Q,@)) iff(1) Qi=.&VX [pj(y) = f(y)for all Ys A@(@j, max{ i, x}) + @i(X)s

6( @j,mad&XDIIn this case we also say that the function f is (absolutely) O-compressed.
The definitions given above are slightly different with respect to the demands on
the “almost-all” quantifier. Moreover, an absolute B-compression index is not only
required to satisfy the inequality @i(X)G 6( @j, max{ i, x})for all x and any program
j computing the same function as program i, but also for any program j whichcoincides with program i on a sufficiently large initial segment dependent on i, j
and x (i.e., for all arguments y 6 A6( @j,max{ &x})).
Next we formalize the concept of a recursive optimizer in two different ways. The
first approach is directly based on the concept of finite identification introduced by
Trakhtenbrot/Earzdin [28] and intensively studied by Lindner [24]. The second one
starts from the standardization of programs originally investigated by Kinber [21]and Freivalds/ Wiehagen [ 151.
The main difference between these two concepts is that in the first one only thegraph of the function to be identified is successively available, whereas an arbitraryprogram of the considered function is given as input in the second approach.
nition 2.3. Let U c R. Then U is said to be finitely idenrijfable ( U E FIN) iff
re is a strategy SE P such that S(f”) is defined for all n E IB1,f~ U, and thesequence (SUnkeN finitely converges to a program i off:
By FIN(S) we denote the family ofall those classes U which are finitely identifiableby the strategy S. Note that FIN c EX, where EX denotes the family of all function
classes which can be identified in the limit (cf. the definition before the proof of
Theorem 4.8).
NOW we modify Definition 2.3 by additionally demanding that the identified
programs be fastest ones in the sense of Definitions 2.1 and 2.2.
efisrition 2.4. Let (Q, @) be a complexity measure, 6 E TEO and U c R. Then U
is said to be) finitely weakly Coptimally identifiable ( U E 6’.FINWOPT(~,@)),
finitely O-optimallyidentflable ( U E &FINO~T( Q, @)),

identijuble (UE O-FINCOMP(Q,#)),
ompressed identifiable ( U E &FINACOMP( Q, Q))nte power of recursive optimizers

293

iff there is a strategy S E P such that U E FIN(S) and for every function f~ U thefinitely converges to a number i such thatsequence (Sky(A) i is a weakly -optimal program for J(B) i is an O-optimal program for f;(C) i is an CKcompression index off;(D) i is an absolute O-compression index off respectively.
Definition 2.5. Let U c_R. U is said to be finitely standardizable ( U E FS)
is a function # E P such that
(1) Qi E U implies that t/%(i)is defined and Qi = Q+(i)9(2) Qi = Qj implieS e(i) = e(j),for all Qi, Qj E u
By FS( +) we denote the family of all those classes U which are finitely standardizableby the function q5.
Definition 2.6. Let (Q, @) be a complexity measure, 6 ETEO and U G R Then U
is said to be(A) finitely weoMy O-optimally standardizable ( U E O-FSWOPT( Q, @)),
(B) finitely O-optimally standardizable ( U E &FSOPT(Q, @)),
(C) finitely 6kompressed standardizable ( U E &FSCOMP(Q,@)),(D) finitely absolutely O-compressed sta dardizable ( U E O-FSACO
iff there is a function $+E P such that U E FS( #) and, for every (pi E U,(A) e(i) is a weakly U-optimal program of Qi,(B) f/?(i) is an 6-optimal program of Qi,(C) $(i) is an b-compression index of Qi,(D) e(i) is an absolI:ke O-compression index of Qi respectively.
In the sequel we sinvestigate the relations between the identificand standardization
defined above, as well as the dependencies ofon the complexity measure and th? choice of the operator 0.

3. Basic results
We start with a negative res
Theorem 3.1. Let (Q, @) be a complexity measure, U = {f 1fe R, soJco)=f, f(x)=0a.e.), and let 0 E TEO be arbitrarily jixed. Then there is no function + E P such thatQi E U implies that #(i) is defined and a weakly 6’-optimalprogram for Qie
This theorem is in some sense much stronger than the corresponding non-existence
result in Alton [l]. First, t ere is even a recursive function h E R2 such that every
function from U is absolutely h-compressed (cf. [30]), a
not only h-QPtimalasiSrfunctions froequivalence
it was required in [I]. Second, the program

T. Zeugmannpartially decidable, i.e., U E FIN. So we could prove Alton’s conjecture [l] that theundecidability of programequivalence and the non-existence of rogramoptimizers
are different things. Third, we only require the optimizer 9 to wo on functions
from U and not on all li-optimal functions. Finally, the translated program is only
demanded to be weakly o-optimal for an operator ETEO and not to be weakly
W-optimal for some WE R2.
As we shall see later, the enlargement of admissible operators from functions
he 2 to arbitraryoperators 0 ETEO greatly enlarges the family of function classes
uniformly having weakly &optimal programs.
Now one might expect that there is no hope at all to finitely identify or standardize
fastest programs, but surprisingly we find t& following theorem
Theorem 3.2. mere is a natural complexitymeasure (9, Qz)such that

(1) 6-FINACOMP(~,@) contains a function class of infinite cardirralityfor every
operator6 ETEO.
(2) ~-FINAcoMP((P,B~)~O-FSACOMP(~,~)
jbreuery0~ TEO.
On the other hand, Theorem 3.2 does not hold for arbitrarycomplexity measures.
Let @ denote the identity operator (i.e., @(f) =f for all f E PF). Then we have thistheorem.
rem 3.3. Tntereis a complexity measure (9, #) such that @-Fso~(cp, #) = 0.
Considering Theorems 3.2 and 3.3, the problem arises whether results obtainedfor one complexity measure can be generalized to any measure in a qualitative
sense. This question is partially answered by our next theorem.
m 3.4. Let (1p, @) and (q*, @*)be complexitymeasuresand let 0 E TEO. 7%en
1san operatorO*E GRO such that

FINWOPT(~~,@)E@@-FINWOP@*,#*),
FINO~(P,~)~O*-FINOPT(~*,~*),(3) 00FSWOPT(~,@) s 0*-FSWOPT((P*,@‘),(4) O-Fsopr(++ a) s 0*-Fsopr(llp*, a*).
Unfortunately, till now we have not been able to extend Theorem 3.4 to 8FINCOMP(~,@),~-FINACOMP(~,#),-FscoMP(~,@),and O-FsAcoMP(~,@).
nd, it would be interesting to know whether the recursive translation
ptimal progams into (weakly) B*-optimal programs could be
improved. Several interesting results concerning this problem can be found in [17].
it has been shown there that there are complexity measures (Q,he following properties:
0 and every function feR,function f possesses

77tepower of recursive optimizers

295(2) there is no recursive function translating -optimal programs w.r.t. (4p1a)
into Q-optimal programs w.r.t. (q*, a*) for any function f E R
ry 3.5. Let (p, @) and (Q*, O*) be complexitymeasures, and h E R2. Then
there is a function h*e R2 such thath-FINwo~(q, #)E h”-Fuuwoi=r(4p*,W@)and
the analogous statement is true for h=FINoMq, a), h-Fswo~qv @), and hFsoti~, @).
Next, it can be shown that there is no best operator

ETEQ in the sense that

O*-FSNOPT(Q,9) 2 &FINOPT(Q,0) for every operator t!k TEO (as well as for theother families introduced above) since we have the following result.
Theorem 3.6. L,et (g, @) be a complexitymeasure. men, for euery opera
there is an operatorcY*E TEO, efictiuely constructable,such that
6*-FINO~T(Q,#).

Finally in this section, we want to investigate the question whether the problem~-FINoPT(~~@) # 0 is decidable for a fixed measure (p, @) and any operator
0~ TEO.
Ikorem 3.7. Let (Q, #) be a complexitymeasure. ntere is no algorithmdecidingfor
every operator 6 E TEO whether or not O-FINoPT(Q,#) # 0 iff there exists some
operator0 E TE at all such that0.FINO~T(q, Qb)= 0.

4. Main results
In this section we start by clarifying the relations between finitely optimal identification and finitely optimal standardization. The next theorem was suggested by
Freivalds [ 141.
Theorem 4.1. Let (Q, @) be a complexitymeasure, and 0 E TEO. Then,(1) 6-FINACOW(Q, @) = FIN n 0-FSACOMP(Q,@),(2) 6%FINCOMP(~~@)=FIN~O-FSCOMP(Q,@),-FINOPT(~,@) = FIN n 6(4) &FINwo~T(Q,@)= FINn
Theorem 4.1 actually shows that finite identification of fastest
decomposed. Instead of directly loo
cess, one may finitely synthesizer doing so, one can translate thisNow we point out that the inters
not trivial.

T. Zeugmann

296

Theorem 4.2. (1) There is a class U E FIN which cannot be$nitely weakly O~optimally
identifiedfor every operator 6 E TEO.
(2) For every complexity measure (Q, @) there is a function h E R2 such that
h-FSKoMi’( q, @) - FIN # 8.
The proof of Theorem 4.2 shows that finite standardization of fastest programsof fastest programs due totopological reasons. In the sequel we shall study the influence of the concrete choiceof the set of admissible operators on the capabilities cf the finite identification offastest programs. In order to do this in a very expressive way, we have to distinguisha certain class of complexity measures. we say that a complexity measure (Q, a)satisfies property (+) iff, for all i, x E l+J,it holds that if @i(X) is defined, then@i(X)3 Qi(X). In the following “id” denotes the identity function (i.e., id(x) = x),
and the functions f(x) = id(x) t 1, g(x) = id(x) + x + 1 are denoted by id+ 1 andid + x + 1 respectively.
is generally more powerful than finite identification

Theorem 4.3. Let (Q, @) be a complexity measure satisfying property (-I-). mere is aclass Ucp,@) such that L@@)E 6*-F INACOMP(Q,@) for an operator 0” E &+I, butthere is no operator 0% aid such that U@@‘)E &FINACOMP(Q, a).
Remark. The latter theorem can be generalized up to an infinite hierarchy; i.e., for

any XE N there are a class U and an operator

6” E &+x+1 such that U E

O*-FINACOMP(Q,@),&FINACOMP(Q,a).

0’ E &+x

but

for

every

operatoritfollows

UE

The next theorem particularly shows that even operators from &+I are much
more powerful in generating classes of functions having fastest programs thanrecursive functions from R2.
Theorem 4.4. Let (Q, @) be a complexity measure having property (i-). mere is aclass @@)E 0*-F INACOMP(Q, @) for some operator O* E &+I such that for every
function h E R’ there is afunction from U (Q*@’that is not weaklyh-optimal.In particular,
U(Q*@)eh-FINWOPT(Q, @) for every h E R2.

If we restrict ourselves to O-l ;ralued functions, the situation changes considerably.
As Theorem 4.4 points out, there are classes of functions uniformly having absolute
O*-compression indices for some operator 6* E 0 id+1 , and Containing arbitrarily
complex functions. Thus, U (QS@)
from Theorem 4.4 cannot be contained in NUM.
On the other hand, the next theorem shows that classes of recursive predicatesbeing finitely absolutely O-compressed standardizable are in general contained in
NUM if we restrict ourselves to operators from 0,. Hence such classes of recursive
predicates cannot contain arbitrarily complex functions.

l&e power of recursiveoptimizers

297

Theorem 4.5. Let (q, @) be a complexity measure, t-CR, and let UEOFSACOMP((P,@)n !PR{o,l)for some operator OE 0,. Then there is a function h E R2

such that U E h-FsopT(q, a), and, moreover, U E NUM.
We conjecture that Theorem 4.5 remains valid even if we replace “6 E 0,” by“0 E GRO”. Moreover, it can actually be shown that, for every class U s &) offunctions uniformly having absolute &compression indices for some operator
0 E a,, there is even a function h E R2 such that every function from U is absolutely
h-compressed (cf. [30, Theorem 4.11). Furthermore, it remains open whether inTheorem 4.5 the assertion that U E h-Fsop’r(q, @) can be sharpened to U E
h-FsAcoMP( q, @). Nevertheless, Theorems 4.3-4.5 show that recursive predicatesand arbitrary functions are extremely different with respect to the existence ofabsolute compression indices.
With our next theorem we investigate the capabilities of the finite identification,
respectively finite standardization of h-compression indices. Please note that theproof of the next theorem uses an idea developed by Jantke [20].
Theorem 4.6. There are a complexity measure (Q*, @*) and a function h* E R2 suchthat h*-FINcoMP(q*, @*) # NUM.
Corollary 4.7. Let (Q, @) be a complexity measure. men, for all suficiently large

functions h E R2 it holds that h-Fsoi=r(Q, @) # NUM.
Finally, we compare the capabilities of weakly O-optimal identification and
Q-compressed standardization. This is done by the following theorem.
Theorem 4.8. Let (Q, @) be a complexity measure with property (+). Then there is aclass U c R and an operator d* E Lnid+Isuch that UE O*-FINWOIT(Q,@), but there
is no operator 0~ GRO at all such that U E O-FSCOMP(Q, @).
Itis an open problem whether Theorem 4.8 can be improved. We conjecture that
O-optimal identification cannot be achieved for every operator 0 E GRO.

Moreover, we conjecture that fol -z&rently large operators 0 the following strict
inclusions hold:

5. Proofs

Before proving Theorem 3.1 we point out that total effective and general recursive
operators have the same capabilities in forming classes of functions uniformly having(weakly) optimal programs, although they are extremely d%erent in some properties} for any complexity measure(cf. [ 19,321). For this purpose, let IQ,,@)(Q, @)-

T. Zeugmann

298(up,(9) be a complexity measure and let 6’E TEO.

Then there isan operatot 6% GRO such that O(f, n) = S’(f; n) a.e. for any function f E &(p,ej.

Proposition 5.1; Let

The proof of this proposition was given in [31] (cf. Lemma 5.1).
Corollary 5.2. Let (Q, @) be a complexity measure and let 6 ETEO. Let W s R be aclass such that every function from U is (weakly) 0.optimak! T&enthere is an operator
6’ E GRO such that every function from U is (weakly) Q-optimal.
The proof is an immediate consequence of Proposition 5.1.
Now we are ready to prove Theorem 3.1.
Prod OFT-hmem 3.1. Let c E TEO be arbitrarily fixed. By Proposition 5.1 and [25),there is an operator 6% CR0 satisfying:
0 6’ is monotone (i.e., S, g e R and f (n) s g(n) a.e. implies S’(S, n) g 6’(g, n) a.e.);anda S(f, n) G S’(X n) a.e. for every f E &q,ej.
Let a function s E R be chosen such that {i0””1i E181)= { Qs(i) 1i EN}, and for every
i EN there are infinitely j’s satisfying (Pi = iOao.
We set t(n) = IllaX{a)stij(n ) 1i s n} Obviously, t e R and, for every i EN, @s(i)(n)et(n) a.e.
Suppose there is an optimizer $i E P satisfying: Q~ E U implies that $(i) is definedand a weakly 6”-optimal program for Qie Let z be any fixed program of rl/.
The function g E R is chosen such that, for all i, x EN,i

Qg(i)(x)=0i

1 A Qec i,( X)if x=0,
if x SC@ [a*(i) + I s k, @e(iJ(k) s 0’( t, k)],otherwise.

Due to the Recursion Theorem (cf. [27])9 there is a number b such that pg(b)= (pbWe proceed by showing that the optimizer # fails on b.
Case 1: t,b(b) is not defined. Then we have @J b) > k for all k E N. Hence,# g(b)= (gb= b0”. Consequently, (pb E U By our assumption, it follows that $(b) isdefined, a contradiction.
Case 2: e(b) is dejined. Then there is a b E N such that (pzz(b) + 1 s k for all k 3 k~+
Subcase 2.1: There is ROk 3 b such that @,,,(bI(k) s B’(t, k). Due to our construction, it follows that @,= 60”. Again we get $t&E u According to our assumption,#(b) is a weakly 0’0optimal program for @,. Hence, for almost all i with Q~(~) = b0”
we obtain @#(b)(X)c s’( @s(i),x) i-0. Since the operator 6’ is monotone, we consequently conclude @+(b)(x)s O’(t, x) i.0. This is a contradiction to QcbI( k) >O’(t, k) for all k a kO.
Subcase 2.2: met-e is a k 2 b satisfying @$(bj(k) s @(t, k). Let x’=
pk [ mz(6) + 1 s k, @$(bt, k)]. By our construction, @(b)(x’) is defined. SO
we have Q&c’) = 1 L QG@)(x’). oreover, it again holds that pb(0) = b and Qb(x) = 0
j(

k)

s

f?'(

l%e power of recursive optimizers

299

a.e. Hence, ~6 E U. In accordance with our assumption, e(b) has to be a weakly&optimal program for y)b. Especially the equality &, = p@(b)has to be satisfied,
which is a contradiction. This proves the theorem. Cl
Proof of Theorem 3.2. The wanted complexrty measure is defined as follows: Q isa canonical enumeration of all 3-tape Turing machines with input tape, work tape,and output tape. For all i, X,y we define @(x) = y if and only if the read-write headvisits exactly y cells on the work tape during the computation of the ith machine
when x is given as input, provided that ai
is considered to be undefined if themachine loops on a bounded tape segment (cf. [9]). Now let 3 be the “zero operator”,
i.e., 3(f) = 0” for every function fe PF. Obviously, 3~ GRO. In order to proveassertion (1) of Theorem 3.2 we set U = {Oilo”“1i E IV}.It actually suffices to provethat U E 3-FINACOMP(q, @). Hartmanis and Hopcroft [IS] have shown that there
is a function g E R satisfying qg(i)= OilOoo,and @g(i)(X)= 0 for all i, x E N. Consequently, g(i) is obviously an absolute a_compression index of 0’ 10” (w.r.t. ((p, @)).
The wanted strategy can easily be defined now. We omit details.
Before proving assertion (2) we recall the fact that a class U E FIN cannot possessa point of accumulation (cf. [24]). In the sequel we shall point out that 3’
FSACOMP(~,@) even contains a function class U having a point of accumulation
SE U We set U={O’lO”( i G min,O’PO”}u (0”). Freivalds and Wiehagen [ 151provethat U is of infinite cardinality. Hence 0” is a point of accumulation. Let g E R be
chosen such that {pg<i,1i E IQ0= (0”10” 1i E N} u {0”}, i Z j implies (pS(i)P: ~~(i), and@g(i)(x)= 0 for all i, x E tU Obviously, g(i) is an absolute a-compression index ofpg(i) w.r.t. (bp,@). Before defining the wanted optimizer we note that for all f~ U
and 6 2 minJ it follows that there is an x s 6 with fix) = 1. Therefore we havef = 0” if and only if f(x) = 0 for all x G 6. Let z be the number such that qgcr)= Oao.
Then we set
if pi(X) is defined for all x s i and pi(O) == pi(i) ~0,
if qi( x) is defined for allbg&)= (Pi(X) for all X G i])
xsi and there is a j G i with qi( j) = 1 and for allx G i, x fj
it holds that vi(X) = 0,l[undefinedllotherwise.

In order to verify that U E a-FSACOMP(~, a)( +), let fe U be fixed, and let i and jbe any fixed programs of J We have to show that G(i) and #(j) are defined andequal, and that e(i) is an absolute a-compression index off w.r.t. (q, @).
Case 1: .f=O”. In particular, we get ~~(0) == pi(i) = 0 and qj(O) = 0=
qj( j) = 0. Therefore it follows that e(i) = $(j) = g(z). Due to the definition of thefunction g, we obtain that g(z) is an absolute a-compression index off:case 2: f $ Ooo.Then there exists an n E N such that f= 0” lo?
f~ U, it must hold that n s min,O”lO”.
i, j 2 min,O” 10”. So #(i) and $(j) are defi
l

l

l

l

l

construction. In accordance with the choice of the function g, there is exactly one
k with pg(k)= 0” 10”. Consequently, we get e(i) = $(j) = g(k), and by construction
it follows that g(k) is an absolute g-compression index of O”lO‘? This proves thetheorem. I3
eorem 3.3. The proof of this theorem was given in 1313 (cf. Theorem 4
and Corollary 5, p. 629). l3
Proof of Theorem 3.4. The proof is an immediate consequence of Proposition 5.1
and the proof of Theorem 10 in [31] (cf. pp. 631-632). Cl
Iproof of CoroIIary 3.5 This can be proved analogously to Theorem 3.4. 0
Proof of Theorem 3.6. Let ((p, @) be a comprexity measure. Let 6 E TEO be any
fixed operator. Due to Proposition 5.1 there is an operator 6’ E GRO withS(f, x) = Q’(f, x)a.e. for every fE Z$V,e).

(a)Moreover, by the Speed-up Theorem (cf. [25]), there is a function f~ R which isO’-speedable and which can be effectively found. Hence, the function $ cannot
possess an V-optimal program (in fact, f does not have a weakly U-optimal
program). Thus we get {f )e6"-FINoIc((~,4p),
and consequently, by (a), {f}g
O-FINOPT(~,Cp).
Now let j be any fixed program of the function $ The wanted
operator 6* is defined in two steps. First we set
S,(t, X) = ej(x)+ t(x)for every TVPF and all XE N.

Obviously, 0, E GRO and {f } E6',-FINOFT(
9,G). Then O*( t, X) = max{a’( t, x),6,( t, A’)}for every t E PF and all x E N. In accordance with the latter definition and(cw)it follows
O*( t, X) 2 6( t, x)

for all t E PF and almost all x E tU

Hence, we have ~-FINo~(~,QZ)~B*-FINOPT(~,,)
and since
FINOPT&+,a), the inclusion is proper. Cl{f}EB-

eorem 3.7. This can be proved analogously to Theorem 6 in [3 11. 0
eorem 4.1. We show only assertion (2) here. The other assertions canan analogous way.
(1) Necessity: Let u E &FINCOMP(~~,
G)(S)for some strategy S. Obviously,
U E FIN(S). The wAnted optimizer + is defined as follows: Let i EN. If the sequence(S(&-Y)neN finitely converges to a number j, then we set #(i) = j. Otherwise, J/(i)remains undefined. Now let f c U and let i be any fixeQ program of$ Hence, qi E R
and S(&‘) is defined for all n E k!. Due to the assumption, the sequence (S(P~))~~~
converges to a number j and j is an O-compression index off w.r.t. (y3,@). Moreover,
S(&Q for all n E F+Jand every program 6 of f, we obtain: U E 0-

T&e power of recumiw optimizers

301(2) Suficiency: Let U E FIN(S) and U E 0-FSCOMP(~,@)(#). The wanted strategy
s’ satisfying 0 E ~-FHNcoNP(~, )(S’) is defined as follows:S’(f“)=

S(f “)

if n = 0 or n > 0 and n c px [S( f x-1) = S( f “)I,

if n>Oand ~~Ju[S(~“-‘)=S(~“)].
1#(S(f”))
It remains to verify that the strategy S’ satisfies the desired requirements. In orderto do so, let f E U We have to prove that the sequence (S’(f *&,+, finitely converges
to an Q-compression index off w.r.t. (p, rP). Since f 6 U, it follows that S(f “) isdefined for all n Ef+l.Furthermore, the sequence (S( f n))nGNfinitely converges. Aslong as the function f is not identified by the strategy S, the strategy S’ works exactly
as S, Let now n = px [S(f x-‘) = S(f x)]. Due to the assumption that U E FIN(S),it follows that yes(l~)=$ Consequently, S’(f “) = JI( S( f “)) is defined. Moreover,#(S( f “)) is an (P-compressionindex off w.r.t. (9, @). Since S( f k-*) = S( f k, forall k 3 n, we obtain S’(f k-1) = S’( f k, for all k > n. This proves the theorem. c3
f of Tkorem 4.2. Assertion (1) directly follows from the proof of Theorem 3.1
since the class U={flf E I?, Qf(0) =A f(x) = 0 a.e.} is obviously contained in FIN.
The proof of assefiion (2) is quite similar to that of Theorem 3.2, part (2). The
only difficulty we have to overcome is the generalization to any complexity measure.
For this purpose let (p, @) be an arbitrarily fixed complexity measure, We again
set U = {O’lO”1i S min,O’lO~}u (0”). Since U is infinite, one obtains that O”Ois apoint of accumulation. Therefore, U e FIN.
It remains to show that the,-eis a function h E R2 such that U E h-FSACOMP(q,Q).
Let g E R be chosen such that (v~(~,)i El+J}= {OilO”Ol
i EtU}u {O”),i #j, implies pg(i)fqg(j)r and g(i) zzi for ali i Ef%.In order to define the wanted function h, we proceedand define h(n,m)=t(n)+mfor
as follows: Set t(n) = maX{ @gtij(X) 1i ~n,x~n}
all n, mEIBI.
Claim. Letf E Uand i* = pi [ Q*( ij= f 1. Thetzg( i*) is an absolute h-compressionindex
off w.r.t. ((p, @).

Let x EbJ.We set m = max{g(i*), x}. Consequently, tlz3 g( i*) 3 i* and tn 2 x Dueto the definition of the function t, we obtain:@*(i*)(X)s max{Qi*>( 2) 12 s m}
s RIaX( Gg(ij(Z) 1i G m, 2 G m}

= t(m) = t(max{g(i*), x}).
Let j be any number satisfying f(y) = pj(y) for all y s max{g( P), X) = m.

en we

have

@g(i*)(x)s t(m) s t(m)+ @j(m)= h(m,i.e., g( i*) is an absolute h-compression index off w.r.t. (4p,@). Let z be the number
satisfying v~+)= 0”.

T. Zeugmann

302

Let # be as in the proof of Theorem 3.2. In the proof of Theorem 3.2, it was
shown that U E $FSACOMP(q, @)(#), where 3 was the operator that always returned
the everywhere-zero function. Clearly, U E h-FSACOMP(q, @)(#). Cl
proof of Theorem 4.3. The desired function class is defined as follows: @@)=
{f IKE R pJto, =f; VX@lf(o,(~)~f(x+ 1)). This class was first studied in [ 111. Now
it suffices to set S*(f; x) = max{f(z) ( z G X+ 1). Obviously, 6* E &+I. Due toproperty (+), one directly obtains that f(0) is an absolute d*-compression index off for every function fE U(@). So L@@) can trivially be identified in the sense of
6’*-FINACOMP.
The second part of the proof is only sketched here. All the details can be foundin [30] (cf. Theorem 4.2, p. 587, and Lemma 3.9, pp. 578-579). The main idea of
this proof works as follows. First, one shows that every class of functions uniformly
having absolute Q-compression indices for some operator d E 0, can be identified
by a strategy SE R working consistently on all function f~ R (i.e., U E R-CONS, cf.
[30, pe 562)). Then it can be proved that the class U(‘@) defined above cannot
belong to R-COMS. So we get the result that for every operator 0~ Mid there is afunction from U (*s*)which is not absolutely CT-compressed.This yields the desired
assertion. Cl
Proof of Theorem 4.4. We set again U(*@)= {f 1fE R, qfto)= f, Vx @ftoj(x) sf(x + 1)). So the first part follows from Theorem 4.3.
Note that the second part is proved using an idea and the proof techniques
explained in 1291. This part of the proof is measure-independent. Let (p, @) be
fixed. Let hi& be a canonical enumeration of all finite functions exactly defined at
an initial segment (0,1, . . . , n} of natural numbers. Additionally, let the functionss E R2 and p E R2 be chosen such that
P~(~,,)(Y) = ~0,Y))forevery4 JG and Y,

and(Pp(i.&) =

F,(X)
pi(X)

if xeArg F,,otherwise.

Here s is the s: function of [27] and p is a table patching function.
For the following let h E R2 be arbitrary and, without loss of generality, let h bemonotone in the second argument. Furthermore, let r E R be a strongly monotonefunction satisfying @i= Q~(~)for all is N. Hence Val r is recursive. Moreover, forany j E fQthere is at most one k E N such that r(k) =j. We define C&,o= 0 for all
j E IU For every n, x a 0, and for every j E N we set C{,* = 0 if jti Val r; otherwise(i.e., there is a k E N such that r(k) = j) define(

cj4x = i(n6

XX,

ifZ U

YCX

C-f&,

@i(JC)Qmax

W,
V-=X

@p(s(&j+*),v)(X 1))l

The power of recursive optimizers
Now

let the function g E R be chosen such that, for every n, x, j EN,s( S n)fP*cj,((“, 0)) =0

if there is a k with r(k) = j,otherwise

and, for x > 0,Pg(j)((%X)1=

I + max{&) 1i E &} + ~S~~O~(x- 1)
if there is a k such that r(k) = j,0otherwise.

In accordance with our construction we obtain that v*(j) E P for
every
jEN.Dueto
the Recursion Theorem 1271, there is a number b such that ~~(,(b))= p6. In thesequel we shall prove that pb E R, Axq+,((O,x)) E @‘@’ and that h~q,,((O, x)) is not
weakly h-optimal.
Claim 1. tpPb
E R.
Since ( , .) is a recursive encoding of N2 to N, it suffices to show cpb((n,x)) isdefined for all n, x EN. First we show inductively that ~~((0, x)) is defined for every
x EN. Due to the construction it holds thatl

P&O, 0)) = P&(b))((O, 0)) = s(b, 0).
Since s E R’, we get that pb((O, 0)) is defined. Let now ~~((0, x - 1)) be defined. We
have to show that vb((O, x)) is defined. By construction we obtainpb((O,X)) = 1 +max

Cgi(X)
1i < X, i E U
{

C$),

@i(X)

YCX

G max

h(x,

@p(s(b,i+*).v)( X 1,)+@s(b,O)tx

-

1).

V-=X

By assumption, ~~((0, x - 1)) is defined. Therefore, @~(~& - 1) must be defined.
It remains to show that C$) is computable for all y <x, and that Qjp(s(b,i+l),v)(X)
is defined for every i <X satisfying i E UycX C$) and every v c x. However, forthis purpose it suffices to show that @P~s~~,l~.v~(~),@,,~s~~,2~,v~(~),. . . 9 @p~s~~,xd~)
are defined for every ic x. By the choice of the functions p and s, it is enough toverify that P&X, x)), (P~((x- I, x)), . . . , pb(( 1, x)) are defined. Due to the construction, (pb((x,x)) = I + Qis(b,& - I ) since there is no i with x G i c x.Hence, P&X, x))
is defined. Furthermore, we get ++,((x- 1, x)) = 1 +max{rpi(x) Ix - 1 s i C x and+ @s(~,Oj(~- 1) since the only i satisfying@i(X)s maxvc, h(.~, @p(s(b,i+~),u)(X))}
x:- 1 G ic x is x - 1, and, obviously, x - 1 L Uy.=, CL!‘!,,. Consequently, it suffices(x) is defined for every v c X. Moreover, @P(s(bx~&) isto show that @p(s(b,x),v)(x)
is
defined
for
every
v
c
x.
On
the
other
hand,
defined for every v < x iff 4pP~s~6,X),v~~P~s~b,X~,v~(~)
is defined if ~J(x, x)) is defined, and this has already been proved.
In a completely analogous way, p&c -2, x)), . . . , ~~((1, x)) is shown to be defined
now. Hence, Aqq,((O,x)) E R, and consequently, @s(b,O)
E R.

T.Zeugmann

304

Claim 2. For all x E N the function hng&n, x)) is total.
By constructiorr we get Qb((n, 0)) = ~(6, n), hence it is defined. Furthermore, forn 3 x > 0, in accordance with the construction, it follows that qb((n, x)) =I+ d&-,)(x z l), and thus defined. Now let Anq&, x’)) E R for every x’<x. We
have ;d prove that An(pb((n,x)) E R. As it has already been proved, Qb((n, x)) isdefined for every n 3 x. Now let n < x. In order to verify that Qb((n, x)) is defined,
it suffices to show @p(s(b,i+l),v)(x)is defined for all i <x and L)C x.This can be donein a completely analogous way as in Claim 1. We omit details. Hence, QbE R.
Claim 3. h@,((O, x)) E u(Q,@).

(0) = s( b, 0). Due to our construction it immediFirst we note that %((O, 0)) = (ps(b,o)
ately follows that
4%(b,o)(~+ 1) =

Qb((O,

x+1))>%(b,O)(dforallx E hi*This yields Claim 3.
Finally we show that the following claim holds.
Claim 4. hx%((O, X))

is notweakl’y h-optimal.

Let (pi = hxQb((O, x)). we have to show that there are infinitely many programs z
satisfying Qi = Q= and @i(X)> h (x, d$( x)) a.e. For this purpose, we first note that
r(b)_
C 0,x
10 1, . . . , n - 1) = Czz). Moreover, it is obvious that for every n there is aU, such that if i < n and i E l&N C$?, then i E U,,.=U,C$,“). Thus, for i < n it holds
that i g C$) for y > u,,, So we have shown that C$z) = C$’ for every x > tr,. Dueto the construction one now immediately obtains
Qb((O,x)) = Q&n, x))

for every n and x> 24,.

(1)

Furthermore, we claim that @i(x) > max,,, h(x, @p(s(b,i+l),u)(x))
for
evew
x>
i* In
order to see this, suppose the converse. Hence, there is an x’ such that i E C$).
Consequently,
Q&O, X’)) = d + maX(Qi(X’)@itx’)

1i C x’and i e UycXt C$’ and

s

h(x’,

max

@p(s(b,i+l),v)cx’)))

V-=X’

+

>

@s(b,O)(x’-1)

Qi(X')

which is a contradiction since Qi = hxQb((O, x)). Moreover, (1) yields that there isa Vi such that Q p(s(b,i+l),vi)(x)= Q&o,x))for every xE f% Thus, it suffices to set
Z=p(S(b, i+l), Vi) t o obt ain one desired program z. This process can be iterated
since h is monotone in the second argument, and so one finds infinitely many
programs z with the wanted properties. 0
S. Let (Q, 4p), r E R and 0 E a,, be arbitrarily fixed and suppose
OMP(Q, WWn!+,,}. In [30, Theorem 4.11, it has been shown
then. This result can be obtained by proving that, under the above
is identifiable by a strategy working reliably on the set of all total

The power of recursive optimizers

functions (i.e., U E TF-REL). Then it is not hard to show that TF-RELn 9%&,l) =NUM n 9V$-,,~. (For details the reader is referred to [30, pp. 582-5831.) Since
U E NUM, there is a function g E R, g(i) 2 i for all i such that U c {Pact,1i E N} c R.
We define a function t as follows: for all n E IV: t(n) = max{@g(i,(x) 1is n, x s n}.
As in the proof of Theorem 4.2 it now follows:@gciJ(;X)
G t(max{g(i), X)) for all X E N.

(o )Using the operator 6’~ 0, we define an operator 0* as follows: for all fc TF we set
0*(X X) = max{d(p, X) (p E TF, Vz s r(x) p(z) s max{f(z), x}}.
Obviously we have 6” E 0, and S(f; X) s S*(f; X) for every f~ TF and x EN. Now
we set t* = O*(t) and define h(n, m)= t*(n)+m.
Claim. UE A-Fsopr(p, a)(#).
For this purpose, recall that for every pi E U it holds that e(i) is defined and isan absolute O-compression index of pi. In particular, for everyj satisfying vi = pgci,
we obtain:@*(i)tx)s O(@g(j), max{ @(i), x})

for all x E l@J.

(P)

Using (0~)and the properties of the operator 0” we get from (B):@$(i)tx)s 6*(@g(j)9 max{+( i), x}) s O*( t, x) = t*(x)

a.e.

(Y)

Let k be any program of pi. By (y) it follows@e(i)(x) s t*(x) s t*(x) + @k(x) = h(x, @k(x))

a.e.

Thus q(i) is an h-optimal program for vi. This proves the theorem.

0

Before proving Theorem 4.6 we quote the Operator Recursion Theorem discovered
by Case [lo].

Operator Recursion Theorem. Let 0 be an efictive operator. Then there is a stricfly
increasing function t E R such that O(t, (i, x)) = cp,&) for all i, x E N.
roof 06. (1) NUM - h*-FINcow((p*, @*) # 8 directly follows fromcore‘.he proof of Theorem 3.1, independently of the complexity measure (q*, a*) and
h*e R2.
(2)There are a complexity measure (Q*, @*) and a function ‘11”E
h*-FINcow(q*,@*) - NUM Z (b.

T. Zeugmann

306

Let (Q, @) be any fixed complexity measure. We set Q* = Q. Furthermore, we
define an operator 0 as follows:
if x=0,@i(X)+Qi(X)+t(i)+l ifx>Ot(i)00, (k x)) =for all functions t E I? Obviously, 6 is effective. Due to the Operator Recursion
Theorem there is a strictly increasing function t* E R such that6( t”, (4 X)) = Q,*(i)(X) for every i, x E IW.
Since the function t* is strictly increasing, we have that Val t* is recursive. Now
we are ready to define @*: for every j and x we set
0

@i(X)

@y-(x) =@j(x)if j E Val t*, x = 0,
if jEVa1 t*, j= t*(i), X>O,otherwise.

Claim 1. (Q*, @*) is ix complexity measure.
Case 1: j e Val t*. Due to the construction it holds th:- Ipi*= @j. So we have
Arg QF= Arg Q~= Arg Gj = Arg @T, and, obviously, @$(x)= y is recursive.
Case 2: j E Val t*. Then there is exactly one number i such that t*(i) = j. Hence,@q(x) =

if x=0,{ @i(X) if X> 0.
0

On the other hand we haveQ_?(x) = Qt*(i)(x)= S( t*, (i, x)) =if x=0,@i(X)+Qi(X)+t*(i)+l ifx>O.
t*(i)Therefore, Arg Q~* =Arg @F since @T(X)= @i(X) and @i(X) is defined iff Q,(X) is
defined. Moreover, since Val t* is recursive, one directly obtains that the predicate“@F(x) = y” is recursive for all j, x and y. This proves Claim 1.
Now we define the wanted class U@*as follows:
Ua* = {flfE R, f is strictly increasing, Q~(~)=A Vx @T,dj(x)<f(x)}.

Suppose the converse, i.e., there is a function g such that V,+ E {Qgci,1i E N} c R.
Let f(0) = Q*(~)(O),and let f(x) = Q&X) +f(x - 1) for all x > 0. Obviously, f isstrictly increasing. Due to [ 301 (cf. Lemma 3 in the proof of Theorem 4.1, p. 584)
there is a program i such that Qi=f and @i is also strictly increasing. SincerpI*(i,(x)=

I

t*(i)

@i(X)+f(X)+ t*(i)+1

if x = 0,
if X>O,7&e power of recursive optimizers

301

we obtain that q+(i)(0) = t*(i) and that (P,*(~)
is strictly increasing. Furthermore, since@&i)(X)= @i(X)s @i(X)+ Qi(X) + t*(i) + 1= (p,*(i)(X), X > 0
and@$@(i)(O)= 06 t*(i) = O,*fi,(O),it follows that p,*(i)E Ua*.
In accordance with our assumption, there is at least one k such that q,*(i)= qgtk).
On the other hand, we get

Ql+(i)(k) = @itk)+ftk) + t*(i) + lz: Qg(k)tk)9
a ccntradiction. This proves Claim 2.
Claim 3. There is a function h* E R* such that f (0) is an h*-compression index foreoery function $ E U&P.
We define: h*( n, m) = maxi,,,{pi( n) 1@r(n) s m}. According to this definition we
have pi(n) G h*(n, @r(n)) for all i and n a i. Let now f e U,*and let j be any
program of J: We set nz = max{f (0), j, x}. Consequently, m aj, m Z=x. Since thefunction f is strictly increasing and satisfies @&&) s cpf&) for all x e N we obtainand thus f(0)is an h*-compression index of f w.r.t. (Q*, @*). Now let f begiven as input. Then the wanted strategy S outputs f(0).Hence, U.* E
h*-FINCow(q*, @*). q
Proof of Corollary 4.7. The proof is an immediate consequence of Theorem 4.6, thefact that
h-FINconwr( q, @) 5 h-FINow( q, @) G h-Fsow( 9, @),and Theorem 3.3 as well as Theorem 3.1. •1
Before proving Theorem 4.8 we define identification in the limit.
Definition. Let U c R. Then U is called identifiable in the limit if there is a strategy
SE P such that for every function fe U and every n E N the value S( f")is defined
converges in the limit to a number j such that Qj =f:
and the sequence (S(f")),EN
Let EX denote the family of all classes U G R identifiable in the limit. The identification type EX is sometimes also denoted by LIM (e.g., [30,31]) or GN (e.g., [4]).

feR,Q~(~,=f, @j-to,(x)S f (x + 1) i.o.}.
Proof of Theorem 4.8. We define: U = {f 1
Then o‘* is exactly the same operator as in the proof of Theorem 4.3. ThenU E 0*-FINWOFT(Q,e)(S), where S is the strategy which, onJ simply outputs f(0).
such that U E OIn order to verify that there is no operator 0 E

T. Zeugmann308

we prove that for every operator 0~ GRO there must be a function from U not
being d-compressed. For this purpose, let us suppose the converse, i.e., there is anoperator 6 such that every function from U has an 0-compression index. In [8] it
has been proved that then U is identifiable in the limit by a strategy working reliably
on I?. On the other hand, let U, = {f Ifc R, f(x) = 0 a.e.}. Obviously, &E NUM,
and hence U, is also contained in EX(S) for a strategy even working reliably on
R Moreover, due to the Union Theorem in [8] it follows that U u U&ZEX. The
proof is finished when we show that there is no strategy S identifying Uu V, inthe limit since this yields a contradiction. This is done by using an idea of Gold[ 161 which has beeu refined by Barzdin [4, Chapter I, pp. 82-881. Nevertheless, theproof might even be shorter by using the techniques of [12].
Suppose, U u rjOe FY(S), whereas, without loss of generality, S E R. Let thefunction r E R be chosen such that @i= qr(i) for all i and r is strictly monotone.
Furthenrre, let the function g E R be chosen such thatiP&j,(O) =if there is an i such that r(i) = j,0 otherwise

and proceed as follows: Compute S(908(i,)= nl. Then define pgcj,(2), pgcjj(3). .
to be zero until a kl is found such that either(a) S(C(P&O)80k9) # n1, or
(P)

l

l

,

S(c(~~,j)(o)lok'))fnl*

Since the strategy S is supposed to identify U u V,, either ((w)or (p) must happen.
If (0~)happens, then define pg(j,(l) =0, and if (p) happens, then define qgcj,(I) = 1.
Moreover, we set qg(j)(k, + 2) = qj( kl + 1) if pj( k, + 1) is defined. Otherwise,
qp(j)(kl + 2) remains undefined and pg(j,(X) will be undefined for all x 2 kl + 2. IIvg(j,(kl+ 2) is defined, we proceed as follows: Compute S(qi$f) = n2. DefinePg(j)tkl+3)9- to be zero until a k2 is found such that either(0~) S( c( &-J~OO’~))# n2, orl

WlsWQ$ok9)# n2.

Again, (0~) or (B) must happen since the strategy S is supposed to identify inparticular U,. If (01)happens, then set pgcj,(kl+3) = 0, otherwise define vg(j)(kl+3)=1. Furthermore, we set ~~(j,(k,+3+kt)=cpi(k,+2+k,)if pj(k,+2+kz)
isdefined. Otherwise, qg(j,(x) remains undefined for all x 3 k, + 3 + k2.
By iteration of this construction we define pg(j) completely. Due to the Recursion
Theorem there is a number 6 such that P~,~(~))= pb. By the construction we getpb(O)= 6. Let S(& = n, and k, may satisfy either(0L) S(c(bOOkl)) Z n,, or(p) S(c(610kl)) f n,.
Thus v&)is defined for all x s k, + 1. Furthermore, eb( k, + 1) = (gr& k, + l), hence
defined. So we get

4Db(k*+2)=~r(b)(kl+l)=~~(kl+l)*
Inductively one now easily shows that (PiE U. On the other hand, the strategy S

The power of recursive oplimizers

309

danges its hypothesis infinitely often if ~6 is given as input. This proves thetheorem. 0

References[l] DA. Alton, Non-existence of program optimizers in several abstract settings, J. Cornput. System
Sci. 12 (1976) 368-393.
[2] D.A. Alton and J.L. Lowther, Non-existence of program optimizers in an abstract setting, in: &IC.
Symp- on Programming, Paris, 1974, Lecture Notes in Computer Science 19 (Springer, Berlin, 1974)
96-105.
[3] D. Angluin and C. Smith, A survey of inductive inference: theory and methods, Cornput. Surueys
15 (1983) 237-269.
[4] Ya.M. Bandin, ed., 7Ireov of Algorirhms and Programs; I, II, III (Latvian State University, Riga,
1974, 1975, 1976) (in Russian).
[S] Ya.M. Barxdin, Inductive inference of automata, functions and programs, in: &oc. Internat.
Mathematical Congress ( 1974) 455-460 (in Russian); or Amer. Mrth. Sot. Transl. 109 ( 1977) 107- 122(in English).
(61 M. Blum, Machine independent theory of complexity of recursive functions, J. ACM 14 (1967)
322-336.
[7] M. Blum, On the size of machines, Inform. and Control 11 (1967) 254-265.
[8] L. Blum and M. Blum, Toward a mathematical theory of inductive inference, Inform. and Control
28 (1975) 122- 155.
[9] A. Borodin, Computational cornpIer’:_1and existence of complexity gaps, J. ACM 19 (1972) 158-173.
[lo] J. Case, Periodicity in generation of automata, Math. Systems 7heory 8 (1974) 15-32.
[ 1l] J. Case and S. Ngo-Manguelle, Refinements of inductive inference by popperian machines, Tech.
Rep. 152, Dept. af Computer Science, State University of New York at Buffalo, 1979.
[ 121 J. Case and C. Smith, Comparison of identification criteria for machine inductive inference, 7heoret.
Compur. §ci. 25 (1983) 193-220.
1131 J. Chen, Tradeoffs in the inductive inference of nearly minimal size programs, Inform and Control
52 (1982) 68-86.
[ 141 R.V. Freivalds, Personal communication, 1983.
[ 151 R.V. Freivalds and R. Wiehagen, Inductive inference with additional information, .I. fnform. Process.
and Cybernet. (EIK) 15 (1979) 179-185.
[ 161 E.M. Gold, Language identification in the limit, Inform. and Control 10 (1967) 447-474.
[17] J. Hartmanis, Computational complexity of formal translations, Math. Systems Theory 8 (1975)
156-166.
[18] J. Hartmanis and J.E. Hopcroft, An overview of the theory of computational complexity, .I. ACM
18 (1971) 444-475.

[ 193 J. Helm, On effectively computable operators, 2. Math. Logik Grundlag. Math. 17 (1971) 231-244.
1201 K.P. Jantke, Personal communication, 1985.
[21] E. Kinber, On comparison of limit identification and star.Jardixation of general recursive functions(in Russian), in: Ya.M. Barzdin, ed., -theory of Algorithms and Programs If (Latvian State University,
Riga, 1975) 45-57.
[22] R. Klette and R. Wiehagen, Research in the theory of inductive inference by GDR mathematicians-asurvey, Inform. Sci. 22 (1980) I;9-169.
1231 L.H. Landweber and E.L. Robertson, Recursive properties of abstract complexity classes, J. ACM
19 (1972) 296-308.
[24] R. Lindner, Algorithmische Erkennung, Dissertation B, Friedrich-Schiller-Universidt, Jena, 1972.
[25] A.R. Meyer and P.C. Fischer, On computational speed-up, in: Conf Rec. Ninth Ann. IEEE SWPon Switching and Automata Theory (1968) 351-355.
[26] D. Osherson, M. Stob and S. Weinstein, Systems thar Learn (MIT Press, Cambridge, MA, 1986).
[27] H. Rogers Jr., Theory of Recursive Functions and E$ecrive Computability (McGraw-Hill, New York1967).

310

T. Zeugmann[28] B.A. Trakhtenbrot and Ya.M. Barxdin, Finite Automafa-Behavior and Synthesis, Fundamental
Studies in Computer Science 1 (North-Holland, Amsterdam, 1975).
[29] P. Young, Easy constructions in complexity theory, Rot Amer. Math. Sot. 37 (1973) 555-563.
[30] T. Zeugmann, A posteriori characterizations in inductive inference of recursive functions, .I Illform.
Process and Cybernet. (EZK) 19 (1983) 559-594.
[31] T. Zeugmann, On the synthesis of fastest programs in inductive inference, J. Inform. Process. andCybernet (EZK) 19 (1983) 625-642.
[32] T. Zeugmann, On the nonboundability of total effective operators, 2 Math. Logik Grundlag. Math.
30 (1984) 169-172.