Zur Komplexitätsmessung Primitiv-Rekursiver Funktionen Über Quotiententermmengen

✍ Scribed by Michael Deutsch

• Publisher: John Wiley and Sons
• Year: 1982
• Tongue: English
• Weight: 799 KB
• Volume: 28
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19820282206

✦ Synopsis

ZUR KOMPLEXZTATSMESSUNG PRIMITIV-REKURSIVER FUNKTIONEN UBER QUOTIENTENTERRIMENGEN von MICHAEL DEUTSCH in Bremen (BRD) Dieser Aufsatz setzt sich zum Ziel, die Gleichwertligkeit verschiedener Ansatze zur Komplexitatsmessung primitiv-rhkursiver Funkt,ionen nach dem Vorbild GRZEGORCZYKS und HEINERMANNS auch fur Quotiententermmengen nachzuweisen. Er schlieljt sich an [2] und [3] an, insbesondere auch hinsichtlich cler gewalilten Bezeichnungen. Fur den Spezialfall der Termmengen sind die Ergebnisse teilweise bereits bekannt (vgl. [4]). y ) , ij, (0 5 ?I v). p ? die cliarakteristische Funktion e des Gleichheitspradikates und die Identitatsfunktionen enthalt und gegeniiber simultanen Einsetzungen abgeschlossen ist.

Fur ?L >= 0 sei R;"Z,'-, die kleinst,e Klasse von Funktionen uber (S, -), die alle Funktionen aus R?x$ -) entlidlt, gegeniiber siinultanen Einsetzungen abgeschlossen ist und f enthalt, falls f durch (S, -)-Rekursion wie in 121, S. 12, aus Funktionen go, . . . , g,,,

, h, aus RYz,-, entsteht. Es sei @" fur n 2 0 die ?a-te GRzEGoRCzYK-Klasse uber N und @f" die Menge der e-stelligen (e 2 0) Funktionen uber ( Z , -), die sich in der Form f(xl, . . . , xe) = c -l 0 g(c(z,), . . ., c(x,)) mit, einer e-st,elligen Funktion g aus an dsrst,ellen lassrn.

Es sei fur R: E X Es sei RYz, -) die kleinste Klasse von Funktionen iiber (2, -), die A%, (0 5 x T ( Z ) = min t f ( y ) (Tiefe von Z),

9 -. c

wobei tf(y) fur y E S die Tiefe des Terms y bezeichnet : tf(*,) := 0 (0 6 x 5 p ) , tf(n,(yl, . . . , yJ) := 1 + max t f ( y , ) (0 5 n 5 2)).

I j L j U ,

Ferner sei fur n 2 0 RM," bzw. RME bzw. RMEp bzw. RMF die Menge der e-stelligen (c 2 0) Funktionen f uber ( 5 , -), fur die es eine Registermaschine R uber (S, -) gibt, so daB sich fur alle :rl, . . ., a, aus ( 5 , w ) f ( x l , . . ., zp) auf R in hochstens f(c(zl), . . . , ~( x , ) ) bzw. f ( d Z ( ~, ) , . . . , abZ(z,)) bzw. f(d'(xl), . . . , nbl'(z,)) bzw. f(T(x1), . . . , T ( x J ) Schritten mit f~ an berechnen lafit, und R: bzw. R: bzw. R;",, bzw. RF sei die kleinste Klasse von Funktionen uber (S, -), die die Funktionen p ) , a, (0 5 ?I 5 v), p und die Identitatsfunktionen enthalt, gegeniiber simultanen Einsetzungen und gegeniiber bezuglich W C-bzw. Kbzw. K'bzw. Tbeschrankter (S, -)-Rekursion abgeschlossen ist,, d. h. mit den Punktionen go, . . . , g,, , h, h,, . . . , h, auch die in [2], S. 12, definierte (Q + 1)-stellige Funktion f enthalt, falls zusatzlich gilt

(0 5 x c(f(z, y)) 5 f * ( C ( R : l ) > . * . > c ( z p ) , C(Y)) bzw. abZ(f(~, y)) 5 f*(abl(xl), . . . , aWx,), WY)) bzw.