INDEXMENGEN REKURSIVER REELLER ZAHLEN
von WOLFGANG SCHADE in Berlin (DDR)')
1. Einl~itiing
Aus der konstruktiven Analysis sind verschiedene Arten der Darstellung rekursiver reeller Zahlen bekannt. Bei der Suche nach Algorithmen, die eine Darstellungsart einer rekursiven reellen Zahl in eine andere umwandeln, stol3t man auf die Tatsache, da13 fur die rat.ionalen Zahlen teilweise andere Algorithmen benotigt werden als fur die rekursiven irrationalen Zahlen (vgl. z. B. KLAUA [l]). Ziel der vorliegenden Veroffentlichung ist es. fur die rekursiven reellen Zahlen in der Darstellung als q-adische Bruche Eumerierungen auf der Grundlage der Kleene-Numerierung der partiell-rekursiven Funktionen einzufiihren und beziiglich dieser Numerierungen die Turing-, m-und 1 -Grade der Indexmengen der rationalen, rekursiven irrationalen und aller rekursiven reellen Zahlen zu bestimmen.
2. Grundlegende Definitionen und Satze
Mit N, Q, I,, R, werden der Reihe nach die Menge der natiirlichen Zahlen, dcr rationalen Zahlen, der rekursiven irrationalen Zahlen und der rekursiven reellen Zahlen bezeichnet. y> 9, JV seien die Menge der einstelligen partiell-rekursiven Funktionen, der einstelligen allgemein-rekursiven Funktionen und der Nullfunktion. Seien ferner rn falls y += 0 und rn * y 5 x < y . (rn + 1) [ %I = { 0 falls y = 0 .2: 2 y die scliwnche Differenz, 0 falls x = 0 -1 sonst , sgn (x) = 1 syn (x). rest (x: y) = x : y -Mit f , g, h . . . . bezeichnen wir einstellige, mit Pl, G', HI, . . . i-stellige partiell-rekursive Funktionen. Speziell ist K L die i-stellige universelle Kleene-Funktion mit der bekannten Rigenschaft KLf1(x0, xl,. . ., xi) = K L ( [ x o , 4, z 2 , . . ., zz). [z, y] ist dabei eine eineindeutige Abbildung von N x N auf N (vgl. MAL'CEV [3]). Den oberen Index i lassen wir fort. wenn keine Zweifel entstehen konnen. Es bezeichne (x, y) eine beliebige rekursive eineindeutige Abbildung von N x N auf N, die man in iiblicher Weise auf n-Tupel ausdehnen kann, und A z ( z ) ~ bezeichne diejenige allgemein-rekursive Umkehrfunktion von Ax, y ( x , y), mittels derer die i-te Komponente erhalten wird. A = B, A B, 5 ,,, B, A 5 ' r B, A und A' bezeichnen Isomorphie, 1-Reduzierbarkeit, m-Reduzierbarkeit, Turing-Reduzierbarkeit, Komplement von A und A-jump (vgl. ROGERS [41). 1) Die Arbeit enthLlt Teile meiner Dissertation; fur die Betreuung und die Hinweise bei der Abfassung der Arbeit danke ich Herrn Professor Dr. GUNTER ASSER.