Dynamic notions of genericity and array noncomputability

Annals of Pure and Applied Logic 95 (1-3):37-69 (1998)
  Copy   BIBTEX

Abstract

We examine notions of genericity intermediate between 1-genericity and 2-genericity, especially in relation to the Δ20 degrees. We define a new kind of genericity, dynamic genericity, and prove that it is stronger than pb-genericity. Specifically, we show there is a Δ20 pb-generic degree below which the pb-generic degrees fail to be downward dense and that pb-generic degrees are downward dense below every dynamically generic degree. To do so, we examine the relation between genericity and array noncomputability, deriving some structural information about the Δ20 degrees in the process

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,337

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Abstract complexity theory and the Δ20 degrees.Benjamin Schaeffer - 2002 - Annals of Pure and Applied Logic 115 (1-3):195-231.
Lowness for genericity.Liang Yu - 2006 - Archive for Mathematical Logic 45 (2):233-238.
Schnorr triviality and genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.
Partition Genericity and Pigeonhole Basis Theorems.Benoit Monin & Ludovic Patey - 2024 - Journal of Symbolic Logic 89 (2):829-857.
On Genericity and Ershov's Hierarchy.Amy Gale & Rod Downey - 2001 - Mathematical Logic Quarterly 47 (2):161-182.
The Turing degrees below generics and randoms.Richard A. Shore - 2014 - Journal of Symbolic Logic 79 (1):171-178.
Subsimple Groups.Frank Wagner - 2005 - Journal of Symbolic Logic 70 (4):1365 - 1370.

Analytics

Added to PP
2014-01-16

Downloads
35 (#646,056)

6 months
9 (#485,111)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Computability and recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
A Refinement of Low n and High n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1-5):5-12.
Minimal degrees recursive in 1-generic degrees.C. T. Chong & R. G. Downey - 1990 - Annals of Pure and Applied Logic 48 (3):215-225.
The degrees below a 1-generic degree $.Christine Ann Haught - 1986 - Journal of Symbolic Logic 51 (3):770 - 777.

View all 8 references / Add more references