Dynamic notions of genericity and array noncomputability (Q1295423)

From MaRDI portal
Revision as of 20:49, 28 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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