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 sets; degrees of unsolvability; \(\Delta^0_2\) degrees; array nonrecursiveness; computable approximations; dynamic genericity; dynamically generic degree; pb-generic degree

Mathematics Subject Classification ID

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

Π₁⁰ classes and strong degree spectra of relations, A semilattice generated by superlow computably enumerable degrees, Turing jumps in the Ershov hierarchy, Low Level Nondelegability Results: Domination and Recursive Enumeration, TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item