Dynamic notions of genericity and array noncomputability (Q1295423): Difference between revisions

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?