Some Theorems on Classes of Recursively Enumerable Sets
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)]).
- On a Class of Recursively Enumerable Sets
- A class of recursively enumerable sets
- scientific article; zbMATH DE number 4057498
- scientific article; zbMATH DE number 3997771
- RECURSIVELY ENUMERABLE SETS AND WELL-ORDERING OF THEIR ENUMERATIONS
- Some Characterization of Recursively Enumerable Sets
- scientific article; zbMATH DE number 3857079
- Some lattice-invariant properties of classes of recursively enumerable sets
- Some reducibilities and splittings of recursively enumerable sets
- scientific article; zbMATH DE number 4087651
- Classes of Recursively Enumerable Sets and Their Decision Problems
- Creative sets
- Degrees of Computability
- Effective operations on partial recursive functions
- scientific article; zbMATH DE number 3117565 (Why is no real title available?)
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- scientific article; zbMATH DE number 3048970 (Why is no real title available?)
- scientific article; zbMATH DE number 3073037 (Why is no real title available?)
- On completely recursively enumerable classes and their key arrays
- On definable sets of positive integers
- Productive Sets
- Recursively enumerable sets of positive integers and their decision problems
- The constructivity of maximal dual ideals in certain Boolean algebras
- The divisibility of isols by powers of primes
- The upper semi-lattice of degrees of recursive unsolvability
- Two Notes on Recursively Enumerable Sets
- The basic theory of partial -recursive operators
- Bibliography of John Myhill
- Complexity classes of partial recursive functions
- A restricted analog of the third level of Rice's theorem for semantic classes of sentences
- A representation of recursively enumerable sets through Horn formulas in higher recursion theory
- Effective inseparability in a topological setting
- The enumerability and invariance of complexity classes
- On completely recursively enumerable classes and their key arrays
- scientific article; zbMATH DE number 3849213 (Why is no real title available?)
- scientific article; zbMATH DE number 3857079 (Why is no real title available?)
- scientific article; zbMATH DE number 3878379 (Why is no real title available?)
- scientific article; zbMATH DE number 3924766 (Why is no real title available?)
- scientific article; zbMATH DE number 4091487 (Why is no real title available?)
- Representation theorems for recursively enumerable sets and a conjecture related to Poonen's large subring of Q
- scientific article; zbMATH DE number 3478858 (Why is no real title available?)
- Recursively enumerable sets and degrees
- The classification of statistically recursive sets
- The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete
- A class of enumerable sets
- On a Class of Recursively Enumerable Sets
- Some Characterization of Recursively Enumerable Sets
- On recursive enumerability with finite repetitions
- Termination analysis for offline partial evaluation of a higher order functional language
- RECURSIVELY ENUMERABLE SETS AND WELL-ORDERING OF THEIR ENUMERATIONS
- On the Degrees of Index Sets
- Isomorphism Types of Index Sets of Partial Recursive Functions
- On Creative Sets and Indices of Partial Recursive Functions
- A Theorem on Productive Functions
- A Theorem on Recursively Enumerable Classes and Splinters
- The Family of all Recursively Enumerable Classes of Finite Sets
- Recursively enumerable classes and their application to recursive sequences of formal theories
- A new recursive theorem on \(n\)-extendibility
- On the theory of the PTIME degrees of the recursive sets
- The divisibility of isols by powers of primes
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)