Z抗 け
scあ ダ ア,れ ar71.五 θ
な打竹化冴θ 何 筋a″ ″β.̲lraけ ヵ。
必″.』 θ,S.ヱ θ9‑772(rθ 84),｀ON THE NONBOUNDABILITY OF TOTAL EF14「,を.

ECTIVtt OPERATORS

by THOMAS Zコ UGMANN in Berlin(G.D.R.)
IntrodRlctioll

e attelnpt to analyze,in some more detail,the difference between
lll this paper、 ア
tOtal effective Operators(dettned on all general rec■lrsive functions)and general re̲

cursive operators(oomputable operators dofined on allもotal functions). It iS Well̲

knoHア n that llot every total effectivo operator is general recursive;the partial recursiveoperator obtttned by the mEIsttL‐ LACOMB□ ‐SHOコ NFI□ LD theOrem [2]does■ Ot always

map every total functiOn to a total functio■ .Therefore we are particularly interested
in learning,in、 マhiCh Solaso total effective and general recursive opertxtors are extremelydifferont.In this colltent it has boell kno、 vn,that every general recursive operator isbounded(cf.Definttion 4)by a gOneral recursive tlnonotone operator;this resuit、vas

proved by]虹 コYコ m and FIscIIttR[3].Hコ Lmlt[l]ShOWed that an analogous theorem fortotal effective Operators call■ ot be obtained. Tlll■ o、 v it has boon RlnknO、 vn whether
this resRllt can be stengthened or not. In response tO a related q■ lestittn stated by
Hコ LM,ヽve、 vill sho、 7 that in ge■ oral total effective operators are not boundttble evennot in a very weak sense(Cf ThOoroln l and 2).Our theOrems given below will shOw
that in proving theorems concerlaillg oomputable Operators,it doos neithor suffice tOCOllSider Only general recursivo operators, ■or to coAsider only mOnotone or quasi̲
mol■ otone operators.
ヽVe assume the reader is familar with RoGERS[4].Now wo shall give sOme basic■oも ぁtions and defillitiOl■ s、 vhich、vill b6 uSed in this paper.

1.Basic Notations alld Definitions

N=(0,1,2,..,.}de■ Otes the set of all natural numbers P and R mark the classof all partial recursive and general recursive functions, respectively of one vぁ riable
over N. The class ott all general recursive predicates over N is delloted by R。
(ie.

rc Ro iff rc R and rg(ア )室 (0,1))・ An acceptable G6del numbering of P is denotedby?.Theあ ̲th parti働l recursive function is then marked by?′ .The abbreviation a.o/e write
stands for̀̀almOst every、 vhere"and l■ eans for all but initely IIlany valuestヽ ヽi.o. as an abbreviatiOn for ̀̀inFinitely often力 . If O is an operator、 マhiCh maps func̲
tioIIs to functions,we write O(/,″ )七 o denote the valuo of the function O(/)航 point″.

DefinitiOn l A llllapping O:P→ P is an g〃 ccけ ありCO″ ケのサ
θケiff there exists an,cPsuch that if?:c dOIn(0),9(ぢ )iS defined and O(?,)=?。 )The operator O i思 けθ脇7(サ0〃 CCけ ありe prOvided that況

室 dom(0)andマ ,C R implies O(?サ )CR,

Definiも ion 2.A■ Operator D:P→

P is ttο ttOけ 0抑 c if for all functions/,9 C dOm(0):if/(″ )≦ 夕(り 航e.,th仰 0(ア ,″ )≦ 0(ク ,″ )a.e.

170

T王 OMAS Zコ VGMANN

DOfinitiOn 3, A■ Operator D: P→ P is ?竹asガ η00%θ けοttι

if fOr all functions/,7 C dOm(o):if/律 )≦ αし)a.e.,then O1/,″ )≦ Do,り i.0.

DeFinitiOn 4.A■ Operator D is said to be(切 θ傷材グ)う θ物%冴abJc l there exists anoperatOr tty such that

(1)dOm(o)峯 dO・ L(0′ ),(2)I「 Or eVery functiOn/c dOm(D)it hOldS that o(/,″)≦ D′ (/,″ )ae.(i.0̀).

2.Rosults
Now we wll research into thO f0110宙 ng twO problemsi(1)Can every tOtal effoOtive Operator be、 veakly bounded by a tOtal ettective tFnOnO‐to■ o operator?
(2)Is it pOSSible to bOund evelly tota1 0ffective Operator by a tOtar1 6ffeCtive quasi̲

