Dynamic notions of genericity and array noncomputability

DOI10.1016/S0168-0072(98)00014-1zbMath0932.03048MaRDI QIDQ1295423

Benjamin Schaeffer

Publication date: 13 March 2000

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

generic setsdegrees of unsolvability\(\Delta^0_2\) degreesarray nonrecursivenesscomputable approximationsdynamic genericitydynamically generic degreepb-generic degree

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (7)

TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES ⋮ A semilattice generated by superlow computably enumerable degrees ⋮ Turing jumps in the Ershov hierarchy ⋮ Π₁⁰ classes and strong degree spectra of relations ⋮ Multiple genericity: a new transfinite hierarchy of genericity notions ⋮ Maximality and collapse in the hierarchy of α-c.a. degrees ⋮ Low Level Nondelegability Results: Domination and Recursive Enumeration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimal degrees recursive in 1-generic degrees
• Array nonrecursive degrees and lattice embeddings of the diamond
• A Refinement of Lown and Highn for the R.E. Degrees
• Complementation in the Turing degrees
• A 1-generic degree which bounds a minimal degree
• The degrees below a 1-generic degree < 0′
• Recursively enumerable generic sets
• The strong anticupping property for recursively enumerable degrees
• Computability and Recursion
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

This page was built for publication: Dynamic notions of genericity and array noncomputability