HIERARCHIES OF OPERATORS IN CONSTRUCTIVE METRIC SPACES UDC 518.5

S. V. Pakhomov

Infinite hierarchies of operators in constructive metric spaces (CMS's) are constructed, based on the convergence of an approximate representation of the operators~

Under fairly general restrictions on the CMS (these restrictions

are satisfied by, e.g., a CMS of constructive real numbers and a CMS of general recursive functions) hierarchies

it is shown that these hierarchies

are nondegenerate.

The

constructed are used for studying the complexity of operators on

general recursive functions.

Operators of superposition and bounded and un-

bounded minimization are considered,

along with diverse recursion operators~

i. Introduction In this note we study the complexity of operators in constructive metric spaces CMS's).

(briefly,

The complexity of an operator is given by the complexity of the algorithms approxi-

mating it [i], which, in turn, is understood as the position of these algorithms in some hierarchy of algorithms of a given type. hierarchies of operators in CMS's.

On the basis of this approach we construct infinite

It is proved that these hierarchies are nontrivial

(see

Corollaries 4.1 and 4.2). The terminology and notation from [i] are usedwithout explanation~ , [,~,&

are used as variables for the natural numbers

The variables

k

,

(briefly, NN's).

2. Definitions of the Hierarchies of Operators Let

A={~F,~I~

SAS's). and ~

By

$

and

~} and A = { ~ , ~ , ~ ' ~ ' ~ $

we denote the sets

I

~(N~

be simply approximable CMS's (briefly,

and

s

, respectively.

A

are assumed to be fixed in what follows.

For constructing hierarchies

of operators from

~

and A

classes of algorithms mapping sets of NN's into NN's such that the classes only NN's

E ~ we define classes

but also elements of the sets

to the class

E~

if

we fix a sequence E~ C ~n§

~11

for all ~ .

of Using

~ ~ of algorithms whose input data and values can be not ~

and

5.

k belongs

The SASWs

the class

~"ak§247

An algorithm

A

of type

m E~

contains

the algorithms

',~(ak§ s

Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 60, pp. 183-193, 1976. Results announced May 15, 1975.

0090-4104/80/1405-1547507.50

9 1981 Plenum Publishing Corporation

1547

An algorithm

A with values in

S

(or

5 ) belongs to the class E ~

algorithm that is the superposition of the algorithm algorithm

~

if ~ m

contains the

~.-{ (or, respectively, ~'{) and the

.

We now define the classes of operatos.

All the operators considered in what follows

(unless otherwise stated) are everywhere-defined one-place operators from the CMS { ~ I into the CMS {~,j~}.

We say that the operator ~

~,k)

~

if algorithms

in

belongs to the class

~,k

(to the class

E~ and # i n [ k are realizable that uniformly O-approximate (re-

spectively, 0-approximate) the operator

~

.

Let j~k = ~ , k

and j ~ = - U j ~ , k for all k .

It

follows from [i] that for all r~ and k j~,kc_ j~ %kan d j~k c_.j~.k Since for every

~ the class

E ~

is contained in ~ §

, for all ~

and k

we have the in-

clusions ~,k+~

where ~

is one of the letters

J~, andJy

under certain restrictions on the sets

k+~

(2.1)

The basic result in this note is a proof that

S and

S

and on the sequence of classes E-~ the

inclusions (2.1), except for ~'kC--J~ n'k~ , are strict. We define classes of elements in ~ to the class

C~

if an algorithm

}

and ~

in E~

of type (N-*-S~

all k we have the inequality p(~,~(k~) < g-k. similarly. element

We say that an operator

~(~]

~

We say that an element

The classes

S , S

and the Classes

{~'fl

an algorithm

is a CMS and 0~e~ , we say that ~

~ of type (N-'-~I

if for any ~

in

ck

the

we need the following defi-

is a standard condensation point when

2.-k.

It is assumed henceforth that the sets $ r~o , an algorithm

and ~

is realizable such that for all k we have the inequalities

.<

An NN

~k

are defined

E~

In order to formulate the restrictions on the sets $ If

of elements in ~

belongs to the class ~k.

3. Restrictions on the Sets

nition.

belongs

is realizable such that for

~

belongs to the class

~ in ~

~ of type

and S

satisfy the following conditions.

(N-~SI, and an algorithm ~

of type (SigN)

are

realizable such that: (A) for any element An element

~o

(B) for all ~ is equal to ~

in

$

in ~

in ~ and any NN r~ , if and an algorithm

and any NN's rL

~-~{~,~I

Moreover,

~(~o~)~

and

~ ~(~

then ~ ( ~ ( m ~ 1 >z2 "~~247

(N,N,~5-~S) are realizable such that:

the value of the algorithm ~

~(~,~,t~

and radius ~'~ and is equal to ~

at the

is a Lipschitz coefficient in degree 1 for the

(see [2, p. 206]), and, consequently,

place Lipschitz operator from the CMS {~,~}

1548

~(t~

~ of type

outside the sphere with center

center of this sphere. algorithm

t

the given algorithm is a one-

into the CMS { S , ~ I ;

(C) the element the elements

{o

is a standard condensation

~(~I are standard condensation

It follows from the definition and (~,[,N--~NI , respectively, in ~

points in the CMS {~,P~ 9

of SAS's that algorithms

are realizable

P

and P

of types (~,$ N-~N]

such that for all

~ , 5

in

$

and

~ ~

and any NN rt we have the equivalences P(t

~,~)=0<:> jo(t,5] <

It follows from (C) that an algorithm all

point in the CMS {$~} ~ and for all ,,%

k

~

~-~

(3.1)

~

of type (N-~S)

is realizable

such that for

we have

< In what follows, we denote by NN, and an element in S

the class of k - p l a c e lowing

the

(A) - (C)

restrictions

algorithms

3,3)

[ , a~ , e , P , P , ~ , r~~ Zo

that satisfy

Let us now formulate

2-k~

in E~

certain fixed algorit~hms, an

and (3.1)-(3.3).

on the sequence of classes ~

By

It is assumed that the classes

[~

~k

we denote

satisfy the fol-

conditions :

(D) for any

~

and

for all the algorithms (F) for any ~

m+~ [ k+~

k the class

the class

contains an algorithm that is universal precisely

Ek ;

in the class E~

is closed with respect to the operation of substitution

and the operation of bounded recursion

(the definitions

of these operations are in

[3]); (G) the class ~~

E~

contains

contains

the class

the algorithms

~

of the Grzegorczyk hierarchy,

~ , aS,~,

P , ~.

We mention without proof that the following SAS's of duplexes take the class tions,

that (A) - (0)

LEMMA 3.1.

If for A

and ~ we take r~ [i], and for the class z we

of the Grzegorczyk hierarchy of the class of (r~+~} -fold recursive func-

then we can construct algorithms

Assuming

assertion is true.

or SAS's of generally recursive functions

$~+~

and the class

such that the conditions

(A) - (~)

hold.

hold, we can prove the following lemmas.

For any distinct

NN's

nl

and

~

, we have the equality

~(~(m]]:n~ and the

inequality

LEMMA 3.2. possible

For any elements

to construct an algorithm

~ ,~ ~

of type

[~(m~ = ~ v ~ ( m ~ = t] ; moreover, for any NN NN

~

is realizable

LEMMA 3.3. in ~§

in S

g

, if-~({ ,~ 0

and any NN {N-~-~I

in ~m+1

, then it is

and an NN k such that

and algorithm ~ of the type

($,N-~Sl

in

~~.

V~ an

such that

For any NN

~

it is possible

such that for every algorithm

~

to construct

an algorithm

of type ( ~ - ~ N 1 in

E~

~

an NN ~

of type (N-~N~ is realizable

such that 1549

4. Hierarchy Theorems In this section it is assumed that ( ~ , f }

is a complete CMS, and lira denotes an algo-

rithm for passing to the limit in the CMS { ~ ' ~ I proving that the inclusions (2.1) are strict.

"

Various operators are constructed for

It turns out that these operators can be ob-

tained in a fairly simple way from a certain algorithm.

The construction of this algorithm

and the proof of the properties of it subsequently used are contained in Lemmas 4.1 and 4.2. The formulations of these lemmas are unwieldy in order to free the proofs of the basic theorems from

constructions

LEMMA 4. i.

For any

of a single type. ol and any algorithm ~

to construct an algorithm

~

(4.1) for any algorithm

of type q=

of type (~--~S]

in ~

it is possible

(N~J-~J) such that:

of type

everywhere-defined operator from the CMS

(N--N1,

the algorithm K~(g;(~{~o]~,~), is an

(J ,f I

into the CMS {~,~};

(4.2) for all [ and

(4.3) it is possible to construct an algorithm for all t

~ of type (N,S-"S)

in ~,x , such that

in $ and any NN [ we have the equality

g,t)] :o; (4.4) for any elements

in ~

~ ,

the inequalities p ( ~ ~(k~] > 2-~;t;~

(4.5) for any NN ~

and NN's ~ and ~, if for all

and p(~,[(k~l > ~-ao-g§

and any element ~

k

.

the operator g x r

(r

and A

are first defined.

Recall that if g

is an element in J

g+4)

The algorithm

in 5

[i].

LEMMA 4.2.

Let

~ , ~, cO

1550

9

and all [ , b let

b is an NN, then

~ is defined as follows.

be algorithms of type

constructed according to Lemma 4.1 for the algorithm

gk

having the properties (4.1)-(4.6). Algo-

For all ~ in ~

and

=

belongs to the class

We describe the construction of an algorithm ~ rithms ~

hold, then so does the inequality

in J , if

z

(4.6) for all L and

k not equal to

~

denotes the element ~F(m,

For all m in ~

(N--~NI ~(f{g)) .

and any ~ we set

and let the algorithm ~

be

Suppose that the algorithm

is such that

~(~]=~(~(~(~>,~

for all ~

in ~

Then if

VR[~(~(~]] = &]

and if

~ is

a nondecreasing algorithm, then:

(4.7) the algorithm ~g [g § operator

~

is a regulator of uniform continuity ~or the

;

(4.8) if the algorithms ~

and ~

O-approximate the operator ~ , then for all

k we

have the inequality

The proof of (4.7) is based on the following statements. any NN

'g ,

if

any NN [ , if

~(=~o~ >9(~+{) , then ~(~(~],
For any element Z in J

any elements ~

and ~ in J

and and

? where

L=0 The proof of (4.8) is based on the following property of the operator element ~

in ~

and any NN L , if Z-~[-~-I.~

THEOREM 4.1.

For any

~ Es k

For any

then ~(~(~]~qD([(L~]1 >~ ~-~(L~-4

9 it is possible to construct an operator ~

such that for all k we have that

~

in the class ~ 0

and qD ~j~.,k .

We describe the construction of an operator ~) satisfying the conditions of the theorem. Let ~=~(01

and ~=~(~)

, so that ~ ( ~ , ~ ] ~ 0

according to Lemma 3.2 for the given

~, ~

.

Suppose that the algorithm ~o is constructed

and the NN ~ .

be constructed according to Lemma 4.1 from the algorithm o0. that qD(0$]= ~ ( 0 , ~

for all ~

C__OROLL_______~Y4.1. ~J1

k

For any

we have the strict inclusions

q)

such

~ ~'k C ~ + % k and

\,.~n.,k ~ ~.

~ it is possible to construct an operator ~D in the class

such that for all 6 we have that

An operator

Then the algorithm"

is the desired one.

, ~ , ~

and the inequality

THEOREM 4.2. ~+~'m+~

For any

in ~

Further, let the algorithm

~ E ~

and ~D ~ ~ , ~ .

QD satisfying the conditions of the theorem can be constructed as follows.

Suppose that the algorithm ~

is constructed according to Lemma 4.1 for the algorithm k&$(~l.

Further, suppose that the algorithm 00 and the NN k

are constructed according to Lemma 3.3

for the NN ~ .

in ~

show that ~D

Let ~(~] = ~ ( 0 o ( m ( ~ ]

E .~§

The proof that

for all ~ ~

Using (4.3) and (4.7), we can

satisfies the remaining conditions of the theorem

can be carried out on the basis of (4.6) and (4.8). COROLLARY 4.2.

For any k and [ we have the strict inclusions

and the inequality ~ t \ ~ k #

~

E J~*~

and ~

{.~{k+~

~

The next theorem is proved under the assumption that the classes

~

satisfy in ad-

dition the following condition:

1551

oH) for any in

E~

~ , algorithms

are realizable such that k

lence ~(~,k~ = 0 < = ~ an

~

~(~=k

(N--N1

k of type

is valid.

and

Moreover, for any algorithm

(N,N-~N)

0 of type , k

the equiva-

~ of type

(N--~I

in

is realizable such that ~([~ > ~ (~. E~

to be the classes

hierarchy, then, using [4], we can prove that (H~ THEOREM 4.3.

~.~176176

If IHI

holds, then for any

$~+5

of the Grzegorczyk

holds.

k it is possible to construct an operator

such that for all ~ we have that

Scheme of Proof. in (~]

E ~+~

is strictly increasing and for all ~

We mention that if we take the classes

in

in

~ 6 ~ ~ and ~ ~ ~6,k .

Suppose that ~ and ~ are the algorithms whose existence is asserted

for given k .

Let ~(~=0

and for all ~

let

~(~+4~=]~(~. if ~k~+4 [~(k,nl+41~O]~

[

Since on ~

~(~)$~

for all ~

it can be shown for all ~, [

using the fact that ~(~

, it can be shown that ~ belongs to the class E ~ .

and ~(~(~] = ~

(~(~.

(m(~+{~t).

~(m(~o]+~

~ in

is constructed according to Lemma 4.1 for the algorithm ~ ~]

for all ~.

E ~ such that for all t

Using the algorithm

in $ we have ~(~([,~)~([~t~l=0.

~ and ~

Let

~(t~=~

0-approximate the operator ~, w h e r e ~ is de-

fined by the equalities ~(t,g] = m(t~ + [ * ~ + ~ The proof that ~

By (4.3), it is possible to construct

~ constructed and (4.7), we can show that ~ e ~%~+~. Further,

it can be shown that the algorithms

wise.

From this,

.

Let

an algorithm

that if k ( ~ ~ ~ < ~([ +41 , then ~ ( ~ = [ .

k is strictly increasing, we can get that for all ~ we have ~(~+~] $

Suppose that the algorithm ~ k~

By induction

if p ( i ~ ( ~ ( t ~ ] ] ~ "~~ and #(t,[) = g + R =

other-

satisfies the remaining conditions of the theorem is based on (4..6)

and (4.8). COROLLARY 4.3.

If the conditions of Theorem 4.3 hold, then for all ~ and k we have the

strict inclusion ~'kC ~,k+~ THEOREM 4.4.

and the inequality j~o,o ~ ~o,k+~ \ ~ k # 0 o

For any R

the strict inclusion ~ ' ~ C ~ ~

holds.

In conclusion the author expresses his gratitude to N. K. Kosovskii for attention to this work. APPENDIX In this appendix we apply the results of the note for investigating the complexity of operators over generally recursive functions (briefly, GRF's). notation.

The tuple ~, .,~

then {~}~ denotes the

is denoted by ~ .

If ~

We introduce the following

is the number of an

GRF ~ I ~ .

We describe the construction of the SAS of ~-place GRF's {%, ~ , ~ F ~ , ~ , we denote by ~ algorithm ~ is equal to

The set ~

is the set of all numbersof

is constructed so that for all 0

~ -place GRF,

if the GRF's

{[~

and

[ and~in

{~

~ - p l a c e GRF's.

the set ~ ,

~$}, which The metric

the duplex

are equal, and equal otherwise to

~%([,~) ~-k , where

k is the smallest NN such that NN's ~4,. , ~ ' are realizable that do not exceed k and are such that { g } ~ { ~ 0 ~ { m ~ ( ~ O

1552

.

The algorithm

~

is constructed so that the set &~IN) ,

henceforth denoted by S~ , is a set of "standard" numbers of

~ -place finitary GRF's, i.e.,

GFR's taking nonzero values on a finite collection of tuples of arguments. The algorithm is constructed so that for every g in ~ dard" number of an ~.

~ )

and for every ~

the value

JF~{~m) is a "stan-

~ -place finitary GRF whose values on the tuples

coincide with the values of the GFR

remaining tuples of arguments.

{~,

~

~

(such that &~4

and are equal to zero on all the

Finally, the algorithm

~

is inverse to the algorit~n

~

with respect to the set N . To study the complexity of multiplace operators over GRF's we define also the SAS's of -tuples of GRF's { J ~ spectively, the set ~4,-" , ~ ~Em

~

6TE~ ~am' ~'~'

denoted below by ~ n

&E (~ , which is denoted by SE

such that ~ e

~

(respectively,

k~e$~L)

isdefined so that the distance between the

equal to n~=4 p ~ ( k ~ , ~ the NN ~

)

inverse to the algorithm

~E~

for ~ ~ L $ ~ .

~K m

-tuple ~F~( k~,~, . , ~ k with respect to N

~

(re-

is the set of ~ -tuples of NN~s The metric algorithm

~ -tuples k4~.. ~ ~ and

The value of the algorithm

is equal to the ~

The set

on the ~ - t u p l e

~

~

[~

in

of NN's k ~

Finally, the algorithm

and

~-~K~ is

.

It is not hard to see that every operator over the GRF's is an operator from the SAS ~K~

into the SAS ~

for some

hierarchies ofoperators the class

~

~, ~

For each pair of SAS's

j~,k, ~,~, ~

mulated in Sec. 3.

and ~

Therefore,

, ~

~§

of the Grzegorczyk hierarchy [3].

the sets

~Km and

~

satisfy all the restrictions for-

~,k

and J~'~

of operators over GRF'so

Let us consider the following frequently used operators over GFR's:

tively,

~

~

from the SAS

) for each ~

It can be

the relations proved in Seco 4 between the classes j~,k and

the classes .ff~'~ are valid for the classes

superposition

we define the

just as was done in the given note, assuming that

is taken to be the class

proved that for any ~.~. ,R~

~Km

~,~

in ~

into the SAS ~

the operator of

, and also the operators

that are obtained from the operator

Sm

(respec-

~ by substituting the

NN m in place of the first (respectively, second) argument~ the operator of minimal recursion MR

from the SAS ~,~,z into the SAS ~z

SMR from the SAS ~4,~ into the SAS ~$ in [5]), as well as the operator

and the operator of simple minimal recursion

(see the definition of these operators,

~k

for each k i n $ ~

for example,

obtained from the operator

by substituting the NN k in place of the third argument; the operator of bounded minimization BM from the SAS ~4,z into the SAS ~4 (see the definition in [3]), as well as the operator B ~

foreach ~

in ~

obtainedfrom the operator ~

place of the first argument; subspace of the SAS ~

by substituting the NN ~

finally, the operator of unbounded minimization

9 consisting of the ~ in ~

such that

~

~k~[{~{k,m~=O]

in

from the into the

SAS ~4 " Below, we give without proof statements on the position of the operators described above in the hierarchies i. ~o,o

~

~a,k

All the operators listed in item 3 except for the operator

and to the class 2.

~a

The operator

~ ~

M

belong to the class

for all R 9 belongs to the set ~ o > \ U ~ .

We remark that the theorems in

Sec. 4 do not imply the realizability of an operator belonging to the set

~'~\~. 1553

3.

The operators

$ , MR

,SMR

, M

do not belong to any of the classes

~,k

since

they are not uniformly continuous. 4.

If ~

the operators

and 5~M~

the class ~.0

k

are such that the GRF's

and M ~ k

and

to the class ~ ' ~

{~

belong to the class ~ ,

, and the operator 54m

But if, moreover, ~ is such that the GRF {~}~

~'~ ' then the operators 54m

5.

belong

{~I~

and ~

belongs to

does not belong to the class

do not belong to any of the classes

The operator SMR belongs to the class

then

~'q~-~

~'~

~0,0 .

LITERATURE CITED lo

2. 3. 4.

5.

S. V. Pakhomov, "Approximability of operators in constructive metric spaces,"Zap. Nauch. Sem. Leningr. Otd. Mat. Inst. im. V. A. Steklova Akad. Nauk SSSR, 60, 171-182 (1976). N. A. Shanin, "Constructive real numbers and constructive lunction--~paces," Tr. Mat. Inst. Akad. Nauk SSSR, 6_7, 15-294 (1962). A. Grzegorczyk, "Some classes of recursive functions," Rozpr. Mat., 4, 1-46 (1953). S. V. Pakhomov, "Some properties of the graphs of functions in the Grzegorczyk hierarchy," Zap. Nauchn. Sem. Leningr. Otd. Mat. Inst. im. V. A. Steklova Akad. Nauk SSSR, 32, 105-107 (1972). So V. Pakhomov, "A simple syntactical definition of all the classes in the Grzegorczyk hierarchy," Zap. Nauchn. Sem. Lening. Otd. Mat. Inst. im. V. A. Steklova Akad. Nauk SSSR, 40, 127-130 (1974).

CONTINUITY OF OPERATORS IN SEPARABLE CONSTRUCTIVE METRIC SPACES S. V. Pakhomov

UDC 518.5

We construct an everywhere defined continuous operator on a separable CMS having the following property:

it is not possible to cover the domain of this operator

by denumerably many balls such that the oscillation of the operator in each ball of the covering is less than i.

It was proved in [i] that for any operator

p

from a complete separable constructive

metric space (briefly, CMS) the following statement holds: NN) ~

For any natural number

(briefly,

it is possible to construct an enumerable covering of the domain of this operator by

balls such that the oscillation of P

in each ball of this covering does not exceed

2 -~.

We say that operators satisfying the property described above are strictly continuous. as in [i], it can be shown that every strictly continuous operator is continuous.

Just

In this

note we construct an example of a continuous operator from a separable CMS that is not strictly continuous. Let

~

be a partially recursive function that is universal for all one-place partially

recursive functions.

By Kleene's theorem on normal forms [2], it is possible to construct

primitive recursive functions

V

and T

such that for any NN's

e

and ~

we have the con-

ditional equality Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 60, pp. 194-196, 1976. Results announced October 16, 1975. 1554

0090-4104/80/1405-15.54507.50

9 1981 Plenum Publishing Corporation