scientific article; zbMATH DE number 3557764

From MaRDI portal
Publication:4133613





Es sei \(\mathcal E (f)\) die Klasse aller zahlentheoretischer Funktionen, die aus den Identitäten, der Nullfunktion, der Nachfolgerfunktion und der Funktion \(f\) durch Substitution und beschränkte primitive Rekursion erzeugt werden können. Ferner sei \(\mathcal {RA}\) die Klasse aller Funktionen, die aus den Funktionen der Klasse \(\mathcal {A}\) durch einmalige primitive Rekursion und durch Substitution erzeugt werden können. Für jede Funktion \(f\) mit \(\forall k \exists x_k \forall x(x \geq x_k \rightarrow f(x+1) \geq f(x) + k))\), deren Graph in der Grzegorczyk-Klasse \(\mathcal E^0\) liegt, gibt es Funktionen \(\alpha_1,\alpha_2,\dots\) mit 1) \(\mathcal E (\alpha_i) \subset \mathcal E (\alpha_{i+1})\), 2) \(\bigcup_{i=0}^\infty \mathcal E(\alpha_1) \subset \mathcal E(f)\), 3) \(\mathcal {RE}(\alpha_i) = \mathcal E(f)\), 4) für jede nichtfallende Funktion \(g\), deren Graph in \(\mathcal E^0\) liegt und die die Nachfolgerfunktion majorisiert, folgt aus \(\bigcup_{i=0}^\infty \mathcal E(\alpha_i) \subseteq \mathcal E(g)\) stets \(\mathcal E(f)\subset \mathcal E(g)\). Mit anderen Worten: Die Folge \(\{\alpha_i\}\) kann als maximale Folge von Funktionen betrachtet werden, aus denen durch Substitution und einmalige primitive Rekursion die Klasse \(\mathcal E(f)\) erzeugt werden kann. Einige spezielle Aussagen ergeben sich, wenn \(f\) so gewählt wird, daß \(\mathcal E(f) = \mathcal E^{n+1}\). Im Falle \(f=\lambda x(2^x)\) sind die Klassen \(\mathcal E(\alpha_i)\) Raum-Kompliziertheitsklassen für Turingmaschinen (sie entsprechen jedoch nicht den Klassen der Ritchie-Hierarchie, da diese nicht substitutionsabgeschlossen sind).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133613)