Some Theorems on Classes of Recursively Enumerable Sets

From MaRDI portal
Publication:3255349





Verff. beweisen eine Reihe von Sätzen über (rekursiv-) aufzählbare (a.), vollständig-aufzählbare (v. a.) und entscheidbare (e.) (- vollständig-rekursive) Klassen von a. Mengen im Sinne von Rice (vgl. auch wegen der Bezeichnungen \textit{H. G. Rice} [Trans. Am. Math. Soc. 74, 358--366 (1953; Zbl 0053.00301)]. Sie geben u. a. mehrere Beweise des Satzes von Rice (loc. cit.), daß es keine nichttriviale e. Klasse gibt, (darunter einen sehr einfachen), sowie verschiedene Verschärfungen dieses Satzes, u. a.: Für jede nichttriviale Klasse \(A\) ist der Unlösbarkeitsgrad im Sinne von Kleene-Post [\textit{S. C. Kleene} and \textit{E. L. Post}, Ann. Math. (2) 59, 379--407 (1954; Zbl 0057.24703)] von \(\theta A\geq 0'\). Weiter bestimmen sie u. a. für die Klasse \(Q\) aller endlichen Mengen den Unlösbarkeitsgrad von \(\theta Q\) zu \(0\). Ferner wird die Ricesche key-array-conjecture über v. a. Klassen bewiesen. Weitere Beweise und Verschärfungen des genannten Satzes von Rice ergeben sich durch Betrachtung von Klassen \(A, B\), für welche \(\theta A\) und \(\theta B\) nicht durch a. Mengen getrennt werden können, sowie durch eine Topologisierung der Klasse \(F\). Ferner werden die Begriffe der Produktivität (vgl. \textit{J. C. E. Dekker}, Trans. Am. Math. Soc. 78, 129--149 (1955; Zbl 0064.01001)]), Kreativität usw. in naheliegender Weise von Mengen auf Klassen übertragen und eine Reihe von Existenzfragen über solche Klassen beantwortet. Hierbei werden u. a. noch folgende interessanten Sätze bewiesen: Der Durchschnitt zweier a. Klassen ist nicht notwendig a. Es gibt abzählbar viele v. a. Klassen \(A\) mit a. Komplement \(F - A\). Die Arbeit enthält auch einige Sätze über Mengen, z. B.: Jede produktive Menge besitzt eine rekursive produktive Funktion (vgl. hierzu Dekker, loc. cit.). Es gibt genau abzählbar viele a., nicht rekursive Mengen, die weder einfach noch semikreativ sind (vgl. Dekker (loc. cit.) und [Proc. Am. Math. Soc. 4, 495--501 (1953; Zbl 0052.25001)]).




Cited in
(34)








This page was built for publication: Some Theorems on Classes of Recursively Enumerable Sets

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