REKURSIVE WORTFUNKTIONEN OBER UNENDLICHEN ALPHABETEN von FRIEDER SCHWENKEL in Tiibingen 1. Wortfunktionen iiber einem endlichen Alphabet Der Begriff der rekursiven Wortfunktion uber einem endlichen Alphabet ist als gesichert anzusehen (ASSER 1960, Hu 1960, VU~KOVI~! 1960, PBTER 1961). Die gebrauchliche Definition lautet : Das (nichtleere) Alphabet A = { a l , a,, . . .} enthalte endlich viele Buchstaben. Die Wortmenge W A uber A bestehe aus allen endlichen Buchstabenketten einschliel3lich des leeren Wortes $3 (der leeren Kette). Die Menge PRA der pimitiv-rekursiven Wortfunktionen uber A sei die kleinste Menge von A-Wortfunktionen (Abbildungen von WA oder kartesischen Produkten davon in WA), welche die Ausgangsfunktionen (1) enthalt und unter den Operatoren der Substitution (2) und primitiven Rekursion ( 3 ) abgeschlossen ist. Au sg a n g sf u n k t i one 11 : das leere Wort P, , aufgefaat als konstante Funktion beliebiger Stellenzahl, die Identitatsfunktion id (2) = x , die Verkettungsfunktionen vki(x) = xui (ai E A), meist einfach als xui geschrieben. S u b s t i t u t i o n s o p e r a t o r e n : 8 k (k = 1 , 2 , . . .), definiert durch f = & ( g , h) mit (2) f (21 3 . .