Variations on promptly simple sets. (English) Zbl 0589.03025
The paper tries to make the role of lowness properties and prompt simplicity in the construction of automorphisms of the lattice of r.e. sets more perspicuous. Two new properties of r.e. sets, namely, the prompt and the low shrinking property, are essential for the present approach. We quote two basic results: a) there exist low sets with the splitting property that are not promptly simple, b) every two low sets with the prompt shrinking property are automorphic in \({\mathcal E}\).
Reviewer: C.Calude
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
Keywords:
prompt shrinking property; lowness properties; prompt simplicity; automorphisms of the lattice of r.e. sets; low shrinking property; low sets; splitting propertyReferences:
| [1] | Recursively enumerable generic sets 47 pp 809– (1982) |
| [2] | Annals of Mathematical Logic 9 pp 307– (1975) |
| [3] | DOI: 10.1090/S0002-9947-1984-0719661-8 · doi:10.1090/S0002-9947-1984-0719661-8 |
| [4] | DOI: 10.1016/0003-4843(82)90016-X · Zbl 0526.03022 · doi:10.1016/0003-4843(82)90016-X |
| [5] | Computational complexity, speedable sets and levelable sets 42 pp 543– (1977) |
| [6] | DOI: 10.1090/S0002-9947-1983-0704618-2 · doi:10.1090/S0002-9947-1983-0704618-2 |
| [7] | DOI: 10.2307/1970842 · Zbl 0253.02040 · doi:10.2307/1970842 |
| [8] | DOI: 10.1016/0168-0072(83)90031-3 · Zbl 0538.03037 · doi:10.1016/0168-0072(83)90031-3 |
| [9] | DOI: 10.1007/BF02760850 · Zbl 0469.03026 · doi:10.1007/BF02760850 |
| [10] | Recursion theory (1982 Summer Institute, Ithaca, New York) 42 |
| [11] | Theory of recursive functions and effective computability (1967) · Zbl 0183.01401 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
