Zeilhchr. 1. malh. Logik und Qrundlagen d . Math. Bd. 11, S. 377-378 (1965)

ZUM BEITRAG VON F. SCHWENKEL

,,REKURSIVE WORTFUNKTIONEN flrBER UNENDLICHEN ALPHABETEN" 1)

von ROZSA PBTER in Budapest

Auf dem Internationalen Symposium ,,In€initistische Methoden" in Warschau, September 1959, habe ich iiber die Verallgemeinerung der Theorie der rekursiven Funktionen fiir abstrakte Mengen geeigneter Struktur (beliebiger Machtigkeit) als Definitionsbereiche vorgetragen, und die ausfiihrliche Ausarbeitung dieses Vortrags ist noch im selben Monat zum ,,Acta Math. Hungarica" eingegangen. Natiirlich war meine Absicht nicht, den - damals nooh nicht vorhandenen - Begriff der rekursi- ven Wortfunktion iiber einem endlichen Alphabet auf ein unendliches Alphabet zu iibertragen (wie dies von SCHWENKEL unterstellt wird, wobei auch mein - vom Schema , ,PLL der anderen zitierten Autoren abweichendes - Rekursionsschema, auf das ich hier noch zuriickkommen werde, irrtiimlich mit ,,P' identifiziert wird). Gerade umgekehrt, ich habe einen vie1 allgemeineren Begriff behandelt, manche Ergebnisse in dieser Allgemeinheit erhalten, und die Ergebnisse iiber Wortfunk- tionen (bei beliebigem Alphabet) ergaben sich aus diesen als Spezialfiille. (Den Son- derfall eines hochstens abzahlbaren - also auch dann nicht nur endlichen - Alpha- bets habe ich nur bei einer Verallgemeinerung der KLEENEschen expliziten Form untersucht.) Unter die Zwecke der Aufstellung einer ,,nichtkonstruktiven" Theorie gehort es, da13 sie als Quellen dienen, von welchen man bei speziellen Anwendungen konstruktive Verfahren schopfen kann; wie ich es in einer Reihe der seitdem be- handelten Anwendungen der allgemeinen Theorie auch immer getan habe.

Die Behauptung SCHWENKELS, da13 nach meiner Definition a l le Wortfunktionen uber einem abzahlbaren Alphabet primitiv-rekursiv seien, beruht auf einem Irrtum. Eine beliebig vage definierte Konstante kann natiirlich nicht als primitiv-rekursiv betrachtet werden. Etwas ahnliches ware ja schon in der Zahlentheorie unerlaubt. Zum Beispiel habe ich in meinem Buch ,,Rekursive Funktionen" eine positive reelle Zahl E angegeben, fur welche bei unserem heutigen Wissen nicht entschieden waden kann, ob die Zahl [t] - welche jedenfalls eine Konstante ist - gleich 0 oder 1 ist. Natiirlich diirfte diese Konstante nicht in der Definition einer primitiv-rekursiven Funktion teilnehmen. Auch zur Angabe einer Konstante darf man nur von den Am- gangsfunktionen ausgehend Substitutionen und primitive Rekursionen verwenden.

Es ist wahr, da13 sich die von SCHWENKEL benutzten Konstanten, wie f ( p - l (ai)) (ai E A), auf diese Weise angeben lassen, sobald f eine hinreichend konstruktiv definierte Funktion ist ; und die Primitiv- (nicht nur Allgemein-) Rekursivitat aller hinreichend konstruktiv definierten A-Wortfunktionen ist auch unerwiinscht. Des- halb ist es angebracht, die in meinen Anwendungen stillschweigend immer bestehende, von SCHWENREL nun ausgesprochene ,,Zusatzbedingung" zur Definition hinzu- zunehmen.

l) Diese Zeitschr. 11 (1965), 133-147.

378 ROZSA P ~ T ~ I Z

Trotz der mangelhaften Motivierung ist es immer von Interesse zu untersuchen, wieviel aus der Kompliziertheit des Rekursionsschemas in die Aufnahme geeigneter Ausgangsfunktionen versetzt werden kann, wie dies SCIIWENKEL in dem von ihm behandelten Spezialfall tut. Man sieht leicht, daD seine Ausgangsfunktionen bei abzahlbarem Alphabet die Reduktion des Schemas auf zwei Definitionsgleichungen auch in meinen (den Anspriichen der Anwendungen entsprechend auch in diesem Fall allgemeiner gefal3ten) Definitionen ermoglichen.

Es schliefit sich daran die folgende Erganzung der SCHWENKELsChen Betrach- tungen.

In den Anwendungen ist es erwiinscht, nicht nur die Anfangsstiicke, sondern alle zusammenhiingende Bestandteile eines Wortes als seine Vorgiinger zu betrachten, wobei sich nicht nur der ,,Vorderteil" vt(x), sondern auch der ,,Endteil" et(x) (niichstkleinerer Ordnung) von x als ein unmittelbarer Vorgiinger des Wortes x anbietet, der [mit SCHWENKELS Bezeichnungen: 0 = ,,das leere Wort", l b ( x ) = ,,der letzte Buchstabe von x"] etwa durch die primitive Rekursion

0 fiir vt(x) = 0 et(vt(x)) lb(x) sonst et(x) =

definiert werden kann. Die Vorgiinger vt (2) und et(x) enthalten niimlich insgesamt sh t l iche echten Vorgiinger von x, und sie selber sind in keinem anderen echten Vorganger von x enthalten. Demnach wird in meinem Rekursionsschema ,,R" zur Bestimmung eines Funktionswertes f ( X , y) nicht nur f (X, vt (y)) , sondern auch f (X , et (y)) herangezogen. Definitionen durch ein solches Schema scheinen keine Kopierungen des zahlentheoretischen Falls zu sein, sondern von der Struktur der Worte wesentlich Gebrauch zu machen. Trotzdem kann der Beweis des SCHWENKEL- schen ,,COdierungssatzes" ohne jede Schwierigkeit auch bei der Verwendung des Schemas ,,R" (und iihnlich auch anderer Schemata) durchgefiihrt werden: in der cin-eindeutigen Zuordnung der Worte iiber einem abziihlbaren Alphabet zu den natiirlichen Zahlen findet man leicht die der Funktion et (2) zugeordnete zahlen- theqretische Funktion, und zwar als eine primitiv-rekursive Funktion ; ferner leuch- tet es ein, da13 fiir jedes x $. 0 eine kleinere Zahl zu et(x) als zu x gehort; so fiihrt die ,,Obersetzung" einer Definition nach dem Schema ,,R" ebenfalls zu einer zahlen- theoretischen Wertverlaufsrekursion (durch welche bekanntlich eine primitiv- rekursive zahlentheoretische Funktion definiert wird). Das hat zur Folge, da13 auch bei Verwendung des scheinbar vom zahlentheoretischen Fall wesentlich abweichen- den Schemas ,,R", ein Aufbau der rekursiven Wortfunktionen (uber einem abziihl- baren Alphabet) angegeben werden kann, der sich vollkommen mit dem Aufbau der zahlentheoretischen rekursiven Funktionen deckt .

Es ergibt sich dabei, daB mein allgemeiner gefaStes (und dadurch besser verwend- bares) Schema ,,R" bei hochstens abziihlbarem Alphabet zu keiner anderen Funk- tionenklasse fiihrt als das enger gefal3te Schema ,,P" der anderen Autoren.

(Eingegangen am 11. August 1985)