Dynamic notions of genericity and array noncomputability (Q1295423)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Dynamic notions of genericity and array noncomputability
scientific article

    Statements

    Dynamic notions of genericity and array noncomputability (English)
    0 references
    0 references
    13 March 2000
    0 references
    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?
    0 references
    0 references
    degrees of unsolvability
    0 references
    generic sets
    0 references
    \(\Delta^0_2\) degrees
    0 references
    dynamic genericity
    0 references
    computable approximations
    0 references
    dynamically generic degree
    0 references
    pb-generic degree
    0 references
    array nonrecursiveness
    0 references