Dynamic notions of genericity and array noncomputability
type: Item
instance of: scholarly article
title: Dynamic notions of genericity and array noncomputability
zbMATH Open document ID: 0932.03048
DOI: 10.1016/S0168-0072(98)00014-1
author: Benjamin Schaeffer
published in: Annals of Pure and Applied Logic
publication date: 2000-03-13T00:00:00Z
review text: The notion of pb-genericity, lying properly between 1-genericity and 2-genericity, was studied by \textit{R. Downey}, \textit{C. G. Jockusch} and \textit{M. Stob} [``Array nonrecursive degrees and genericity'', in: S. B. Cooper et al. (eds.), Computability, enumerability, unsolvability: Directions in recursion theory, Lond. Math. Soc. Lect. Note Ser. 224, 93-104 (1996; Zbl 0849.03029)]. It involves primitive recursive bounds on computations. The present author defines a stronger property, dynamic genericity, and constructs a set that exhibits it. Dynamic genericity turns on a set's computable approximations, hence applies only to \(\Delta^0_2\) sets. He shows that pb-generic degrees are downward dense below any dynamically generic degree (that is, if \(\underset\widetilde{} 0\neq\underset\widetilde{} b\leq\underset\widetilde{} a\) and \(\underset\widetilde{} a\) is dynamically generic, there is some pb-generic \(\underset\widetilde{} c\leq\underset\widetilde{} b\)), but not below every \(\Delta^0_2\) pb-generic degree. The property of array nonrecursiveness [loc. cit.] is exploited in the arguments. Open questions are raised: Can the requirement of dynamic genericity be weakened in the cited result? Are dynamically generic degrees themselves downward dense below dynamically generic degrees?
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1308098
zbMATH Keywords: degrees of unsolvability
zbMATH Keywords: generic sets
zbMATH Keywords: \(\Delta^0_2\) degrees
zbMATH Keywords: dynamic genericity
zbMATH Keywords: computable approximations
zbMATH Keywords: dynamically generic degree
zbMATH Keywords: pb-generic degree
zbMATH Keywords: array nonrecursiveness
reviewed by: Joseph S. Ullian
MaRDI profile type: Publication
cites work: Minimal degrees recursive in 1-generic degrees
cites work: Q3691650
cites work: The strong anticupping property for recursively enumerable degrees
cites work: Array nonrecursive degrees and lattice embeddings of the diamond
cites work: Q4863240
cites work: The degrees below a 1-generic degree < 0′
cites work: Q3905267
cites work: Q3724315
cites work: A 1-generic degree which bounds a minimal degree
cites work: Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
cites work: Recursively enumerable generic sets
cites work: A Refinement of Lown and Highn for the R.E. Degrees
cites work: Q3727983
cites work: Complementation in the Turing degrees
cites work: Computability and Recursion
Recommended article: Nonexistence of minimal pairs for generic computability
Recommended article: Q4863237
Recommended article: A MINIMAL PAIR IN THE GENERIC DEGREES
Recommended article: The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals
Recommended article: Degrees bounding minimal degrees
Recommended article: Relative recursive enumerability of generic degrees
Recommended article: A WEAKLY 2-GENERIC WHICH BOUNDS A MINIMAL DEGREE
Recommended article: Generic complexity of first-order theories
Recommended article: Separating weak \(\alpha\)-change and \(\alpha\)-change genericity
Recommended article: COMPUTABLE DOWD-TYPE GENERIC ORACLES
description: scientific article; zbMATH DE number 1308098