monotOne operator?
In response tO these t、 70 queStions, 、7e COnStrtlct a total effectivo OperatOr、 vhich
neither can be、 veakly bOunded by ally total effective II10■ otOno OperatOr nOr can bO
bounded by a tOtal eゴ fective quasil■ ol10tOne operatOr.
At ttrst、 ve shall shO、マ that the First prOblern can be red■ lced to the second One,Th∞

的mL物 0挽

θ290夕 協けο″ D体 切θα乃物bθ 物角 冴θtt bグ のa%グbθ ￠ι?0あ あ砲

腕θ筋
枠を協物
撒 梅漱歓虎開」
終抗牝あグ α サ
θけのJθ・ 島?物 asづ 物 οttο ′θ%θ サθけαJ θ/rC所 あ θ θク θ″所 ο夕.

Proof. Let O be any arbitrarily fixed total effOctive Operator. suppose that thetotal e鮮 ootive lllonotono operator O weakly bounds thO Operator O, that

dolll(0)匡 dOm(o)alad for every functiOn/c dOIn(0)it h01ds that(A)■leallso(メ ,何 )≦ ⑤(/,″ )itO.

ヽVe define nOw an Operator tt as fol10ws:動(/,何 )=max(0(r,り ,① (メ ,り }fOr all func̲
tions r C P and all何 cN.Then by oonstruction tt is cleallly total efrec胡ャe and sあ tisies。 (r,り ≦ にx/,″ )fOr all:unctiO■ sメ C dOm(0)alld all″ cN.TherefOre,the operator S
bounds the operator D.It relnalns to shO、 7 that'働 is a quasilIIonotone operator.

Let r,夕be two arbitrarily ixed functiOns frOm dOm(8)with/(″O is a mOnotOne operator it h01ds(B))≦ θ(何 )a.e.Since⑤ ,″ )≦ CSl(ク ,伊 )ate・(アBy(A)働 nd by construction of the OperatOr tt we getに x/,″ )=0(/,″S(メ ,″ )≧ 0(r,″ )for all tt and ev‐ ery functiOn r C dom(9)Thus We Obも航 ■ by9(/,り)i.0.働 ndusing(B)=⑤ (r,り ≦ o(θ ,″ )≦ 品 ,″ )itO.and therefOre S is quasimOnotonet□(θNo、 v we give an exalnplo Of a tOtal eftective Operator、
any quasil■ onotone operator.

7hiCh Can■ Ot be bounded byTheOrelm 2,Pあ θ″θ c″ 体偽 α けθサαJ c〃ccけ わθ οPθ ″ぁけθ″ D切 筋 cあ 体 %θ bθ 物%冴 abJθ あ α物
ググ
歩θtta'c//cCサ あC?物 αsあ 物θttο ゎ%c θPι ″筋θ″ 勧・ON THIB NONBOUNDABILITY Oll「 TOTALコ IFコ コCTIVコ OPコ RATORS

Proof.Lot?be a ttXed acceptable G6dei ntmbering of P and set F=(乃converges}・ It iS well̲known that r catt be effectively enumerated.Let乃￨%(ん )。ル 1ル 2,…

be a fixed effective enumeration of F. DeineO(ア ,り171'=the leaSt,Such thaも ち >″ and/(ZJ)=?た y他 ,.

By the TheOrel1 0f RIcコ ,(ぢ ￨?J=メ}iS infinite for any functiOn/c P and thus Opera̲

tor D is clearly total effective.TO see that it satisfies the Other requttements,we prove
the follo、vingLcIBma. あ冴 O bθ けあc abθ りc ttcrづ 物￠冴 θpθ γの歩οヶ.Tttc,ル ″ cり を″グ /物 拘 ぢο物 あ cRけ あθ″cづ sのP″ c冴 づcaけ c /c Ro sttcん け
あのサ/θ ″αJ7″ , D(/,″ )> あ(″ ).
Proof. Letあ be an arbitrarily fixed functiOll from R. Defille the functionあ ′as′fol10wsl 乃′(0)=あ (0)and〃 (何 +1)=あ ′(″ )十 乃(″ +1).By cOnstruction,あ c R and乃(筋 )≦ ″(″ )fOr all β.FurthermOre乃 ′is monotone.To define the wanted predicate/1et【 】=(乃 。 …,乃 丼}and,fOr all″ ,letCけ°キ=￨!1苦 稼チДり樹ゴ
鉢担81d偽楊,・0:携]告01ear]y rg(r)室 (0)1}̀

01ailn l.Tあ c PT2冴 けcttc/づ s pι %θ ″aJ″ cc物 ヶSガ υC.
LOt tt be a fixOd 010ment Of N.It is tO shOw that r(″)is dottned and cOmputable.
cR.Thus rf″ )isぴ foctively′computable ttnd finite.Thellefore,it is decidable ttvhether tt cゴ 密拷(メ ).In the case thatAt rir前 。。mpllteあ ′律 ).ThiS iS ettfectively possible sinceあ"件′(・スP′ (工 ),the prodicate r iS already dOfined at the point密 .Otherwise,by the dettni̲

