Zur Programmkomplexität Rekursiv Aufzählbarer Mengen

✍ Scribed by Hans-Dietrich Hecker

• Book ID: 102485332
• Publisher: John Wiley and Sons
• Year: 1976
• Tongue: English
• Weight: 425 KB
• Volume: 22
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19760220132

✦ Synopsis

Wir definieren nun eine uniforme Numerierung @' = (&Jn , , , , : Fur alle p , x E N berechne man den Wert von q~L(x) durch Anwenden des Algorithmus % auf die Werte 2, vP(O), . . ., vp(f(x)), also sei q~L(x) = %(x, vP(O), . . ., yP(f(z)). Die so definierte Numerierung ist uniform. Sei weiter po E N so, da13

fur alle .I' f(n). Dann ist offenbar p?ho(x) = x s ( x ) fur alle x 5 n. Also folgt S"'(N, n ) 5 c(po), und damit existiert eine Konstante C , so da13 fiir alle n E N gilt: S(N, n) 6

Fur m 2 f(0) sei nun h(m) das groate Y E N, fur das f ( v ) 5 m ist; fiir m < f(0) sei h(m) = 0. Dann ist h ESP. Sei nun D a m gilt zunachst g(f(n)) = t ( n ) -C fur alle n E N. Sei m 2 f ( 0 ) beliebig. Fur geeignetes n gilt dann f(n) m < f ( n + l ) . Dann ist S ( M , m) 2 S ( M , f(n)) 2