The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals. (English) Zbl 1367.03077
The paper is devoted to the study of generic computations – the motivation for the latter is derived from complexity theory. It is shown that generic reduction is \(\Pi_{1}^{1}\)-complete. Therefore the author works with the generic degrees of density-1 reals. It is demonstrated how an understanding of these degrees leads to a greater understanding of the overall structure of the generic degrees. The density-1 sets are used to provide a new characterization of the hyperarithmetical Turing degrees.
Reviewer: Roman Murawski (Poznań)
MSC:
| 03D30 | Other degrees and reducibilities in computability and recursion theory |
| 03D15 | Complexity of computation (including implicit computational complexity) |
References:
| [1] | DOI: 10.1016/0022-0000(91)90007-R · Zbl 0825.68420 · doi:10.1016/0022-0000(91)90007-R |
| [2] | DOI: 10.1090/S0002-9947-1978-0491103-7 · doi:10.1090/S0002-9947-1978-0491103-7 |
| [3] | DOI: 10.1112/jlms/jdr051 · Zbl 1247.03076 · doi:10.1112/jlms/jdr051 |
| [4] | Higher Recursion Theory (1990) · Zbl 0716.03043 |
| [5] | DOI: 10.1016/S0021-8693(03)00167-4 · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4 |
| [6] | Recursively Enumerable Sets and Degrees (1987) |
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.