tion Of」 て it hOlds that?"(″ )00nverges.Thus it is decidable whether?"(″So wO have rC R.
C】)=0 0r nOt.

ぁill1 2.0(r,tal>〃 (″ )″ の材何.

SSncO o is a tota1 0ffectiv0 0perator and/CR。 ,we have D(ナdefil10d fOr all″ .Let O1/,″ )=す・It rehains to show that,>〃)C R Thus O(/,″ )iS(″).SuppOSe the con̲濫脇温沼れダ
4私 品対ヂ勤 )協 ぽ球欝 .瞥 枇鮒陥孟絲側i球・猛路 批士員瑠 兜岳
品鮒稗温,押 靴縄急e解 枇協デ枕)暫 脳n払『針瑞&鮒登ゴ卒
告士
孟i糾 旨
R桃 &協 F蟹 宵
絆8F督 靴轡棚 械耽
紺盤
持3・i品

(冴

(林:操i魯虻〉is an arbitrarily fixed tOtal ettective quasil■ o13otone Operator̀ Thus it h01ds thatthe functiOnあ is general recursive)and fOr any predicato r c Ro wc haveS勧″(r,何 ):≦ito.Therefore,by Ollr lemma,we obtttn that there is a predicate r c Ro with O(′>品 ラ″)≧ 動げ,り i.O ThiS Oompletes the prOOf̀回ド勧(?ち,″))>(ダOorOllary,あ 冴 oあ 弱 あθのあοりc″ 釘ガ%筋 ο?C″ αけθヶ̀?乃 θ%力 乃οttsf Tあ c oPcダ aけ ο″ め 体 拘ひけ
切 での乃物bο 物物 冴ab7θ う α脅ググ サοけのJθ 〃 ccけぢυC ttθ %0け θ%￠ θPcダ αわ ″・Proof, It is an inilnediate consequcllce of TheOron■ l and 2.
I町 ■ally、 ve want to discuss these results,I「 irst,、 ve remark that Obviously there areinfillitely lnany predicates such that for the abOve defined OperatOr O and any total
effoOtive quasimonotone operatOr S it h01ds that O(メ ,り >9(/,り 上o Next,it is easy→￨172

THoMAS Zコ

UGMANNI七o show that anyも otal effective quasil■ o■ otone operator Stt does noも only fail tO bOund

the operator D on R。 ,it fails t?do so On arllbitrarrily large functionst Tle■ ,We wantto point out that TheOreln 2 is even true if、 7e replace the phraseて ̀any total effectiveてquattlnonotone operator Sめ ''byて any total effeotive quasiIItlonotone operatorド 勧relative,oο ttθ け0%θ ″θ
7の あり￠けθRo if there is a function″ cR
to R。 ".(A■ operatorド 働is called 2竹 のsぢ 夕

such that″ (筋 )≧ l fOr貌 1″ ,and for any predicate r c Ro it holds that働 (r,″ )≦ 動(″ ,りi.0.)The proof is,in essential,the same.

夕i.

!

￨￨￨■ofo■ o■ oos[1]Hコ LM,J.P.,On effectively computable operatorsi This Zeitschr.17(1971),231‑244.
[2]KRコ IsISL,G.,D.LA00MBコ ,and J.R.S■ oコ Nコ I13LD,Par位 らl recursive fllnctionals and effectiveoperations.In:Constructivity in Mathemttics(A.Hコ YTIN6,ed.),North‐ Hollalld Publ.COIIlp.,、Amsterda11,1959,pp.290‑297.
[3]MEYl13R,A.,and P.FIscHコR,On COmputational speed‐ up.Ini Conf.Rec.Ninth An■ ual IEEE
Symp.on S、 vitching and Automattt Theory,1968,pp.351‑355.
解岨 RoGコ RS,H.,」 r.,Theory of Recursive Functions and ttffective Computability.McGraw̲Hill

Book Comp.,New York,1967,

Thomas Zeugmam
Sektion IIatllel■ ati止Humboldt‐ Universiも あもDDR‑1086 Berlin

PF.1297
0,D.R.

(Eingegangen aIL 8,April 1982)￨1