Universalität von Berechenbaren Numerierungen von Partiell Rekursiven Funktionen

✍ Scribed by Josef Falkinger

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

✦ Synopsis

UNIVERSALITAT VON BERECHENBAREN NUMERIERUNGEN VON PARTIELL REKURSIVEN FUNKTIONEN von JOSEF FALKINGER in Linz (bterreich),) I. Es bezeichne P, , die Menge aller n-stelligen partiell rekursiven (p. 1.) Funktionen. Wir definieren : F ist berechenbare Numerierung von p . r . Funktionen :-F E P, . Der Begriff der berechenbaren Numerierung von p. r. Funktionen ist ein prazises Substitut fur den Begriff der Programmiersprache mit funktionaler Semantik. Der Zusammenhang mit der Intuition ergibt sich durch folgende Interpretation : fur ,,F(n, x) = y" lies ,,Programm n in der Sprache F , angewandt auf Datum x, liefert Resultat y". (Ax) F ( n , x) ist dann ,,die durch das Programm n berechnete (p. r.) Funktion". F ,,numeriert" also die Menge {(Ax) F(n, x) I n E N} s P,. Eine ausfiihrliche Diskussion der jntuitiven Deutung findet man z. B. in [l] oder [2]. I n [3] wurden verschiedene Reduzierbarkeitsbegriffe auf der Klasse BN der ,,berechenbaren Numerie-

In dieser Arbeit wird die Lage der beziiglich dieser Reduzierbarkeitsrelationen maximalen Elemente in P, geklart. Diese maximalen Elemente konnen auch als verschiedene Universalitatsbegriffe (mit klarer intuitiver Deutung) fur berechenbare Numerierungen von p. r. Funktionen aufgefa13t werden.