Reduzierbarkeit von Berechenbaren Numerierungen von P1

✍ Scribed by Josef Falkinger

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 553 KB
• Volume: 26
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19800262804

✦ Synopsis

REDUZIERBARKEIT VON BERECHENBAREN NUMERIERUNGEN VON P, von JOSEF FALEINOER in Linz (Osterreich) l) I. Es bezeichne P, die Menge aller n-stelligen partiell rekursiven Funktionen. Wir definieren :

Dies entspricht dem Rocmsschen Konzept der semieffektiven Numerierung (siehe ROGERS [lo]). Die Struktur der Klasse der berechenbaren Numerierungen (BN) beziiglich verschiedener Reduzierbarkeitsrelationen ist Gegenstand zahlreicher rekursionstheoretischer Untersudhungen (siehe ROGERS [lo], FRIEDBERG [5], POUR-EL [9], KHUTORETSKII [8], GOTZE [6, 71, SCHINZEL [IZ], CHYTIL [3, 41). I n dieser Arbeit wird das VerhLltnis der in der Literatur bisher behandelten und einiger dariiber hinaus , ,sinnvoll' ' erscheinenden Reduzierbarkeitsrelationen zueinander untersucht . Speziell beweisen wir, daB die verschiedenen Reduzierbarkeitsbegriffe auf der Klasse BN in einem strengen Sinne nicht ubefeinstimmen. N o t a t i o n . Es bedeutet:

(., . . ., .) irgendeine fix gewahlte rekursive und b-dktive Funktion (,,Paarfunktion") von NJ in N ( j = 1,2, . . . ; welches j zu nehmen ist, wird aus dem Zusammenhang immer klar sein), . . . , .J die zu ( > gehorigen Projektionen auf die erste, zweite, . . ., j-te Komponente, id, die identische Punktion von N in N, ci die Funktion, die N auf die Konstante y abbildet (y E N),

Rj die Menge der j-stelligen (total) rekursiven Funktionen. 1) Diese Arbeit wurde im Rahmen einer Dissertation am Institut fur Mathematik an der Johannes Kepler Universitiit Linz bei 0. Prof. Dr. B. BUCHBERGER angefertigt, dem ich fur zahlreiche wertvolle Anregungen und Hinweise danken mochte.